题目描述

请求出满足 $1 \le x \le N$ 且恰好满足下面三个条件中的一个的整数 $x$ 的个数，答案对 $998244353$ 取模。

• $x$ 是 $3$ 的倍数；
• $x$ 的十进制表示中含有数字 3；
• $x$ 的十进制表示中恰好用到 $3$ 种不同的数字。

其中整数的十进制表示不含多余的前导 0。

输入格式

N

输出格式

输出答案对 $998244353$ 取模的结果。

输入示例 1

45

输出示例 1

19

示例 1 说明

$1$ 到 $45$ 中恰好满足一个条件的整数共 $19$ 个：

• 只满足第 $1$ 个条件的有 $6, 9, 12, 15, 18, 21, 24, 27, 42, 45$，共 $10$ 个；
• 只满足第 $2$ 个条件的有 $13, 23, 31, 32, 34, 35, 37, 38, 43$，共 $9$ 个；
• 只满足第 $3$ 个条件的不存在（两位数最多只有 $2$ 种数字）。

注意 $3, 30, 33, 36, 39$ 这些数同时满足第 $1$、$2$ 个条件，属于「满足两个」，不计入答案。

输入示例 2

1013

输出示例 2

424

示例 2 说明

举几个例子：

• 只满足第 $1$ 个条件的有 $555$、$1011$ 等；
• 只满足第 $2$ 个条件的有 $343$、$553$ 等；
• 只满足第 $3$ 个条件的有 $1012$、$704$ 等。

输入示例 3

2

输出示例 3

0

示例 3 说明

$1$ 和 $2$ 三个条件一个都不满足，所以答案是 $0$。「一个都不满足」也不算「恰好满足一个」。

输入示例 4

314159265358979323846264338327950

输出示例 4

658111391

示例 4 说明

$N$ 可以非常大（最多 $500$ 位），远远超出任何内置整数类型，只能当成字符串读入。

约束条件

• $N$ 是整数
• $1 \le N < 10^{500}$