하나를 제외하고

시간 제한1초메모리 제한2048 MB

요약

소수 p와 정수 k, t가 주어질 때, 1부터 p-1까지의 수에서 k를 뺀 집합의 모든 t원소 부분집합 곱의 합을 p로 나눈 나머지를 구합니다.

문제

세 정수 $p$ , $k$ , $t$ 가 주어진다. 여기서 $p$ 는 소수이다.

집합 $S$ 는 다음과 같이 정의한다: $S = \{x \mid x \in \mathbb{N}, \ 1 \leq x \leq p - 1, \ x \neq k \}$ .

$S$ 의 모든 $t$ 개 원소 부분집합에 대해 원소들의 곱을 구하고, 그 합을 $p$ 로 나눈 나머지를 구하라.

첫째 줄에 세 정수 $p$ , $k$ , $t$ 가 주어진다 ( $p$ 는 소수이다; $1 \leq k \leq p-1$ ; $1 \leq t \leq p-2$ ; $p \leq 10^9$ ).

$S$ 의 모든 $t$ 개 원소 부분집합의 곱의 합을 $p$ 로 나눈 나머지를 출력한다.