矩阵删除

题目描述 给一个� × �的 01 矩阵，我们想在每一行删除一个元素，得到一个� × (� − 1)的 矩阵。其中删除的元素的位置(�, �� )(1 ≤ � ≤ �)，满足|�� − ��+1 | ≤ �。

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

输入格式 第一行，包含三个整数�, �, �。接下来�行，每行一个长度为�的 01 串。

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

样例输入 1 5 5 1 00100 10101 00100 01000 11101

样例输出 1 70

样例输入输出 2 见下发文件。

数据规模 共十组数据。

测试点 1,2 满足�, � ≤ 7。

测试点 3,4 满足�, � ≤ 50。

测试点 5,6 满足�, � ≤ 500。

测试点 7 满足� = �。

对于 100%的数据，满足�, � ≤ 3000,1 ≤ � ≤ �。