시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB17812911177.083%

문제

$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$로 나눈 나머지를 출력하시오.

예제 입력 1

10 1299721

예제 출력 1

42

$1\,299\,721$은 소수다.

예제 입력 2

100 1299721

예제 출력 2

1024698

출처

University > 아주대학교 > 2022 아주대학교 프로그래밍 경시대회 APC D번