xreverse

Termopanes şi-a găsit un nou prieten, pe Boolănel, maestrul boolanului în informatică şi vrea să se distreze împreună cu el. Deoarece lui Termopanes îi plac numerele naturale iar lui Boolanel îi plac numerele oglindite, ei decid să calculeze suma numerelor $X$ cu $N$ cifre care nu conţin cifra $0$, cu proprietatea că $X$ modulo $K = 0$ şi $reverse(X)$ modulo $K = 0$. Deoarece suma numerelor poate fi foarte mare, ei vor să găsească suma modulo $M$.

Cerinţă

Ajutaţi-i pe cei doi să calculeze suma din enunţ.

Date de intrare

Fişierul de intrare xreverse.in va conţine o singură linie cu $3$ numere naturale $N$, $K$ şi $M$ cu semnificaţiile din enunţ.

Date de ieșire

Fişierul de ieşire xreverse.out va conţine o singură linie pe care se va afla răspunsul dorit de cei doi.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq K \leq 32$
• $1 \leq M \leq 10 \ 000$
• Pentru $40\%$ din teste $1 \leq N \leq 10 \ 000$ şi $1 \leq K \leq 20$
• Prin $reverse(X)$ se înţelege oglinditul lui $X$, de exemplu: $reverse(1234) = 4321$, $reverse(542) = 245$

Exemplu

xreverse.in

2 9 6613

xreverse.out

495

Explicație

Numerele $X$ cu $2$ cifre cu proprietatea că $X$ modulo $K = 0$ şi $reverse(X) \% K = 0$ sunt: $18, 27, 36, 45, 54, 63, 72, 81, 99$