银河幸运星

题目描述

在新春之际，某游戏推出了一个幸运大乐透的抽奖活动，所有玩家均可参与抽奖。 活动共持续 $m$ 天，全服务器所有玩家每天可以进行选择是否参与抽奖活动，如果放弃参加抽奖活动，则每天可以领取到固定 $100$ 个活动代币，而如果参与抽奖，则有概率获得如下奖项：

1. 特等奖( $500000$ 活动代币)：在所有玩家中抽取 $p$ 位特等奖获得者。
2. 一等奖( $600$ 活动代币)：在除去特等奖获奖玩家之外的其他玩家中，将会随机有 $10\%$ 的玩家成为一等奖获得者。
3. 二等奖( $50$ 活动代币)：剩余的 $90\%$ 玩家会成为二等奖获得者。

同时，为了保证活动的公平性，还有一条补充规则，即不会有玩家重复得到特等奖。

由于Orange是一个理性的赌狗，他认为，如果固定每天领取 $100$ 个活动代币的话，最后总和也只有 $700$ 个活动代币，但是只要有一天中了一等奖以上的奖项，那么至少也有 $600 + 50 \times 6 = 900$ 个活动代币，因此Orange决定梭哈抽奖！（梭哈是一种智慧）

现在，假设共有 $n$ 位玩家每天都固定参与抽奖，你的任务是，计算出Orange得到 $x$ 次一等奖的概率。

由于题目中可能出现无法被有限小数表示的实数，因此你只需要求出这个值对 $998244353$ 取模的结果。

正式地说，答案对 $998 244 353$ 取模表达了如下含义。令 $M = 998 244 353$，可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 均为整数，且 $q \not \equiv 0 \pmod M$。你需要输出 $p · q^{−1} \mod M$。换句话说，你需要输出满足 $0 ≤ x < M$ 且 $x · q ≡ p \pmod M$ 的整数 $x$。

输入格式

输入共一行，包含四个整数 $n,m,p,x$，分别如上述题意所述。

数据范围

测试点的区别主要来自对于 $m$ 的约束和 $p$ 具有的特殊性质。

对于所有测试数据的约束： $1 \le n < 998244353$ $1 \le m \le 10^5$ $0 \le x \le m$ $1 \le m \times p \le n$

输出格式

输出共一行，包含一个整数表示答案。

样例 #1

样例输入 #1

100 7 0 0

样例输出 #1

352532689

提示

样例解释1：

容易知道，当 $p = 0, x = 0$ 时，$\text{ans} = (\frac{9}{10})^{7}=\frac{4782969}{10^7}$。而 $352532689 \times 10^7 \equiv 4782969 \pmod {998244353}$，且 $1 \le 352532689 < 998244353$，因此 $352532689$ 是一个合法的答案。