25958번 - 예쁜수

문제

1ドル$보다 크거나 같은 정수 $N$의 각 자리의 합을 $S$라고 할 때, $S$가 $N$의 약수라면 그 수를 예쁜수라고 하자.

지수는 자연수 $M$($M \leq 5,000円$)을 예쁜수들의 합으로만 표현하고 싶다.

이때 합이 $M$인 예쁜수들의 구성이 다른 경우에만 다른 방법이다.

예를 들어 $M=4$인 경우, 1ドル+1+2=4$과 2ドル+1+1=4$는 같은 경우다.

지수를 도와 자연수 $M$을 예쁜수들의 합으로만 표현하는 경우의 수를 구해주자.

경우의 수는 매우 클 수 있으므로 자연수 $M$을 예쁜수들의 합으로 표현하는 경우의 수를 $K$(10ドル^{6} \leq K \leq 10^{7},ドル $K$는 소수)로 나눈 나머지를 구해주자.

입력

첫 번째 줄에 자연수 $M$(1ドル \leq M \leq 5,000円$)과 $K$(10ドル^{6} \leq K \leq 10^{7},ドル $K$는 소수)가 공백으로 구분되어 주어진다.

출력

$M$을 예쁜수들의 합으로만 표현하는 방법의 수를 $K$로 나눈 나머지를 출력하시오.

제한

힌트