1196. 二维跑步 - Hard Version

牛牛在二维空间中跑步!

牛牛在二维坐标中跑步,初始位置 (0,0),然后牛牛跑了 n 步。

  • (i,0) 牛牛可以跑到 (i+1,0),(i+1,1),(i+1,2),(i,0),(i-1,1),(i-1,2)
  • (i,1) 牛牛可以跑到 (i+1,0),(i+1,1),(i+1,2),(i,1),(i-1,0),(i-1,2)
  • (i,2) 牛牛可以跑到 (i+1,0),(i+1,1),(i+1,2),(i,2),(i-1,0),(i-1,1)

每次牛牛跑步都不想跑的太远,于是牛牛想考考你,有多少种跑步方式使得你的 x 坐标最后落在 [-m,m]

答案对 998244353 取模输出。

输入

一行两个正整数,n, m \ (1≤n,m≤3 \times 10^6)

输出

一个整数表示答案。

样例

标准输入 复制文本
5 2
标准输出 复制文本
5616

来源

2020 牛客寒假算法基础集训营

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 12
通过 5