题目描述

给一个 $n \times m$ 的 $01$ 矩阵，我们想在每一行删除一个元素，得到一个 $n\times(m-1)$ 的矩阵。其中删除的元素的位置 $(i, a_i)(1 ≤ i ≤ n)$ ，满足 $|a_i−a_{i+1}| ≤ K$ 。

请问最后能得到多少种不同的矩阵。两个矩阵如果删除的元素位置不同，但最后得到的结果相同，我们认为是相同的。由于答案很大，输出答案对 $10^9+7$ 取模的值。

输入格式

第一行，包含三个整数 $n,m,k$ 。 接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 串。

输出格式

输出一个数字，表示答案。

样例 1 输入

5 5 1
00100
10101
00100
01000
11101

样例 1 输出

70

样例 2 输入输出

见下发文件。

数据规模

共十组数据。

测试点 $1,2$ 满足 $n,m ≤ 7$ 。

测试点 $3,4$ 满足 $n,m ≤ 50$ 。

测试点 $5,6$ 满足 $n, m ≤ 500$ 。

测试点 $7$ 满足 $K=m$ 。

对于 $100\%$ 的数据，满足 $n, m ≤ 3000, 1 ≤ k ≤ m$ 。