1936번 - 재미있는 수학 문제 분류

$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$는 소수