你有一个 n 行 m 列的方格，每个格子都填有 0123456789+-* 中的某一个字符。 你从左上角出发，每次可以向右或向下走一格，直到走到右下角。有多少种走法，把经过的所有字符按经过顺序排成一排可以得到一个合法的算式，该算式的得数是 k 的倍数？输出对 10⁹ + 7 求余。 保证左上角、右下角的格子都是数字。称一个算式合法当且仅当没有两个连续的运算符。我们允许数字有前导零，并且此时和 C++ 规则不同，仍把数字看作十进制数。
输入格式
本题输入有多组测试数据。输入的第一行有一个正整数 T（1 ≤ T ≤ 5），表示数据组数。之后的每一组数据格式如下： 输入的第一行有三个正整数 n, m, k（2 ≤ n, m ≤ 100，2 ≤ k ≤ 20），分别表示方格的行数和列数，以及得数的要求。 之后 n 行，每行有 m 个字符，表示这个方格。