5201314

跨过山河人海，我最终只想停在你身旁

给定一个非负整数x，考虑区间[0,10^x - 1]中的所有整数。 问：把这些整数都写成十进制后，数字字符"1"一共出现了多少次？ 答案对5201314取模

漫漫人生路，只想与你一路同行

输入

一行一个整数x（0 <= x <= 18）。

输出

输出一个整数，表示答案对5201314取模后的结果。

样例

2

20

说明

当x=2时，区间是[0,99]。这一百个数字中，字符“1”出现了20次，所以答案是20。

1s, 1024KiB for each test case.