Fişierul intrare/ieşire:	xreverse.in, xreverse.out	Sursă	Lot Cluj 2009, Baraj 5
Autor	Catalin-Stefan Tiseanu, Mircea Dima	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	1.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 ≤ N ≤ 1 000 000
• 1 ≤ K ≤ 32
• 1 ≤ M ≤ 10 000
• Pentru 40% din teste 1 ≤ N ≤ 10 000 şi 1 ≤ K ≤ 20.
• Prin reverse(X) se înţelege oglinditul lui X. De exemplu, reverse(1234) = 4321, reverse(542) = 245.

Exemplu

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.

Cum se trimit solutii?