竹鼠，宝藏与故事
题号：NC276336
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,收工回店，清楚开始仔细研究这些图形。竹鼠忽开口言：“蒙君饱腹之恩，吾等当助君得宝。“言罢，摇身一变，化作数道白光没入轴中，清楚定睛一看，方觉卷轴乃一微型迷宫也。 
\,\,\,\,\,\,\,\,\,\,迷宫曲折，然竹鼠数量众多、各行其道，不消片刻，白光再现，宝物尽数被带出。
\,\,\,\,\,\,\,\,\,\,n \times m 的迷宫中有无数珍宝，左上角为迷宫的起点，右下角为终点。我们使用数字 -1 标记这个格子无法被通过；使用自然数来代表这个格子上宝藏的珍惜程度（数字为 0 即代表该位置上不存在宝藏）。现在，你需要找出所有从起点出发、直达终点的简单路径，输出这些路径上的宝藏珍惜度之和。
\,\,\,\,\,\,\,\,\,\,请注意，每一份宝藏只能被取一次。若某一条路径已经取走了 A 处的宝藏，那么当另一条路径也经过 A 处时，将无法再取。
\,\,\,\,\,\,\,\,\,\,这里的简单路径是指从起点出发，每一步都可以选择上下左右任意一个方向行走（前提是目标格可以通行），且路径上的每一个格子至多只经过一次，最终到达终点的路径。

输入描述:

\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n 和 m\ (2 \le n,m \le 1000) ，代表迷宫的长和宽。
\,\,\,\,\,\,\,\,\,\,此后 n 行，每行输入 m 个数字 a_1,a_2,\dots,a_m\ (-1 \le a_i \le 10^9) ，表示迷宫中这一行的情况，其中 -1 表示该单元格无法通行。第一行第一个字符必定不为 -1 ，代表起点；最后一行最后一个字符必定不为 -1 ，代表终点。

输出描述:

\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表所有直达终点的路径上的宝藏数量。
示例1

输入

复制 
3 4
0 1 -1 9
0 -1 1 -1
0 0 0 0

输出

复制 
0

说明

\,\,\,\,\,\,\,\,\,\,如下图所示，只有唯一的路径可以直达终点，而这条路径上没有宝藏，所以答案为 0 。
\,\,\,\,\,\,\,\,\,\,
示例2

输入

复制 
4 4
0 1 0 3
0 -1 1 0
0 -1 -1 0
2 -1 0 0

输出

复制 
5

说明

\,\,\,\,\,\,\,\,\,\,如下图所示，一共有两条直达终点的路径，虽然两条路径都经过了第一行第二列的宝藏单元格，但每份宝藏只能被取一次，所以最终答案仍为 1+3+1=5 。