题目描述

牛牛家的密码锁，输入密码的位置是$\red{N}$行$\red{M }$列的，每个位置都是一个不同字母、 数字或符号的按钮。

牛牛发现，每次点击一个按钮，都会发出声音。可以通过辨识前后两个声音的间 隔，来判断前后两个按钮的最大距离。

牛牛把听到的声音间隔分析了一下，计算出了每个位置离前一个按钮的最大距离。 距离是指曼哈顿距离，即上下左右相邻的按钮距离为$\red{1}$。当然，有时候输入密码 的人会停顿非常久，所以让牛牛计算出来的距离非常大，甚至比最远的两个按钮 还大，但这只是可能的最大距离，计算时应该予以考虑。

已知密码长度为$\red{t ，}$牛牛不知道密码输入的起始位置，但牛牛想知道通过这样的 计算，有多少种可能的密码，结果对$\red{10^9 + 7}$取模。

输入格式

第一行输入三个整数$\red{N, M,t，}$表示密码锁的按钮行列数，和密码长度。

第二行输入$\red{t - 1}$个整数，第$\red{i}$个整数 $\red{ai}$表示按下的第$\red{i + 1}$个位置和第$\red{i}$个位置的距 离。

对于 $\red{20\%}$的数据有$\red{n = 1}$或$\red{m = 1}$。

另有 $\red{20\%}$的数据有$\red{1 ≤}$ $\red{n, m ≤}$ $\red{3}$。

对于 $\red{60\%}$的数据有$\red{1 ≤}$ $\red{n, m ≤}$ $\red{10}$。

对于 $\red{100\%}$的数据有$\red{1 ≤}$ $\red{n, m ≤}$ $\red{25, 2 ≤}$ $\red{t ≤}$ $\red{1000,0 ≤}$ $\red{ai ≤}$ $\red{10^9}$。

输出格式

一行输出一个整数，即密码可能的数量。

样例

输入样例1

1 3 2
1

输出样例1

7

输入样例2

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

输出样例2

363792

提示

样例 $\red{1 }$说明

开始位置可能是 $\red{(1,1),(1,2),(1,3)}$。

如果第一个按钮和第二个按钮距离为 $\red{0 ，}$则密码为 $\red{(1,1)->(1,1),(1,2)->(1,2),(1,3)->(1,3)，}$有三种不同的密码。

如果第一个按钮和第二个按钮距离为 $\red{1 ，}$则密码为 $\red{(1,1)->(1,2),(1,2)->(1,1),(1,2)->(1,3),(1,3)->(1,2)，}$有四种不同的密码。 共计有 $\red{7 }$种不同的密码。

样例 $\red{2 }$说明

该样例为大样例。