시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB78241633.333%

문제

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

입력

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

출력

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

예제 입력 1

5 3

예제 출력 1

11

길이 $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

123 3

예제 출력 2

1

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

예제 입력 3

100000 5

예제 출력 3

0

예제 입력 4

0 2

예제 출력 4

0

예제 입력 5

10 3

예제 출력 5

9

수식은 +나 -로 시작할 수 없다.