Se numește graf scară de ordin $n$ un graf neorientat cu $2n$ vârfuri, etichetate de la $1$ la $2n$, și $3n-2$ muchii, definite astfel: $[2k - 1, 2k]$ pentru $1 \le k \le n$ și $[k, k + 2]$ pentru $1 \le k \le 2n - 2$.

Cerință

Pentru $n$ și $b$ valori date, se cere să se calculeze numărul arborilor parțiali pentru un graf scară de ordin $n$ și să se afișeze rezultatul în baza de numerație $b$.

Date de intrare

Fișierul de intrare grafscara.in conține pe prima linie, separate printr-un spațiu, numerele naturale $n$ și $b$ cu semnificația de mai sus.

Date de ieșire

Fișierul de ieșire grafscara.out va conține pe prima linie valoarea cerută.

Restricții și precizări

• $1 \le n \le 50\ 000$
• $2 \le b \le 10$
• Se garantează că numărul de cifre al rezultatului nu depășește $100\ 000$.

Exemplul 1

grafscara.in

3 10

grafscara.out

15

Exemplul 2

grafscara.in

10 2

grafscara.out

100100111100010100

Exemplul 3

grafscara.in

40 10

grafscara.out

21792711940069192045616

Exemplul 4

grafscara.in

50 8

grafscara.out

11164406761045535232603005157144