시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB30232076.923%

문제

You are given three integers $p$, $k$, $t$, where $p$ is a prime number.

The set $S$ is defined as follows: $S = \{x \mid x \in N, \ 1 \leq x \leq p - 1, \ x \neq k \}$.

Find the sum of the products of all $t$-element subsets of $S$, modulo $p$.

입력

The first line contains three integers $p$, $k$, $t$ ($p$ is a prime number; $1 \leq k \leq p-1$; $1 \leq t \leq p-2$; $p \leq 10^9$).

출력

Print the sum of the products of all $t$-element subsets of $S$, modulo $p$.

예제 입력 1

7 5 3

예제 출력 1

1

예제 입력 2

11 6 7

예제 출력 2

3