题目描述

给出 $m$ 个模板字符串。对于一个字符串，我们可以把这个字符串切成若干段；如果切完后有 $t$ 段分别和某个模板串相等，那么这种切割方式的价值为 $t$。定义一个字符串的价值为所有切割方式的价值的最大值。

板板想知道，有多少长度为 $2n$ 的数字字符串，满足字符串的前 $n$ 位和后 $n$ 位相等，且价值不超过 $k$。

输入格式

输入的第一行包含三个整数 $n$、$m$、$k$；

接下来 $m$ 行，每行一个数字字符串，表示每个模板串。

输出格式

输出板板想求的字符串个数模 $1000000007$。

2 2 0
23
41

96

样例解释 1

4 个不合法的字符串为 23|23、3|23|2、41|41、1|41|4。每个数字中的竖线表示一种价值超过 $0$ 的切割方案。

5 2 3
23
41

99880

子任务

子任务一（6 分）：$n\le 5, m\le 10$；

子任务二（9 分）：每个模板串长度为 $1$；

子任务三（18 分）：$n\le 20,m\le 50$；

子任务四（15 分）：$k = 0$；

子任务五（13 分）：$k = 1$；

子任务六（19 分）：$k = 2$；

子任务七（20 分）：无特殊限制。

对于所有数据，$n\le 100$、$m\le 200$、$k\le 3$、每个模板串长度不超过 $5$。