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 ≤ 100000
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.