No.1100 Boxes
SSRS
37zigenProblem Statement
You put $N$ mutually distinguishable balls into $K$ mutually distinguishable boxes.
However, you want the number of boxes containing no balls to be odd.
Find the number of ways to put the balls that satisfy this condition.
Since the answer can be very large, output it modulo $998244353$.
Input
$N \ K$
The input satisfies the following constraints.
- All inputs are integers
- $1 \leq N \leq 10^7$
- $1 \leq K \leq 10^5$
Output
Output the number of ways to put the balls that satisfy the condition, modulo $998244353$.
Sample
Sample 1
Input
2 3
Output
6
There are 2 balls and 3 boxes.
If the 2 balls are put into the same box, the number of boxes containing no balls is 2, which does not satisfy the condition.
If the 2 balls are put into different boxes, the number of boxes containing no balls is 1, which satisfies the condition.
Therefore, the answer equals the number of ways to put the 2 balls into different boxes, which is 6.
Sample 2
Input
4 1
Output
0
All the balls must be put into the same box, so no matter how they are put, the number of boxes containing no balls is 0 (even).
Sample 3
Input
5 4
Output
604
Sample 4
Input
1000 100
Output
656749944
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。