Harder Staircase Numbers

Time limit2sMemory limit1024 MB

Summary

Count the length-N B-ary staircase numbers (adjacent digits differ by 1, no leading zero) that use every digit from 0 to B-1, modulo M.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

Consider the number 45656. The difference between every pair of adjacent digits is 1. A number like this is called a staircase number.

Sejun wants to know how many B-ary staircase numbers of length $N$ exist in which every one-digit number from 0 to $B-1$ appears as a digit.

Given $N$ , $B$ , and $M$ , write a program that finds the number of B-ary staircase numbers of length $N$ that contain every digit from 0 to $B-1$ , modulo $M$ . (A number cannot start with 0.)

Input

The first line contains natural numbers $N$ , $B$ , and $M$ . ( $1 \le N \le 10^6$ , $2 \le B \le 10^6$ , $10^9 \le M \le 2 \times 10^9$ )

Output

Print the answer on the first line.

Examples4

Example 1
Input
```
14 12 1234567891
```
Expected output
```
16
```
Example 2
Input
```
2000 1800 1000000000
```
Expected output
```
47168488
```
Example 3
Input
```
5 6 2000000000
```
Expected output
```
0
```
Example 4
Input
```
987654 3210 1234567890
```
Expected output
```
245695446
```