Except One

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

요약

소수 p와 제외할 값 k가 주어질 때, {1,...,p-1}에서 k를 뺀 집합의 모든 t원소 부분집합의 곱의 합을 p로 나눈 나머지를 구한다.

문제

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