Divisible by Twenty-Five

2000ms

524288K

Description:

Mr. Chanek has an integer represented by a string $$$s$$$. Zero or more digits have been erased and are denoted by the character _. There are also zero or more digits marked by the character X, meaning they're the same digit.

Mr. Chanek wants to count the number of possible integer $$$s$$$, where $$$s$$$ is divisible by $$$25$$$. Of course, $$$s$$$ must not contain any leading zero. He can replace the character _ with any digit. He can also replace the character X with any digit, but it must be the same for every character X.

As a note, a leading zero is any 0 digit that comes before the first nonzero digit in a number string in positional notation. For example, 0025 has two leading zeroes. An exception is the integer zero, (0 has no leading zero, but 0000 has three leading zeroes).

Input:

One line containing the string $$$s$$$ ($$$1 \leq |s| \leq 8$$$). The string $$$s$$$ consists of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _, and X.

Output:

Output an integer denoting the number of possible integer $$$s$$$.

Sample Input:

Sample Output:

Sample Input:

_00

Sample Output:

Sample Input:

_XX

Sample Output:

Sample Input:

Sample Output:

Sample Input:

0_25

Sample Output:

Note:

In the first example, the only possible $$$s$$$ is $$$25$$$.

In the second and third example, $$$s \in \{100, 200,300,400,500,600,700,800,900\}$$$.

In the fifth example, all possible $$$s$$$ will have at least one leading zero.

Informação

Provedor Codeforces

Código CF1575D