题目背景

洛谷的试题为民间回忆版，仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。

本题测试数据较大，加载需要一定时间。原题内存限制为 64MB，为了鼓励更多做法，在洛谷上提供了 512MB 的内存限制。

题目描述

给定一个 $h \times w$ 的网格。机器人从左上角 $(1, 1)$ 出发，每次只能向右或向下移动一格，最终到达右下角 $(h, w)$。

网格中的每个单元格 $(i, j)$ 都有一个正整数值 $a_{i,j}$。一条路径的“乘积值”定义为该路径经过的所有单元格（包括起点和终点）的 $a_{i,j}$ 值的乘积。

你需要计算从 $(1, 1)$ 到 $(h, w)$ 且“乘积值”为 $11$ 的倍数的路径的总数。由于答案可能非常大，请将结果对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $h, w$，分别代表网格的高度和宽度。

接下来 $h$ 行，每行包含 $w$ 个整数，描述了整个网格。第 $i$ 行的第 $j$ 个整数代表 $a_{i,j}$ 的值。

输出格式

输出一个整数，表示符合题目要求的路径的数量，结果对 $10^9 + 7$ 取模。

3 3
10 21 30
14 11 6
3 6 9

4

提示

数据范围与约定

对于 100% 的数据，满足：$1 \le h, w \le 10^7$，$1 \le h \times w \le 10^7$，$1 \le a_{i,j} \le 10^9$。