시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 12 4 3 30.000%

문제

$f(n, k)$는 집합 $[n]$에서 모든 $k$-부분 집합을 구하고, 각 부분 집합에서 원소를 곱한 값을 모두 더한 값이다. 집합 $[n]$은 $1$보다 크거나 같고, $n$보다 작거나 같은 모든 자연수로 이루어진 집합이고, $k$-부분 집합은 크기가 $k$인 부분 집합이다. $f(n, k)$는 다음과 같은 수식으로 표현할 수 있다.

\[\sum_{S \subseteq [n], |S| = k}{\prod_{x \in S}{x}}\]

$f(n, 0) = 1$이다.

$f(n, k)$를 구하는 것은 지루하기 때문에, 재미있는 값을 구하려고 한다. 자연수 $n$과 소수 $p$가 주어졌을 때, $f(n, k)$가 $p$로 나누어 떨어지지 않는 $k$ $(0 \le k \le n)$의 개수를 구해보자.

입력

첫째 줄에 정수 $n$과 소수 $p$가 주어진다.

출력

문제 조건을 만족하는 $k$의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

제한

  • $1 \le n < 10^{501}$
  • $2 \le p \le 10^5$
  • $p$는 소수

예제 입력 1

4 2

예제 출력 1

2

$f(4, k)$는 다음과 같다.

  • $f(4, 0) = 1$
  • $f(4, 1) = 1+2+3+4 = 10$
  • $f(4, 2) = 1\cdot 2 + 2\cdot 3 + 3\cdot 4 + 4\cdot 1 + 1\cdot 3 + 2\cdot 4 = 35$
  • $f(4, 3) = 1\cdot 2\cdot 3 + 2\cdot 3\cdot 4 + 1\cdot 3 \cdot 4 + 1\cdot 2\cdot 4 = 50$
  • $f(4, 4) = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

$k = 0$, $k = 2$인 경우만 $p = 2$로 나누어 떨어지지 않는다.