시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

bobo is a big fan of linear algebra! He plans to count the number of $k$-dimension subspaces in $\mathbb{F}_q^n$ modulo $p$.

For those who are not familiar with linear algebra:

  • $\mathbb{F}_q$ is the set $\{0, 1, \dots, q - 1\}$, with addition and multiplication modulo $q$ defined on;
  • $\mathbb{F}_q^n$ is the $n$-dimension vector space $\{(x_1, x_2, \dots, x_n) : x_1, x_2, \dots, x_n \in \mathbb{F}_q\}$;
  • A subset $K \subseteq \mathbb{F}_q^n$ is a subspace, if and only if for all $\mathbf{p}, \mathbf{q} \in K$, $\mathbf{p} + \mathbf{q} \in K$;
  • The dimension of subspace $K$ is the cardinality of the maximal independent subset;
  • A subset $\{\mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_k\} \subseteq K$ is called independent if and only if equation $c_1 \cdot \mathbf{p}_1 + c_2 \cdot \mathbf{p}_2 + \dots + c_k \cdot \mathbf{p}_k = 0$ has only solution $c_1 = c_2 = \dots = c_k = 0$.

입력

$4$ integers $q, n, k, p$ ($2 \leq q \leq 10^9, 1 \leq k \leq n \leq 10^9, 2 \leq p \leq 2 \cdot 10^5$).

It is guaranteed that $p$ and $q$ are prime numbers.

출력

A single integer denotes the number of subspaces.

예제 입력 1

2 3 2 100003

예제 출력 1

7