Substring Pairs

시간 제한1초메모리 제한512 MB

요약

알파벳 크기가 A일 때 길이 N인 문자열 s와 길이 M인 문자열 t의 쌍 중 t가 s의 부분 문자열인 것의 개수를 10^9+7로 나눈 나머지를 구합니다.

문제

Snuke came up with an integersing pair of strings (s, t), but forgot it. He remembers the following information:

The length of s is exactly N.
The length of t is exactly M.
t is a substring of s. (You can choose consecutive M characters from s that are the same as t.)

Compute the number of possible pairs of strings (s, t), modulo 109 + 7. Assume that the size of the alphabet is A.

First line of the input consists of three integers N, M and A (1 ≤ N ≤ 200, 1 ≤ M ≤ 50, M ≤ N, 1 ≤ A ≤ 1000)

Print the number of pairs of strings (s, t) that satisfy the conditions above, modulo 109 + 7.