Statement

Yourein君は夢で神に会いました。
神は$M$個の相異なる0以上9以下の整数からなる集合$a = \lbrace{a_1, \hspace{0.2em} a_2, \hspace{0.2em} ..., \hspace{0.2em} a_M\rbrace}$をYourein君に手渡しこう言いました。
「あなたは今日条件を満たす数列を持つと幸せになれる」

神が示した条件は以下の通りでした

• 数列の項はすべて集合$a$の要素である。
• 数列の初項が$0$でない。
• その数列は初項から末項までをつなげて10進数整数としたときに$K$の倍数である。(「この条件の例は入力例1や3を参照すること」)

Yourein君は神のお告げを信じそのような数列を紙に書いて1日持ち歩くことにしました。

Yourein君は数列の長さが長いほうがより幸せになれると考えており、紙には最大で$N$項の数列を書くスペースがあります。そのため、項数が$N$項以下かつ条件をすべて満たす数列のうち最も長いものを紙に書こうと考えています。

Yourein君が最終的に紙に書き込んだ数列の長さを教えて下さい。
ただし、どのようにしても条件を満たす数列を作ることができない場合は-1を出力してください

Constraints

• $1 \le N, K \le 3 \times 10^3$
• $1 \le M \le 10$
• $a_i \in \lbrace{x | 0 \le x \le 9, x \in \Z\rbrace}$
• $|a| = M$
• 入力はすべて整数

Input

1行目に$N, K, M$がスペースを開けて与えられる 2行目に$a_1, a_2, ... \ , a_M$が与えられる。

Output

問題文の条件に合うような数列のうち最も項数が多いものの項数を出力せよ。ただし、そのような数列を作ることができない場合は-1を出力せよ。

Examples

Example1

3 13 2
1 7

3

作れる数列は$1, 7, 11, 17, 71, 77, 111, 117, 171, 177, 711, 717, 771, 777$です。 この中で13の倍数となるものとしては$117$があります。
その長さは3なので3を出力します。

Example2

10 6 2
1 2

10

Example3

7 18 1
4

-1

実は$444444444$が$18$の倍数です。このように求める数列が構成可能な場合でも書ききるスペースがなければ答えが$-1$となることに気をつけてください。

Example4

125 2 1
3

-1

$3$をいくつ並べてもそれらはすべて$3$の倍数です。また$1$の位も偶数にはならないので、どのようにしても条件を満たす数列を構成することができません。