#13436. 【数位DP练习题】火柴棒等式

【数位DP练习题】火柴棒等式

题目描述

给你 nn 根火柴棍,你可以拼出多少个形如 A+B=CA+B=C 的等式?等式中的 AABBCC 是用火柴棍拼出的整数(若该数非零,则最高位不能是 00)。用火柴棍拼数字 090\sim9 的拼法如图所示:

注意:

  1. 加号与等号各自需要两根火柴棍;
  2. 如果 ABA\neq B,则 A+B=CA+B=CB+A=CB+A=C 视为不同的等式(A,B,C0A,B,C\geq0);
  3. nn 根火柴棍必须全部用上。

输入格式

一个整数 n(1n200000)n(1 \leq n\leq 200000)

输出格式

一个整数,能拼成的不同等式的数目mod 998244353mod \ 998244353

样例 #1

样例输入 #1

14

样例输出 #1

2

样例 #2

样例输入 #2

18

样例输出 #2

9

提示

其实这题可以出成矩阵快速幂的形式,但是我懒的出了,想写矩阵快速幂版本的可以自己写一下。