생일 선물

시간 제한2초메모리 제한1024 MB

요약

자릿수가 a이고 인접한 두 자리 숫자가 서로 같지 않으며 225로 나눈 나머지가 b인 수의 개수를 10^9+7로 나눈 값을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 행렬, 수학
정답자: 아직 제출이 없습니다

문제

금성에 사는 친구의 생일입니다. 친구의 정확한 나이는 기억나지 않지만, $10^{18}$ 년을 넘지 않는다는 것은 확실합니다. 앞자리가 0이 아닌 십진수를 생일 선물로 줍니다. 숫자의 자릿수는 친구의 나이와 같아야 합니다. 숫자를 더 흥미롭게 만들기 위해 인접한 두 자리가 서로 같지 않도록 합니다.

금성의 한 해는 $225$ 일이므로, 친구의 생일은 $0$ 부터 $224$ 까지의 정수입니다. 선물 숫자를 $225$ 로 나눈 나머지가 생일을 $225$ 로 나눈 나머지와 같아야 합니다. 선물을 여러 개 줄 수도 있습니다. 가능한 선물의 개수를 $10^9+7$ 로 나눈 나머지로 구하세요.

입력

한 줄에 공백으로 구분된 두 정수 $a$ ( $1 \le a \le 10^{18}$ )와 $b$ ( $0 \le b < 225$ )가 주어집니다. $a$ 는 친구의 나이이고, $b$ 는 친구의 생일입니다.

출력

조건을 만족하는 선물의 개수를 $10^9+7$ 로 나눈 나머지를 한 줄에 출력합니다.

예제5

예제 1
입력
```
12345 200
```
예상 출력
```
323756255
```
예제 2
입력
```
100 87
```
예상 출력
```
896364174
```
예제 3
입력
```
100 35
```
예상 출력
```
785970618
```
예제 4
입력
```
5000 5
```
예상 출력
```
176058968
```
예제 5
입력
```
888888 88
```
예상 출력
```
906317283
```