有一天，有小美在搭電車時，一位奇怪的大叔對他說：「這裡有一個\(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

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