问题描述

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

这次他遇到了一个很大的数字 $N$（$1 \leq N \leq 10^{5000000}$），其中若干位被打印得不是很清晰（被覆盖的位不连续）。那些位数可以是 $0 \sim 9$ 中的任何数。

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

顺带一提，$N$ 可以有前导零。

输入格式

题目包含多组数据。

输入的第一行有一个整数 $T$（$1 \leq T \leq 10$）代表有 $T$ 组数据。

对于每组数据分为两行：

第一行有两个整数 $LN$，$M$（$1 \leq LN \leq 5\,000\,000$，$1 \leq M \leq 20$），$LN$ 代表 $N$ 的位数，$M$ 如上所述。

第二行有一个字符串，代表一个数字，其中打印不清楚的数位用字母 $\texttt{X}$ 表示。

输出格式

对于每组数据，输出的第一行为 $\texttt{Case \#}x\texttt{:}$，其中 $x$ 是数据编号（从 $1$ 开始）。

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

样例输入

1
2 13
2X

样例输出

Case #1:
1