Description

设 F(N) 表示正整数 1 到正整数 N 中,数字 1,2 总共出现了多少次。例如 N = 10 时: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 这 10 个数中,数字 1 出现了两次,数字 2 出现了 1 次,所以数字 1, 2 总共出现了 3 次,因此 F (10) = 3。

现在给你正整数 N ,请你求出 F(N) 的值。由于 F(N) 可能很大,你仅需输出 F(N) 除以 20123 的余数。

Input Format

输入数据仅一行,包含一个正整数 $N (1 ≤ N ≤ 10^{100} )$,表示函数 F(N)的参数。

Output Format

输出仅一个整数,为 F(N) 除以 20123 的余数。

10​

3​

Source

蓝桥杯 算法提高