TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

開門見山的說,我們摯愛的曾老師今天遇上了一個生成函數題。

不過他懶得下凡演示他精湛的解微分方程技巧, 這題對他的兩個隊友(神仙數學講師和威力枕頭)來說又太簡單,於是他就把這題交給了你。

給定正整數 $K$,定義生成函數 $F_0(x), F_1(x), F_2(x), \cdots $ 如下:

$ F_0(x) = 1 $ 並且 $$ F_{i+1} = F'_{i}(x) + \frac{1-x^ K}{1-x}F_i(x)$$ 對所有的非負整數 $i$ , 其中 $F'_{i}(x)$ 是 $F_i(x)$ 的微分。

請告訴曾老師 $F_N(0)$ 的值,因為這個數字很大,輸出除以 $998244353$ 的餘數即可。

你現在幫過我,我承諾讓你當神仙隊伍 NoName 的下一任隊員。

Input Format

輸入兩個正整數 $N, K$。

  • $1 \leq N, K \leq 10^ 6$

Output Format

輸出一行整數,代表 $F_N(0) \text{ mod } 998244353$ 的值。

Sample Input 1

2 3

Sample Output 1

2

Sample Input 2

4 2

Sample Output 2

10

Hints

範例一中 $F_N(x) = x^ 4+2x^ 3+3x^ 2+4x+2$

範例二中 $F_N(x) = x^ 4+4x^ 3+12x^ 2+16x+10$

Problem Source

IOICamp 2022 Day5 pC

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~8 $1 \leq N, K \leq 2 \times 10^ 5$ 50
3 0~11 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3
1 3000 262144 65536 1 2 3
2 3000 262144 65536 2 3
3 3000 262144 65536 2 3
4 3000 262144 65536 2 3
5 3000 262144 65536 2 3
6 3000 262144 65536 2 3
7 3000 262144 65536 2 3
8 3000 262144 65536 2 3
9 3000 262144 65536 3
10 3000 262144 65536 3
11 3000 262144 65536 3