Rezolvare PBinfo #4511

Se citesc numerele naturale n şi k şi cifrele nenule distincte c[1], c[2], …, c[n].

Cerința

Să se determine câte numere de k cifre formate doar cu cifrele c[1], c[2], …, c[n] sunt divizibile cu 9. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 666013.

Date de intrare

Fișierul de intrare divnoua.in conține pe prima linie numerele naturale n şi k separate printr-un spațiu, iar linia a doua cele n cifre distincte c[1], c[2], …, c[n], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire divnoua.out va conține o singură linie pe care va fi scris un singur număr natural, reprezentând numărul (modulo 666013) de numere de k cifre formate doar cu cifrele c[1], c[2], …, c[n] și divizibile cu 9.

Restricții și precizări

• 1 ≤ n ≤ 9
• 2 ≤ k ≤ 100.000
• 1 ≤ c[1], c[2], ..., c[n] ≤ 9

Exemplu:

divnoua.in

3 2
3 6 9

divnoua.out

3

Explicație

Numerele cu două cifre formate cu cifrele 3, 6 și 9 sunt 36, 63 și 99.