分数: 450 点
问题陈述
查找,取模 998244353,整数个数 x 与 1 \leq x \leq N 满足 正好一个 以下三个条件。
- x 是的倍数 3.
- 的十进制表示 x 包含
3. - 在十进制表示中使用了三个不同的数字 x.
这里,整数的十进制表示不应有不必要的前导 0s。
约束
- N 是一个整数。
- 1 \leq N < 10^{500}
输入
输入由标准输入按以下格式给出:
N
输出
输出答案。
样本输入 1
45
示例输出 1
19
中的整数 1 to 45,有 19 恰好满足问题陈述中的条件之一的整数,如下所示。
- 有 10 仅满足第一个条件的整数: 6, 9, 12, 15, 18, 21, 24, 27, 42, 45.
- 有 9 仅满足第二个条件的整数: 13, 23, 31, 32, 34, 35, 37, 38, 43.
- 不存在仅满足第三个条件的整数。
示例输入 2
1013
示例输出 2
424
以下是适用整数的示例。
- 仅满足第一个条件的整数包括 555 和 1011.
- 仅满足第二个条件的整数包括 343 和 553.
- 仅满足第三个条件的整数包括 1012 和 704.
示例输入 3
2
示例输出 3
0
没有适用的整数。
示例输入 4
314159265358979323846264338327950
示例输出 4
658111391