부분공간

bobo는 선형대수의 열성 팬이다. 그는 $\mathbb{F}_q^n$에서 $k$차원 부분공간의 개수를 $p$로 나눈 나머지로 세려고 한다.

선형대수에 익숙하지 않은 사람을 위해 정의를 적는다.

• $\mathbb{F}_q$는 덧셈과 곱셈을 $q$로 나눈 나머지로 정의한 집합 $\{0, 1, \dots, q - 1\}$이다;
• $\mathbb{F}_q^n$은 $n$차원 벡터 공간 $\{(x_1, x_2, \dots, x_n) : x_1, x_2, \dots, x_n \in \mathbb{F}_q\}$이다;
• 부분집합 $K \subseteq \mathbb{F}_q^n$이 모든 $\mathbf{p}, \mathbf{q} \in K$에 대해 $\mathbf{p} + \mathbf{q} \in K$를 만족하면, 그리고 그때에만 $K$는 부분공간이다;
• 부분공간 $K$의 차원은 $K$의 가장 큰 독립 부분집합의 원소 개수이다;
• 부분집합 $\{\mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_k\} \subseteq K$는 $c_1 \cdot \mathbf{p}_1 + c_2 \cdot \mathbf{p}_2 + \dots + c_k \cdot \mathbf{p}_k = 0$의 해가 $c_1 = c_2 = \dots = c_k = 0$뿐일 때 독립이라고 한다.

네 정수 $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$). $p$와 $q$가 소수임이 보장된다.

부분공간의 개수를 나타내는 정수 하나를 출력한다.