3872 - 旅行
时间限制 : 2 秒
内存限制 : 128 MB
小 C 在 C 国旅行。
C 国有 个城市,可以看做 的网格。定义 表示在网格中第 行第 列的城市。
该国有 种交通系统:
- 对于所有 , 到 有一段由 L 公司修的单向铁路;
- 对于所有 , 到 有一段由 Z 公司修的单向铁路;
在每一个城市有一个售票口, 城市的售票口可以用 元购买一张 L 公司的铁路票, 元购买一张 Z 公司的铁路票。当你拥有一个公司的一张铁路票时,你可以乘坐这个公司的任意一段铁路,并消耗掉这张铁路票。注意,一张铁路票可以且仅可以使用一次。
小 C 原来在城市 。他想要在 C 国旅游,但是他不想浪费任何的钱(即,当他旅游完毕时手上不应该有多余的车票)。对于所有 ,求他花 元钱并在城市 结束旅行的方案数,对 取模。
两种旅行方案不同,当且仅当小 C 经过的城市不同,或他在某一个城市购买的某家公司的铁路票数量不同。
输入
输入的第一行包含三个正整数 ,表示网格的大小和钱的数目。
接下来 行,每行 个正整数,第 行第 个正整数表示 。
接下来 行,每行 个正整数,第 行第 个正整数表示 。
输出
输出一共 行,每行 个整数,表示到每个点钱恰好花完并结束旅行的方案数,对 取模。
样例
输入复制
3 3 5 3 2 1 2 1 3 1 3 2 1 2 3 2 3 1 3 1 2
输出复制
0 0 0 0 1 5 1 3 5
提示
【样例解释 #1】
到 的方案有:
- 在 购买 张 L 公司的铁路票;乘坐 L 公司的铁路到 ;在 购买 张 L 公司的铁路票;乘坐 L 公司的铁路到 。
到 的方案有:
- 在 购买 张 L 公司的铁路票;乘坐 L 公司的铁路到 ;在 购买 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 。
到 的方案有:
- 在 购买 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 ;在 购买 张 L 公司的铁路票;乘坐 L 公司的铁路到 ;乘坐 L 公司的铁路到 。
- 在 购买 张 L 公司的铁路票和 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 ;乘坐 L 公司的铁路到 ;在 购买 张 L 公司的铁路票;乘坐 L 公司的铁路到 。
- 在 购买 张 L 公司的铁路票和 张 Z 公司的铁路票;乘坐 L 公司的铁路到 ;乘坐 Z 公司的铁路到 ;在 购买 张 L 公司的铁路票;乘坐 L 公司的铁路到 。
到 的方案有:
- 在 购买 张 L 公司的铁路票和 张 Z 公司的铁路票。在此之后,有 种方案可以从 乘坐两公司的铁路到 。
- 在 购买 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 ;在 购买 张 L 公司的铁路票和 张 Z 公司的铁路票。在此之后,有 种方案可以从 乘坐两公司的铁路到 。
对于所有数据保证:,$1\leq k,a{i,j},b{i,j}\leq90$。
来源
KDOI