Sum of Products of Permutations

Consider a sequence (a_1, a_2, \dots, a_n). The sequence is said to be valid if and only if:

• Each \(a_i\) is an integer in the range \([1, k]\).
• All \(a_i\) are distinct.

The value of a sequence is defined as the product of its elements: \(a_1 \times a_2 \times \dots \times a_n\).

Your task is to compute the sum of the values of all different valid sequences modulo \(p\). Note that two sequences are considered different if they differ in at least one position.

inputFormat

The input consists of a single line containing three space-separated integers: (n), (k), and (p), where (n) is the length of the sequence, (k) is the upper bound of the range, and (p) is the modulus.

outputFormat

Output a single integer which is the sum of the products of all valid sequences modulo (p).

sample

2 3 100

22

</p>