Problem K: 奇怪的打印机

Problem K: 奇怪的打印机

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 62  Solved: 18
[Submit][Status][Web Board]

Description

在新格尔软件公司有一个奇怪的打印机,打印数字的时候经常会把一些数字打印的不是很清楚。这让打印机管理员菜乐武很是苦恼。

这次他遇到了一个很大的数字N (1≤N≤10^5000000),其中若干位被打印的不是很清晰(被覆盖的位不连续)。那些伟数可以是0~9中的任何数。

他想知道求N有多少种可能能够被M整除,他又是一个很奇怪的人,所以只需要把答案模1,000,000,007告诉他就可以了。

顺带一提,N可以有首零。

Input

题目包含多组数据。

输入的第一行有一个整数T (1≤T≤10) 代表有T组数据。

对于每组数据分为两行:

第一行有两个整数LN M (1≤ LN≤5,000,000 , 1≤M≤20)LN代表N的位数,M如上所述。

第二行有一个字符串,代表一个数字,其中打印不清楚的数位用字母X表示。

Output

对于每组数据,输出的第一行为Case #x: ,其中x是数据编号(从1开始),

第二行有一个整数,输出答案。

Sample Input

1
2 13
2X

Sample Output

Case #1:
1

HINT

[Submit][Status]