곱 부분집합 계수 세기

정수 $n$과 $k$에 대해 $[n]=\{1,2,\dots,n\}$이라고 하자. $f(n,k)$는 $[n]$의 모든 $k$개 원소 부분집합을 고른 뒤, 각 부분집합에 들어 있는 원소들의 곱을 모두 더한 값이다. 즉,

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

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

자연수 $n$과 소수 $p$가 주어질 때, $0\le k\le n$인 정수 $k$ 중에서 $f(n,k)$가 $p$로 나누어떨어지지 않는 것의 개수를 구하시오.

첫째 줄에 정수 $n$과 소수 $p$가 공백으로 구분되어 주어진다.

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

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