Substring Pairs

Sunuke came up with a pun called "s de t t", but forgot it. Sunuke remembers the following.

• The length of s is N.
• The length of t is M.
• t is a substring of s. (There is a part of consecutive M characters of s that matches t.)

Divide the number of possible combinations as (s, t) by 1,000,000,007 to find the remainder. However, it is assumed that there are A types of characters.

Constraints

• 1 ≤ N ≤ 200
• 1 ≤ M ≤ 50
• M ≤ N
• 1 ≤ A ≤ 1000

Input

N M A

Output

Divide the number of character string pairs (s, t) that satisfy the condition by 1,000,000,007 and output the remainder.

Examples

Input

3 2 2

Output

14

Input

200 50 1000

Output

678200960

inputFormat

Input

N M A

outputFormat

Output

Divide the number of character string pairs (s, t) that satisfy the condition by 1,000,000,007 and output the remainder.

Examples

Input

3 2 2

Output

14

Input

200 50 1000

Output

678200960

样例

3 2 2

14