严格下降的到达路线数

难度：T2

【知识点：记忆化搜索】

前置知识：函数、递归、数组、完整状态与无环依赖。

题目描述

给定高度矩阵和起点、终点。每次移动到上下左右相邻且高度严格更低的格子，求从起点到终点的不同路线数。到终点立即结束。经过的坐标序列不同就是不同路线。起终点相同时，零步路线算一种。相等高度不能移动，不能斜走。

输入格式

第一行 $n,m$。接下来 $n$ 行，每行 $m$ 个高度。 最后一行 $s_r,s_c,t_r,t_c$，依次为起点行列与终点行列，坐标从 $1$ 开始。

输出格式

一行路线数量，不取模；没有路线输出 0。

样例输入

2 2
9 8
6 4
1 1 2 2

样例输出

2

样例解释

两条路线分别向右再向下、向下再向右，均从左上到右下。

数据范围

$1\le n,m\le6$，起终点坐标合法。 高度为 $0$ 到 $10^9$ 的整数。