Counting Product Subset Coefficients

For integers $n$ and $k$, let $[n]={1,2,\dots,n}$. The value $f(n,k)$ is the sum, over every $k$-element subset of $[n]$, of the product of the elements in that subset. In other words,

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

Also, $f(n,0)=1$.

Given a positive integer $n$ and a prime $p$, count how many integers $k$ with $0\le k\le n$ make $f(n,k)$ not divisible by $p$.

The first line contains an integer $n$ and a prime $p$, separated by a space.

Print the number of valid values of $k$, modulo $10^9+7$.

• $1 \le n < 10^{501}$
• $2 \le p \le 10^5$
• $p$ is prime