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

노트