쿠옹이는 어느 날 갑자기 이런 궁금증이 들었다. '연산 결과가 $N$이 되는 수식은 몇 개가 있을까?'

쿠옹이는 연산 결과가 $N$이 되는 수식의 뒤에 +0, -0 등을 이어 붙이면 여전히 연산 결과가 $N$이므로 이 시행을 반복하면 연산 결과가 $N$인 수식을 무한히 만들 수 있다는 슬픈 사실을 깨닫고 말았다.

그래서 쿠옹이는 수식의 길이가 $M$이어야 한다는 제약을 추가했지만 이번에는 답을 내지 못했다. 여러분이 대신 이 문제를 풀어 주자!

수식은 다음과 같이 정의된다.

• 항은 0, 1, 2, 3, 4, 5, 6, 7, 8, 9만으로 구성되어 있으며 0으로 시작하지 않는 길이 $1$ 이상의 문자열이다. 단 0은 0으로 시작하지만 예외적으로 항이다.
• 수식은 $1$개 이상의 항을 포함하며 각 항이 + 또는 -로 구분되어 있는 문자열이다.

다르게 설명하면 수식은 다음 정규식을 만족하는 문자열을 말한다.

• (([1-9][0-9]*|'0')[+-]))*([1-9][0-9]*|'0')

Input

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($0 \le N \le 10^5, 1 \le M \le 11$)

Output

길이 $M$의 연산 결과가 $N$이 되는 서로 다른 수식의 수를 출력하라. 이때 그러한 수식이 아주 많을 수 있으므로 $10^9+7$로 나눈 나머지를 대신 출력하라.

Examples

Input 1

5 3

Output 1

11

Input 2

123 3

Output 2

1

Input 3

100000 5

Output 3

0

Input 4

0 2

Output 4

0

Input 5

10 3

Output 5

9

Note

예제 1: 길이 $3$의 연산 결과가 $5$가 되는 수식은 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, 9-4의 $11$개이다.

예제 2: 수식은 +나 -를 포함하지 않을 수도 있다.

예제 5: 수식은 +나 -로 시작할 수 없다.