882 . 小愛的火柴棒

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

66.7% (2/3)

Tags

ntucpc-speedrun1

Description

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

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

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

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

Input Format

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

  • $1\leq N\leq 10^ {18}$

Output Format

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

Sample Input 1

7

Sample Output 1

12

Sample Input 2

3

Sample Output 2

1

Sample Input 3

1000000

Sample Output 3

811496257

Hints

Problem Source

Subtasks

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

Testdata and Limits

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
Submit
Back to Top