← 返回题目列表

AtCoder · abc465_e

E. 数字马戏团

中文机器翻译题面 查看原题

分数: 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