Migrated from Lutece 1740 字符串匹配

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

字符集大小为$m$，给定一个长为$k$的字符串$s$，求出所有长为$1$到$n$的串中，不包含子串$s$的共有几个?

Input

输入的第一行包含三个整数$m,k,n.(1 \leq m,k,n \leq 10^5)$

接下来一行包含$k$个整数，表示串$s( 1 \leq s_i \leq m)$.

Output

输出$n$行表示答案，因为答案可能较大，你只需输出其在$\text{mod } 10^9+7$意义下的值

Samples

5 5 10
1 2 1 2 1

5
25
125
625
3124
15615
78051
390135
1950075
9747376

Resources

Prepared by xiper