You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一座机房被划分成 $N$ 行 $M$ 列的网格，每个格子里都有一个需要巡检的模块。维护机器人要连续巡检 $t$ 个模块，但它的起点没有被记录下来。

系统只保留了相邻两次巡检之间的移动约束：第 $i$ 次巡检后到第 $i+1$ 次巡检前，机器人移动的曼哈顿距离不能超过 $a_i$。

两个格子 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的曼哈顿距离为：

机器人可以原地不动。若 $a_i$ 大于网格中最远两格的距离，则这一轮约束不会额外限制移动。

请计算一共有多少条可能的巡检路线。答案可能很大，请对 $10^9+7$ 取模。

输入格式

在文件 patrolroutes.in 中读入。

第一行输入三个整数 $N,M,t$，表示网格行数、列数和路线长度。

第二行输入 $t-1$ 个整数 $a_1,a_2,\ldots,a_{t-1}$，其中 $a_i$ 表示第 $i$ 个格子到第 $i+1$ 个格子的最大允许曼哈顿距离。

输出格式

在文件 patrolroutes.out 中输出。

输出一行一个整数，表示可能路线数量对 $10^9+7$ 取模后的结果。

样例

样例输入 #1

1 3 2
1

样例输出 #1

7

样例输入 #2

4 4 10
2 0 0 0 1 0 3 1 3

样例输出 #2

363792

数据范围

• 对于 $20\%$ 的数据，满足 $N=1$ 或 $M=1$。
• 对于另外 $20\%$ 的数据，满足 $1 \le N,M \le 3$。
• 对于另外 $60\%$ 的数据，满足 $1 \le N,M \le 10$。
• 对于 $100\%$ 的数据，满足 $1 \le N,M \le 25$，$2 \le t \le 1000$，$0 \le a_i \le 10^9$。