题目描述

你正在开车去机场接朋友，但朋友的航班晚点了。你准确知道还需要等待多少分钟，希望在这段时间里开车在城市中兜一圈，并且恰好在指定时刻到达机场。

城市共有 $n$ 个路口，编号为 $0,1,\ldots,n-1$。道路信息由一个 $n\times n$ 的字符矩阵 adj 给出：

• adj[i][j]='.' 表示不存在从路口 $i$ 到路口 $j$ 的道路；
• adj[i][j] 为 '1' 到 '5' 时，表示存在一条从 $i$ 到 $j$ 的有向道路，通行时间等于该数字所表示的分钟数。

道路不一定是双向的；即使两个方向都存在道路，通行时间也可能不同。

你在时刻 $0$ 位于路口 start，机场位于路口 finish。求经过恰好 time 分钟后到达机场的不同路线数量。答案对 $1000003$ 取模。

输入格式

第一行输入五个整数 $n,m,start,finish,time$。

其中 $n$ 表示矩阵行数，$m$ 表示每一行的字符数；本题数据中始终有 $m=n$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示矩阵 adj。

输出格式

输出一个整数，表示恰好经过 time 分钟从 start 到达 finish 的路线数量，对 $1000003$ 取模后的结果。

数据范围

• $1\le n=m\le 10$；
• adj[i][j] 只可能是 . 或字符 1～5；
• adj[i][i]='.'；
• $0\le start,finish<n$；
• $1\le time\le 10^9$。

样例

输入

3 3 0 2 5
.12
2.1
12.

输出

8