Submission #559223

---

Source Code Expand

import sys

N , M = map(int, raw_input().split())
table = [[[0 for x in range(M + 1)] for x in range(N + 1)] for x in range(N + 1)]
s = list(raw_input())
ans = 0

def dp(i):
	if s[i] == '?':
		for x in range(N):
			for y in range(M + 1):
				if x % 2 == 1:
					table[i + 1][1][y] += table[i][x][y]
					if y + (x + 1) / 2 > M:
						table[i + 1][x + 1][M] += table[i][x][y]
					else:
						table[i + 1][x + 1][y + (x + 1) /2] += table[i][x][y]
					table[i + 1][0][y] += table[i][x][y] * 8
				else:
					table[i + 1][x + 1][y] += table[i][x][y]
					table[i + 1][0][y] += table[i][x][y] * 9
	else:
		if s[i] == '2':
			for x in range(N):
				for y in range(M + 1):
					if x % 2 == 0:
						table[i + 1][x + 1][y] += table[i][x][y]
					else:
						table[i + 1][1][y] += table[i][x][y]
		elif s[i] == '5':
			for x in range(N):
				for y in range(M + 1):
					if x % 2 == 1:
						if y + (x + 1) / 2 > M:
							table[i + 1][x + 1][M] += table[i][x][y]
						else:
							table[i + 1][x + 1][y + (x + 1) / 2] += table[i][x][y]
					else:
						table[i + 1][0][y] += table[i][x][y]
		else:
			for x in range(N):
				for y in range(M + 1):
					table[i + 1][0][y] += table[i][x][y]
table[0][0][0] = 1
for x in range(N):
	dp(x)

for x in range(N):
	for y in range(M + 1):
		if y >= M: ans += table[N][x][y]

mod = 1000000007
ans = ans % mod
print str(ans)

Submission Info

Judge Result