Pedro has $$$n$$$ stones forming a line and wants to paint them with $$$c$$$ different colors in such a way that there are no $$$k \geq 2$$$ consecutive stones of the same color.
He wants to know in how many ways he can paint the stones.
The input starts with a line with an integer $$$t$$$ indicating the number of cases.
Each case consists of four integers $$$n$$$, $$$c$$$, $$$k$$$, and $$$p$$$. Where $$$p$$$ is a prime number with $$$10^8 \leq p \leq 10^9$$$.
The answer can be very large, write the result modulo $$$p$$$.
For each case, write a line with the result modulo $$$p$$$.
$$$1 \leq t \leq 100$$$
$$$2 \leq k \leq n \leq 10^6$$$
$$$1 \leq c \leq 10^9$$$
$$$10^8 \leq p \leq 10^9$$$
11 Points: $$$n,c \leq 10$$$ and $$$c^n \leq 10^4$$$
13 Points: $$$n,c \leq 100$$$
19 Points: $$$n \leq 1000$$$
12 Points: $$$n \leq 50000$$$ and $$$c \leq 10$$$
7 Points: $$$n \leq 50000$$$ and $$$c \leq 100$$$
38 Points: no restrictions
5 7 3 6 100000007 10 2 5 100000037 100 100 50 100000039 1000 123456789 345 100000049 1000000 987654321 123456 100000073
2172 802 62324845 55895361 81968913
