#P13890. [蓝桥杯 2023 省 Python A] 奇怪的数

[蓝桥杯 2023 省 Python A] 奇怪的数

题目描述

小蓝最近在找一些奇怪的数,其奇数数位上是奇数,而偶数数位上是偶数。同时,这些数的任意 5 个连续数位的和都不大于 mm

例如当 m=9m = 9 时,10101101011230312303 就是奇怪的数,而 12345123451111111111 则不是。

小蓝想知道一共有多少个长度为 nn 的上述的奇怪的数。你只需要输出答案对 998244353998244353 取模的结果。

输入格式

输入一行包含两个整数 n,mn, m,用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

5 5
6

提示

【评测用例规模与约定】

对于 30%30\% 的评测用例,n12n \leq 12

对于 60%60\% 的评测用例,n5000n \leq 5000

对于所有评测用例,5n2×1055 \leq n \leq 2 \times 10^50m500 \leq m \leq 50