In the Grand Palace of the Fruits Kingdom, there is a long ornamental chain consisting of $$$n$$$ decorative beads, numbered from $$$1$$$ to $$$n$$$ from left to right. Initially, all beads are uncolored.

To celebrate the upcoming Fruits' Festival, the King has invited $$$m$$$ jesters to color the beads. The jesters are numbered from $$$1$$$ to $$$m$$$. The coloring process runs for $$$m$$$ turns, in the $$$i$$$-th turn, the $$$i$$$-th jester must paint a contiguous segment of the beads with color $$$i$$$. However, the jesters do not view themselves as ordinary performers, instead, all of them are strictly adhered to the sacred number $$$k$$$, insisting that each jester's stroke must cover exactly $$$k$$$ beads. It follows that each jester has $$$n - k + 1$$$ choices in their turn.

Note that painting a colored bead will overwrite its original color.

Since the jesters are paid, the king does not want to see uncolored beads at the ceremony. Thus, all $$$n$$$ beads must be painted by at least one of the jesters by the end of the process.

Please help the King calculate the total number of possible final states of the beads that satisfy the condition above. Two final states are considered different if and only if there exists a bead $$$i$$$ that has a different color in the two states. Since the answer could be large, output it modulo $$$p$$$.