human
Give me a the Python program you requested given the following:
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 ≤ |s| ≤ 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.

Examples

Input

25

Output

1

Input

_00

Output

9

Input

_XX

Output

9

Input

0

Output

1

Input

0_25

Output

0

Note

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

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

In the fifth example, all possible s will have at least one leading zero.
Using python3 can you solve the prior task?
assistant
#Here is the Python program you requested.

import sys
sys.setrecursionlimit(100000)
 
def _r(): return sys.stdin.buffer.readline()
def rs(): return _r().decode('ascii').strip()
def rn(): return int(_r())
def rnt(): return map(int, _r().split())
def rnl(): return list(rnt())

def solve(s):
    if len(s) == 1:
        return int(s in '0_X')
    def _solve(s):
        if s[0] == '0':
            return 0
        uc = s.count('_')
        xm = 10 if 'X' in s else 1
        return xm*10**uc if s[0] not in 'X_' else xm*10**uc//10*9
    l2 = s[-2:]
    if l2 in ('25', '50', '75', '00'):
        return _solve(s)
    elif l2 == 'XX':
        return _solve(s.replace('X', '0'))
    elif l2 == 'X5':
        return _solve(s.replace('X', '2')) + _solve(s.replace('X', '7'))
    elif l2 == 'X0':
        return _solve(s.replace('X', '5')) + _solve(s.replace('X', '0'))
    elif l2 == '2X' or l2 == '7X':
        return _solve(s.replace('X', '5'))
    elif l2 == '5X' or l2 == '0X':
        return _solve(s.replace('X', '0'))
    elif l2 == '__':
        return _solve(s[:-2] + '25') + _solve(s[:-2] + '50') + _solve(s[:-2] + '75') + _solve(s[:-2] + '00')
    elif l2 == '_5':
        return _solve(s[:-2] + '25') + _solve(s[:-2] + '75')
    elif l2 == '_0':
        return _solve(s[:-2] + '50') + _solve(s[:-2] + '00')
    elif l2 == '2_' or l2 == '7_':
        return _solve(s[:-1] + '5')
    elif l2 == '5_':
        return _solve(s[:-1] + '0')
    elif l2 == '_X':
        return _solve(s.replace('X', '0')[:-2] + '00') + _solve(s.replace('X', '0')[:-2] + '50') + _solve(s.replace('X', '5')[:-2] + '25') + _solve(s.replace('X', '5')[:-2] + '75')
    elif l2 == 'X_':
        return _solve(s.replace('X', '0')[:-2] + '00') + _solve(s.replace('X', '5')[:-2] + '50') + _solve(s.replace('X', '2')[:-2] + '25') + _solve(s.replace('X', '7')[:-2] + '75')
    return 0

print(solve(rs()))
 
# for _ in range(rn()):
#     n = rn()
#     edges = [rnt() for _ in range(n-1)]
#     print(solve(n, edges))