3677: 密码锁(第六轮03)
题目描述
牛牛家的密码锁，输入密码的位置是N行M 列的， 每个位置都是一个不同字母、 数字或符号的按钮。
牛牛发现，每次点击一个按钮，都会发出声音。可以通过辨识前后两个声音的间 隔，来判断前后两个按钮的最大距离。
牛牛把听到的声音间隔分析了一下，计算出了每个位置离前一个按钮的最大距离。 距离是指曼哈顿距离， 即上下左右相邻的按钮距离为1。当然，有时候输入密码 的人会停顿非常久，所以让牛牛计算出来的距离非常大，甚至比最远的两个按钮 还大，但这只是可能的最大距离，计算时应该予以考虑。
已知密码长度为t ，牛牛不知道密码输入的起始位置，但牛牛想知道通过这样的 计算，有多少种可能的密码。结果对109 + 7取模。
输入
第一行输入三个整数N, M, t，表示密码锁的按钮行列数，和密码长度。
第二行输入t − 1个整数， 第i个整数 ai 表示按下的第i + 1个位置和第i个位置的距 离。
对于 20%的数据有n = 1或m = 1。 另有 20%的数据有1 ≤ n, m ≤ 3 。 对于 60%的数据有1 ≤ n, m ≤ 10。
对于 100%的数据有1 ≤ n, m ≤ 25, 2 ≤ t ≤ 1000,0 ≤ ai ≤ 109 。
输出
样例输入 复制
1 3 2
1样例输出 复制
7提示
【样例 1 输入】
1 3 2
1
【样例 1 输出】
7
【样例 1 说明】
开始位置可能是 (1,1),(1,2),(1,3)。
如 果 第 一 个 按 钮 和 第 二 个 按 钮 距 离 为 0 ， 则 密 码 为 (1,1)->(1,1),(1,2)->(1,2),(1,3)->(1,3)，有三种不同的密码。
如 果 第 一 个 按 钮 和 第 二 个 按 钮 距 离 为 1 ， 则 密 码 为 (1,1)->(1,2),(1,2)->(1,1),(1,2)->(1,3),(1,3)->(1,2)，有四种不同的密码。
共计有 7 种不同的密码。
【样例 2 输入】
4 4 10
2 0 0 0 1 0 3 1 3
【样例 2 输出】
363792
【样例 2 说明】
该样例为大样例。
对于 20%的数据有n = 1或m = 1。
另有 20%的数据有1 ≤ n, m ≤ 3 。
对于 60%的数据有1 ≤ n, m ≤ 10。
对于 100%的数据有1 ≤ n, m ≤ 25, 2 ≤ t ≤ 1000,0 ≤ ai ≤ 10^9 。