← 返回题目列表

Codeforces · 1575/D

D. 可被二十五整除

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

Chanek 先生有一个由字符串 $$$s$$$ 表示的整数。零个或多个数字已被删除并由字符 _ 表示。还有零个或多个数字由字符 X 标记,这意味着它们是相同的数字。

Chanek 先生想要计算可能的整数 $$$s$$$ 的数量,其中 $$$s$$$ 可以被 $$$25$$$ 整除。当然,$$$s$$$ 不能包含任何前导零。他可以将字符 _ 替换为任何数字。他还可以将字符X替换为任意数字,但是对于每个字符X来说必须是相同的。

请注意,前导零是位置表示法中数字字符串中第一个非零数字之前的任何 0 数字。例如,0025 有两个前导零。整数零是一个例外(0 没有前导零,但 0000 有三个前导零)。

输入

一行包含字符串 $$$s$$$ ($$$1 \leq |s| \leq 8$$$)。字符串 $$$s$$$ 由字符 0、1、2、3、4、5、6、7、8、9、_ 和 X 组成。

输出

输出一个整数,表示可能的整数 $$$s$$$ 的数量。

示例

输入 #1

25

输出 #1

1

输入 #2

_00

输出 #2

9

输入 #3

_XX

输出 #3

9

输入#4

0

输出#4

1

输入 #5

0_25

输出 #5

0

注意

在第一个示例中,唯一可能的 $$$s$$$ 是 $$$25$$$。

在第二个和第三个示例中,$$$s \in \{100, 200,300,400,500,600,700,800,900\}$$$。

在第五个示例中,所有可能的 $$$s$$$ 将至少有一个前导零。