Un palindrom este un număr care citit de la dreapta la stânga cât şi de la stânga la dreapta este acelaşi. De exemplu, 12321 sau 1551 sunt palindromuri. Un bipalindrom este un număr constituit din două palindromuri având acelaşi număr de cifre. Primul dintre cele două palindromuri nu poate să înceapă cu cifra 0. De exemplu 121050 este un bipalindrom (fiind format din două palindromuri cu 3 cifre 121 şi 050), dar 2222444 nu este bipalindrom (este format din două palindromuri, dar care nu au acelaşi număr de cifre), nici 010232 (pentru că primul palindrom începe cu 0).

Cerinţă

Date fiind două numere naturale N şi M, să se determine câte bipalindromuri de N cifre divizibile cu M există.

Date de intrare

Fişierul de intrare bipal.in conţine pe prima linie numerele natural N şi M separate prin spaţiu.

Date de ieşire

Fişierul de ieşire bipal.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de bipalindromuri de N cifre divizibile cu M.

Restricţii

• 2 ≤ N ≤ 20, N par
• 1 ≤ M ≤ 1 000 000

Exemple

bipal.in	bipal.out	Explicatie
2 10	9	Cele 9 bipalindromuri de două cifre divizibile cu 10 sunt 10, 20, 30, 40, 50, 60, 70, 80, 90

bipal.in	bipal.out	Explicatie
6 12345	1	Singurul bipalindrom de 6 cifre divizibil cu 12345 este 555525

prof. Marinel Serban

Liceul de Informatica "Grigore Moisil" Iasi

marinel_serban@yahoo.com