Description

眾所周知，火柴棒可以拿來拼數字，而 $0$ 到 $9$ 每個數字的拼法如下圖所示：

不同的整數可能會需要使用不同數量的火柴棒，例如： $17$ 需要一個 $1$ 和一個 $7$ ，所以要拼出 $17$ 總共需要 $2 + 3 = 5$ 支火柴棒，而要拼出 $45510$ 則需要 $4 + 5 + 5 + 2 + 6 = 22$ 支火柴棒。

小愛手上有 $N$ 支火柴棒，他想要用盡所有的火柴棒拼出一個非負整數。

小愛拼出的非負整數能有幾種？由於答案可能很龐大，所以請回答答案除以 $998244353$ 的餘數。

Input Format

輸入只有一個正整數 $N$ 。

請輸出一個非負整數，代表小愛能拼出的非負整數種類數除以 $998244353$ 的餘數。

811496257

No.	Testdata Range	Constraints	Score
1	0~2	範例測資	0
2	0~22	無額外限制	100

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	1 2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2
18	1000	524288	65536	2
19	1000	524288	65536	2
20	1000	524288	65536	2
21	1000	524288	65536	2
22	1000	524288	65536	2