You are given a telephone number of length $N$. Assume that the two phone numbers are similar if the following conditions are met:

1. They are different.
2. The number of positions that contains different digits does not exceed $K$.
3. The difference between the corresponding figures in the numbers does not exceed 1.

Your task is to find how many such numbers are similar to this phone number. Since the answer can be very large, print it modulo $10^9+7$.

Input format

• The first line indicates two space-separated numbers $N, K$.
• The next line contains $N$ digits.

Output format
Print one number denoting the answer modulo $10^9+7$.

Constraints
$1 ⩽ N ⩽ 10^4$
$1 ⩽ K ⩽ 100$