#P18489. Cola

Cola

Cola

Alice 有一个喜欢的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N),它是 1,2,…,N1,2,\ldots,N 的一个排列。Bob 得知,如果他猜中了 PP,Alice 就会送他一瓶可乐。于是 Bob 决定通过向 Alice 提问来猜出 PP。

Bob 最多可以提问 MM 次,每次问题如下:选择一个 1,2,…,N1,2,\ldots,N 的排列 Q=(Q1,Q2,…,QN)Q=(Q_1,Q_2,\ldots,Q_N),询问 Alice 她喜欢的排列是否就是 QQ。其中 M≤NM\le N。

Alice 的回应规则为:

  • 如果 P=QP=Q,Alice 送给 Bob 一瓶可乐。
  • 如果 P≠QP\ne Q,Alice 告诉 Bob 满足 Pi≠QiP_i\ne Q_i 的最小下标 ii。

例如,如果 P=(4,3,2,1)P=(4,3,2,1),Bob 提问的排列为 Q=(4,3,1,2)Q=(4,3,1,2),Alice 会告诉他:存在不相等的位置,最小下标为 33。

即使 Bob 在第 MM 次提问之后已经能够确定 PP,只要这些提问中没有实际猜中,他也不会获得可乐。

最初 Bob 对 PP 没有任何信息。请计算他获得可乐的最大概率,并输出这个概率模 998244353998244353 的值。

这是一个离线计算题:输入只有 N,MN,M,程序只输出一个概率值,不进行上述提问交互。

概率模 998244353998244353 的定义

可以证明,所求概率总是有理数。在本题约束下,将概率写成最简分数 y/xy/x 后,保证分母 xx 不被 998244353998244353 整除。此时,存在唯一整数 zz 满足 0≤z<9982443530\le z<998244353 且

y≡xz(mod998244353).y\equiv xz\pmod{998244353}.

输出这个 zz。

输入格式

N M

输入中的数均为整数,满足 1≤M≤N≤1071\le M\le N\le10^7。本题没有测试用例数量 TT。

输出格式

输出所求的概率模 998244353998244353 的值。

样例 1

输入:

2 1

输出:

499122177

只能提问一次,可能的排列有两个,所以得到可乐的最大概率为 1/21/2。即使第一次猜错后已经能确定排列,也不能因此获得可乐。

样例 2

输入:

1 1

输出:

1

Bob 在第一次提问时一定能获得可乐。

样例 3

输入:

167 91

输出:

469117530