sirdivk

Cu ajutorul a trei cifre date $a$, $b$, $c$, unde $a > 0$, se construieşte următorul şir de numere: $\overline{\text{a}}$, $\overline{\text{ab}}$, $\overline{\text{abc}}$, $\overline{\text{abca}}$, $\overline{\text{abcab}}$, $\overline{\text{abcabc}}$, $\dots$.

De exemplu, pentru $a=1$, $b=3$, $c=7$, putem construi şirul: $1$, $13$, $137$, $1371$, $13713$, $137137$, $1371371$, $13713713$, $\dots$.

Cerință

Scrieţi un program care determină câte numere divizibile cu $k$ se găsesc în primii $n$ termeni ai şirului dat.

Date de intrare

Fișierul de intrare sirdivk.in conține pe prima linie numerele $a$, $b$, $c$, $n$, $k$.

Date de ieșire

Fișierul de ieșire sirdivk.out conţine o singură linie pe care este scris numărul $nr$ de numere divizibile cu $k$ aflate printre primii $n$ termeni ai şirului dat.

Restricții și precizări

• $1 < n < 1 \ 000$
• $2 \leq k < 32 \ 000$
• $1 \leq a \leq 9$
• $0 \leq b,c \leq 9$

Exemplu

sirdivk.in

7 2 1 8 3 

sirdivk.out

2

Explicație

Printre primii $8$ termeni ai şirului: $7$, $72$, $721$, $7217$, $72172$, $721721$, $7217217$, $72172172$, $\dots$ există doi termeni divizibili cu $3$.