33945번 - 쿠옹이의 궁금증

문제

쿠옹이는 어느 날 갑자기 이런 궁금증이 들었다. '연산 결과가 $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$로 나눈 나머지를 대신 출력하라.

제한

힌트