3502. 不同路径数

给定一个 $n \times m$ 的二维矩阵,其中的每个元素都是一个 $[1,9]$ 之间的正整数。

从矩阵中的任意位置出发,每次可以沿上下左右四个方向前进一步,走过的位置可以重复走。

走了 $k$ 次后,经过的元素会构成一个 $(k+1)$ 位数。

请求出一共可以走出多少个不同的 $(k+1)$ 位数。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行,每行包含 $m$ 个空格隔开的整数,表示给定矩阵。

输出格式

输出一个整数,表示可以走出的不同 $(k+1)$ 位数的个数。

数据范围

对于 $30\%$ 的数据, $1 \le n, m \le 2, 0 \le k \le 2$
对于 $100\%$ 的数据,$1 \le n, m \le 5, 0 \le k \le 5, m \times n > 1$

输入样例:

3 3 2
1 1 1
1 1 1
2 1 1

输出样例:

5

样例解释

一共有 $5$ 种可能的 $3$ 位数:

111
112
121
211
212