19141번 - Subspace 다국어

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.