棋盤遊戲


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

有一天,有小美在搭電車時,一位奇怪的大叔對他說:「這裡有一個\(n \times m\)的棋盤,每一格上有一個數字\(A_{i,j}\),代表你在\((i,j)\)這格時可以移動到曼哈頓距離小於等於\(A_{i,j}\)的位置。」小美害怕的回答:「什麼是曼哈頓距離?」親切的大叔解釋:「\((x,y)\)到\((i,j)\)的曼哈頓距離就是\(|x-i|+|y-j|\)」大叔又說:「如果你能在\(t\)步內從左上角\((0,0)\)移動到右下角\((n-1,m-1)\),那麼我就給你1000元」這時,一旁的奇異博士說:「你有\(X\)種移動方法數能獲得1000元」

請你求出\(X\)。此外,為了避免奇異博士舌頭打結,\(X\)請\(mod\) \(10^9+7\)

Input

第一行有三個正整數,分別是\(n,m,t\) \((1≤n,m≤10)\)

接下來有\(n\)行,每行有\(m\)個整數,代表棋盤上的數字\(A_{i,j}\) \((1≤A_{i,j}≤10,但A_{n-1,m-1}=0)\)

Output

輸出\(X\),答案請\(mod\) \(10^9+7\)

Constraints

第\(1\)組測資,\(t≤10\) \((25\%)\)

第\(2\)組測資,\(t≤2 \times 10^5\) \((75\%)\)

Sample Input 1
3 3 5
1 1 1
1 1 1
1 1 0
Sample Output 1
6
Sample Input 2
5 5 10
2 4 5 5 3
2 3 2 1 4
5 5 5 5 1
1 2 4 4 3
5 1 1 3 0
Sample Output 2
568101491
Notes

移動時必須離開所處格子,即不能移動到現在的格子上。另外,到達終點後就必須結算,計為一種方法。


Comments

There are no comments at the moment.