시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 178 | 129 | 111 | 77.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$로 나눈 나머지를 출력하시오.
10 1299721
42
$1\,299\,721$은 소수다.
100 1299721
1024698