더 어려운 계단 수

45656이라는 수를 보자. 이 수는 인접한 모든 자릿수의 차이가 1이다. 이런 수를 계단 수라고 한다.

오늘도 세준이는 0부터 $B-1$까지 모든 한 자리 숫자가 자릿수로 등장하면서 길이가 $N$인 $B$진법 계단 수가 몇 개 있는지 궁금해졌다.

$N$, $B$, $M$이 주어질 때, 길이가 $N$이면서 0부터 $B-1$까지 모든 숫자가 등장하는 $B$진법 계단 수의 개수를 $M$으로 나눈 나머지를 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

첫째 줄에 자연수 $N$, $B$, $M$이 주어진다. ($1 \le N \le 10^6$, $2 \le B \le 10^6$, $10^9 \le M \le 2 \times 10^9$)

첫째 줄에 정답을 출력한다.