407276: GYM102741 D Combo Counter

Sally has had some downtime recently and so to keep from boredom, she's been playing a lot of Super Smash Bros Ultimate. She has made it her goal to be the best player in the world and while watching some of the current best players, she found a special type of move combo called a kill-confirm which guarantees that you will be able to take one of your opponent's stock. In order for a combo to be a kill-confirm, she realized that the combo must be $$$n$$$ moves long and every 'sub-combo' of $$$p$$$ moves must be a palindrome. A 'sub-combo' of size $$$p$$$ is $$$p$$$ consecutive moves in the original combo and for a 'sub-combo' to be a palindrome, the list of moves must be the same when read forward and backward. For example, if the list of $$$p$$$ moves is 'Up, Down, Down, Up' this is a palindrome.

Armed with this information, Sally wants to figure out the number of distinct kill-confirm combos for a specific character in the game that has $$$m$$$ distinct moves. This number can be quite large so return the quantity modulo $$$10^9 + 7$$$.

There will be one line of input which contains $$$3$$$ space-separated integers: $$$n$$$, $$$p$$$, and $$$m$$$ ($$$1 \leq n,p,m \leq 2500$$$ and $$$p \leq n$$$).

Output a single integer, the number of possible combos that fit the desired scheme modulo $$$10^9 + 7$$$.

1 1 1

1

5 4 2

2

In the first example, there is only one move and the length of the combo is one so the only combo possible is that move itself. In the second example, there are two moves (call them $$$w$$$ and $$$s$$$ for example), and the only way for a combo to be of length $$$5$$$ with all 'sub-combos' of length $$$4$$$ being palindromes is if the combo is $$$wwwww$$$ or $$$sssss$$$.