监狱逃亡
题号:NC229116
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

勇者为救公主杀入魔塔,不料在魔塔三层遭遇魔王偷袭,失去了神圣剑与神圣盾,而自身也被关入监狱。

监狱是一块的区域,每块格子都有一个价值。勇者目前在监狱的左上角处,而他需要逃亡到监狱的右下角处。

勇者每次可以向右或者向下移动一格,请问勇者逃亡到右下角,其路径价值和大于等于0的不同方法数一共有多少种,答案对取模。

输入描述:

第一行一个正整数

接下来三行,每行个整数,第行第个整数表示该块格子的价值,

输出描述:

输出勇者逃亡路径价值和大于等于0的不同方法数。

示例1

输入

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

输出

复制
3