33384번 - Except One 다국어

문제

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$.

제한

힌트