곱 부분집합 계수 세기

시간 제한2초메모리 제한512 MB

요약

최대 500자리 이상인 n과 소수 p가 주어질 때, 기본대칭식 f(n,k)가 p로 나누어지지 않는 k의 개수를 1e9+7로 나눈 나머지로 구하는 문제입니다.

문제

정수 $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$ 로 나눈 나머지를 출력한다.