#1205. 「HB 省队互测 2019 Round2 Day1」电荷冲突的会面

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Edgration

题目描述

众所周知凤凰院凶真非常喜欢研究量子 (Quantum),某天他正在思考如何改进「电话微波炉 (暂定)」。

现在有 K 种量子, N 个时刻,每个时刻会等概率的产生这 K 种量子中的任意一个,然后凶真会将这 N 个量子收集起来。

凶真改进后的「电话微波炉 (暂定)」有 Z 个量子槽,他想选出 Z 个量子放入量子槽中。对于所有放置方案,凶真定义一种方案合法当且仅当每个量子槽中只放入了一个量子,并且第 i 个槽中放入的是第 i 种量子。凶真定义这台「电话微波炉 (暂定)」的潜力为合法放置方案数的 F 次幂 (两个方案不同当且仅当存在至少一个量子槽中的量子产生的时刻不同),并且他想知道这台「电话微波炉 (暂定)」的期望潜力是多少。

凶真将这个问题交给了聪明的你。如果你能答对,凶真会奖励你一个嘟嘟噜的水晶香蕉!

当然啦,凶真为了不为难你,所以你只用告诉凶真这个期望对 998,244,353 取模后的值。

输入格式

从标准输入中读入数据。

一行四个正整数 N,K,Z,F

输出格式

输出到标准输出中。

一行一个整数表示「电话微波炉 (暂定)」的期望潜力。

样例

样例 1 输入

3 2 2 2

样例 1 输出

3

样例 1 解释

对于第一个样例的八种情况分别为:

  • 1 1 1
  • 1 1 2
  • 1 2 1
  • 1 2 2
  • 2 1 1
  • 2 1 2
  • 2 2 1
  • 2 2 2

可知答案为: (0^2+2^2+2^2+2^2+2^2+2^2+2^2+0^2)\div 8 = 3

样例 2 输入

23333 2333 233 23 

样例 2 输出

475713660

数据范围与提示

所有数据满足以下条件。

1\le N\le 10^5 1\le K,Z,F\le 10^9

子任务

  • 子任务一 (9\%)\ N,K,Z,F\le 8
  • 子任务二 (15\%)\ K,Z\le 2
  • 子任务三 (21\%)\ N,K,Z,F\le 3\times 10^2
  • 子任务四 (12\%)\ F=1,N,K,Z\le 10^5
  • 子任务五 (12\%)\ N\le 10^3
  • 子任务六 (31\%) 无特殊限制

提示

设答案化为最简分式后的形式为 \frac ab ,其中 a b 的互质。输出整数 x 使得 bx\equiv a \pmod{998244353} 0\le x < 998244353 。(可以证明这样的整数 x 是唯一的)