#P5223. Function

Function

题目背景

CYJian{\rm CYJian}最近想起了水の三角,他觉得太水了,于是想了一个更加有意思的版本。

题目描述

给你NNKK,请你求出:

i=1Kf[N][i] (mod 998244353)\sum_{i=1}^{K}f[N][i] \ (\bmod\ 998244353)

其中:

$$f[i][j]=f[i-1][j]+f[i][j-1]+f[i-1][j-1](i>1,j \leq i) $$$$f[1][1] = 1 \qquad f[i][0] = 0 \qquad f[i][j]=0(j>i) $$

输入格式

第一行两个正整数表示NNKK

输出格式

一行,输出上面式子的值。

1 1
1

2 2

3

3 3

11

4 3

23

提示

对于10%10\%的数据:1N1031K1021 \leq N \leq 10^3 \qquad 1 \leq K \leq 10^2

对于30%30\%的数据:1N1061K1021 \leq N \leq 10^6 \qquad 1 \leq K \leq 10^2

对于50%50\%的数据:1N10181K1021 \leq N \leq 10^{18} \qquad 1 \leq K \leq 10^2

对于另20%20\%的数据:1N1061K1031 \leq N \leq 10^6 \qquad 1 \leq K \leq 10^3

对于100%100\%的数据:1N10181K1031 \leq N \leq 10^{18} \qquad 1 \leq K \leq 10^3

保证KNK \leq N

Upd:时限改为了:第11~3535的测试点时限为600ms600ms,第3636~5050的测试点时限为400ms400ms