Условие недоступно на русском языке
D. 쿠옹이의 궁금증
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

쿠옹이는 어느 날 갑자기 이런 궁금증이 들었다. '연산 결과가 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 ≤ N ≤ 105, 1 ≤ M ≤ 11)

Output

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

Examples
Input
5 3
Output
11
Input
123 3
Output
1
Input
100000 5
Output
0
Input
0 2
Output
0
Input
10 3
Output
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: 수식은 +나 -로 시작할 수 없다.