Solve this please

[ghost]

You are given an employee number of length P. Assume that the two employee numbers are similar if the following conditions are met:
They are different.
The number of positions that contains different digits does not exceed Q
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 employee number. Since the answer can be very large, print it modulo 10^9+7
Input format
The first line indicates two space-separated numbers P Q
The next line contains P digits.
Output format
Print one number denoting the answer modulo 10^9+7
Sample Input
3 2
012
Output
13
Explanation
Similar 13 employee numbers: 001, 002, 003, 011, 013, 021, 022, 023, 102, 111, 112, 113, 122.