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$.


-----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 \in \{100, 200,300,400,500,600,700,800,900\}$.

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

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Graph traversal

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
from bisect import bisect_left, bisect_right
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
v = []
s = input().strip()
n = len(s)
strt = 10 ** (n - 1)
end = 10 ** n - 1
if n == 1:
	strt = 0
	end = 10
if n == 2:
	strt = 25
	end = 99
while strt < end:
	v.append(strt)
	strt += 25
cnt = 0
for i in range(len(v)):
	target = str(v[i])
	flag = 1
	X = -1
	for i in range(n):
		if s[i] == target[i]:
			continue
		elif s[i] == '_':
			continue
		elif s[i] == 'X':
			if X == -1:
				X = target[i]
			elif target[i] == X:
				continue
			else:
				flag = 0
				break
		else:
			flag = 0
			break
	if flag:
		cnt += 1
print(cnt)


def check(s, i):
	if i == len(s):
		x = ''.join(s)
		if x[0] == '0' and x != '0':
			return 0
		if int(x) % 25 == 0:
			return 1
		return 0
	res = 0
	if s[i] == '_':
		if i != 0 and i < len(s) - 2:
			s[i] = '1'
			res += 10 * check(s, i + 1)
		else:
			for j in range(10):
				s[i] = str(j)
				res += check(s, i + 1)
		s[i] = '_'
		return res
	else:
		return check(s, i + 1)
inp = input()
total = 0
if 'X' in inp:
	for i in range(10):
		s = inp
		s = s.replace('X', str(i))
		total += check(list(s), 0)
else:
	total = check(list(inp), 0)
print(total)


s = input()[::-1]
xval = ['x']

def compare(c, target):
	if c == target:
		return True
	if c == '_':
		return True
	if c == 'X':
		if xval[0] == 'x':
			xval[0] = target
			return True
		else:
			return xval[0] == target
	return False
dic = {}

def getnext(index, xval):
	if index == n - 1:
		if s[index] == '_':
			return 9
		elif s[index] == 'X':
			if xval == 'x':
				return 9
			else:
				return xval != '0'
		else:
			return s[index] != '0'
	if (index, xval) in dic:
		return dic[index, xval]
	output = 0
	if s[index] == '_':
		output = 10 * getnext(index + 1, xval)
	elif s[index] == 'X':
		if xval != 'x':
			output = getnext(index + 1, xval)
		else:
			for c in range(10):
				output += getnext(index + 1, str(c))
	else:
		output = getnext(index + 1, xval)
	dic[index, xval] = output
	return output
n = len(s)
if n == 1:
	if s[0] == '0' or s[0] == '_' or s[0] == 'X':
		print(1)
	else:
		print(0)
	exit()
candidate = ['52', '05', '57']
if n > 2:
	candidate.append('00')
ans = 0
for c0 in range(10):
	for c1 in range(10):
		if n == 2 and c1 == '0':
			continue
		xval[0] = 'x'
		if not compare(s[0], str(c0)) or not compare(s[1], str(c1)):
			continue
		if n == 2:
			if str(c0) + str(c1) in candidate:
				ans += 1
			continue
		if str(c0) + str(c1) in candidate:
			ans += getnext(2, xval[0])
print(ans)


import math
import random
import sys

def main(s):
	if len(s) == 1 and (s[0] == '0' or s[0] == '_' or s[0] == 'X'):
		return 1
	elif s[0] == '0' and len(s) > 1:
		return 0
	elif len(s) == 1:
		return 0
	mult1 = 1
	mult2 = 1
	f = False
	for i in range(len(s) - 2):
		if s[i] == '_':
			if i != 0:
				mult1 *= 10
			else:
				mult1 *= 9
		elif s[i] == 'X' and mult2 == 1:
			if i != 0:
				mult2 = 10
			else:
				mult2 = 9
				f = True
	ans = 0
	for i in range(100):
		if i % 25 != 0:
			continue
		val = list([c for c in str(i)])
		if i == 0:
			val = ['0', '0']
		mult_val = mult2
		check = [s[-2], s[-1]]
		if check[0] == 'X':
			if val[0] == '0' and f:
				continue
			check[0] = val[0]
			mult_val = 1
			if check[1] == 'X':
				check[1] = val[0]
		if check[1] == 'X' and check[0] != 'X':
			if val[1] == '0' and f:
				continue
			check[1] = val[1]
			mult_val = 1
		if check[0] == '_':
			check[0] = val[0]
		if check[1] == '_':
			check[1] = val[1]
		if val == check and (not (len(s) == 2 and check[0] == '0')):
			ans += mult_val * mult1
	return ans
s = input()
print(main(s))


s = input()
ways = 0
if len(s) == 1:
	if s in ['_', 'X', '0']:
		ways = 1
elif len(s) == 2:
	if s in ['25', '50', '75']:
		ways = 1
	elif s in ['__', '_X', 'X_']:
		ways = 3
	elif s == '_0':
		ways = 1
	elif s in ['_5', 'X5']:
		ways = 2
	elif s in ['2_', '5_', '7_', '2X', '5X', '7X', 'X0']:
		ways = 1
else:
	d = s[-2:]
	s = s[:-2]
	if d in ['00', '25', '50', '75', '__', '_X', 'X_', 'XX', '_0', '_5', '0_', '2_', '5_', '7_', 'X0', 'X5', '0X', '2X', '5X', '7X']:
		ways = 1
		xfound = False
		if d in ['__', '_X', 'X_']:
			ways *= 4
		elif d in ['_0', '_5', 'X0', 'X5']:
			ways *= 2
		if 'X' in d:
			xfound = True
		if s[0] == '_' or (s[0] == 'X' and (not xfound)):
			ways *= 9
		if s[0] == 'X':
			xfound = True
		if s[0] == 'X' and d in ['_X', 'X_', 'XX', '0X', 'X0', '5X']:
			if d == 'X0':
				ways //= 2
			elif d in ['_X', 'X_']:
				ways //= 4
				if d == 'X_':
					ways *= 3
				else:
					ways *= 2
			else:
				ways = 0
		if s[0] == '0':
			ways = 0
		for c in s[1:]:
			if c == '_':
				ways *= 10
			elif c == 'X' and (not xfound):
				ways *= 10
				xfound = True
print(ways)


tmp = input()

def can(s, t):
	if len(s) != len(t):
		return False
	if 'X' in t:
		for ch in range(10):
			if can(s, t.replace('X', str(ch))):
				return True
		return False
	for i in range(len(s)):
		if s[i] == t[i] or t[i] == '_':
			continue
		else:
			return False
	return True
if len(tmp) <= 4:
	x = 0
	answer = 0
	while len(str(x)) <= len(tmp):
		if can(str(x), tmp):
			answer += 1
		x += 25
	print(answer)
	exit(0)

def get_prefix(pref):
	if pref[0] == '0':
		return 0
	answer = 1
	if pref[0] == '_':
		answer = 9
	for i in range(1, len(pref)):
		if pref[i] == '_':
			answer *= 10
	return answer

def get_suffix(suff):
	answer = 0
	for good in ['00', '25', '50', '75']:
		if can(good, suff):
			answer += 1
	return answer

def get(t):
	if 'X' in t:
		answer = 0
		for x in range(10):
			answer += get(t.replace('X', str(x)))
		return answer
	if tmp[0] == '0':
		return 0
	pref = t[0:len(t) - 2]
	suff = t[len(t) - 2:len(t)]
	return get_prefix(pref) * get_suffix(suff)
print(get(tmp))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	s = [int(k) if k.isdigit() else k for k in input()]
	if len(s) == 1 and s[0] not in ['_', 'X', 0]:
		print(0)
		continue
	start = 0
	if len(s) > 1:
		start = 10 ** (len(s) - 1)
	while start % 25:
		start += 1
	ans = 0
	done = False
	while 1:
		if done:
			break
		x = start
		ind = len(s) - 1
		XV = None
		pos = True
		while x:
			if ind < 0:
				pos = False
				done = True
				break
			d = x % 10
			if s[ind] == '_':
				pass
			elif s[ind] == 'X':
				if XV is None:
					XV = d
				elif XV != d:
					pos = False
			elif s[ind] != d:
				pos = False
			x = x // 10
			ind -= 1
		if pos:
			ans += 1
		start += 25
	print(ans)


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()))


s = input()
y = s
n = len(s)
m = 1
c = 0
for i in range(0, n - 2):
	if s[i] == '_' and i == 0:
		c = 1
		m *= 9
	elif s[i] == '_':
		c = 1
		m *= 10
val = 0
re = m
if s.count('X') == n and n != 1:
	print(0)
elif n == 2 and (s[-2:] == '__' or s[-2:] == '_X'):
	print(3)
elif n == 1 and (s[0] == '0' or s[0] == '_' or s[0] == 'X'):
	print(1)
elif n == 1 or s[0] == '0':
	print(0)
elif 'X' in s:
	if s[0] == 'X':
		for i in ['1', '2', '3', '4', '5', '6', '7', '8', '9']:
			s = y
			m = re
			s = s.replace('X', i)
			if s[-1] == 'X' and s[-2] == 'X' or (s[-1] == 'X' and s[-2] == '_'):
				m = m
			elif s[-2] == '_' and s[-1] == 'X':
				m = m * 2
			elif s[-1] == '_' and s[-2] == '_':
				m = m * 4
			elif s[-2] == '_' and s[-1] in ['5', '0']:
				m = m * 2
			elif s[-2] in ['2', '5', '7', '0'] and s[-1] == '_':
				m = m
			elif s[-2:] == '25' or s[-2:] == '75' or s[-2:] == '50' or (s[-2:] == '00'):
				m = m
			else:
				m = 0
			val += m
		print(val)
	else:
		for i in ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']:
			s = y
			m = re
			s = s.replace('X', i)
			if s[-1] == 'X' and s[-2] == 'X' or (s[-1] == 'X' and s[-2] == '_'):
				m = m
			elif s[-2] == '_' and s[-1] == 'X':
				m = m * 2
			elif s[-1] == '_' and s[-2] == '_':
				m = m * 4
			elif s[-2] == '_' and s[-1] in ['5', '0']:
				m = m * 2
			elif s[-2] in ['2', '5', '7', '0'] and s[-1] == '_':
				m = m
			elif s[-2:] == '25' or s[-2:] == '75' or s[-2:] == '50' or (s[-2:] == '00'):
				m = m
			else:
				m = 0
			val += m
		print(val)
else:
	if s[-1] == 'X' and s[-2] == 'X' or (s[-1] == 'X' and s[-2] == '_'):
		m = m
	elif s[-2] == '_' and s[-1] == 'X':
		m = m * 2
	elif s[-1] == '_' and s[-2] == '_':
		m = m * 4
	elif s[-2] == '_' and s[-1] in ['5', '0']:
		m = m * 2
	elif s[-2] in ['2', '5', '7'] and s[-1] == '_':
		m = m
	elif s[-2:] == '25' or s[-2:] == '75' or s[-2:] == '50' or (s[-2:] == '00'):
		m = m
	else:
		m = 0
	print(m)


def divisible_by_25(s):
	n = len(s)
	if n < 2:
		if s == '0' or s == '_' or s == 'X':
			return 1
		return 0
	b = s[:n - 2]
	e = s[n - 2:]
	valid_endings = ['25', '50', '75']
	if n >= 3:
		valid_endings = ['00', '25', '50', '75']
	total = 0
	for valid_ending in valid_endings:
		(valid, x) = can_be_made(valid_ending, e)
		if not valid:
			continue
		total += count_variants(x, b)
	return total

def can_be_made(valid_ending, e):
	if e == '__':
		return (True, None)
	for underscore in ['0', '2', '5', '7']:
		for x in ['X', '0', '2', '5', '7']:
			e_ = e.replace('X', x)
			e_ = e_.replace('_', underscore)
			if e_ == valid_ending:
				if x == 'X':
					x = None
				return (True, x)
	return (False, None)

def count_variants(x, b):
	if b == '':
		return 1
	if b[0] == '0':
		return 0
	total = 1
	if b[0] == 'X':
		if x == '0':
			return 0
		if x is None:
			total *= 9
			x = '1'
	if b[0] == '_':
		total *= 9
	for ch in b[1:]:
		if ch == '_':
			total *= 10
		if ch == 'X':
			if x is None:
				total *= 10
				x = '1'
	return total
s = input()
print(divisible_by_25(s))