Note

Problem Statement

You are given a string $S$ consisting of characters from '0' to '9', and a positive integer $M$.
Output, mod 1,000,000,007$=10^9 + 7$, the total number of subsequences of one or more characters that, when interpreted as a decimal number, are multiples of $M$.
Here, a subsequence of a string $S$ is a string that can be expressed as $S[a_1]S[a_2]\cdots S[a_k]$ using a sequence $(a_i)_i$ such that
$1 \le a_1 < a_2 < \cdots < a_k\le |S|$
holds. ($S[i]$ is the $i$-th character of $S$.)
Subsequences that are the same as strings but differ in positions are treated as different. For example, when $S="110"$, the subsequence "10" formed by the 1st and 3rd characters and the subsequence "10" formed by the 2nd and 3rd characters are counted separately.
Also, subsequences of two or more characters that start with 0 are not counted. For example, when $S="02", M = 2$, "02" is not regarded as a multiple of 2.

Input

$S$
$M$

$1 \le |S| \le 10,000$
$1 \le M \le 20,000$
Each character of $S$ is between '0' and '9'.
Among the sample cases, those whose file names start with "testcase-small1-" satisfy $1 \le |S| \le 16, 1 \le M \le 1,000 $.
Among the sample cases, those whose file names start with "testcase-small2-" satisfy $1 \le |S| \le 10,000, 1 \le M \le 1,000 $.

Output

Output the result. Print a newline at the end.

Sample

012
3

2

220
2

7

123456789123456789
1

262143