Spaceship

题目描述:

奶牛 Bessie 外星人绑架了，现在被关在了一艘外星人的飞船里！飞船有 N（1≤N≤60）间房间，编号为 1…N，其中某些房间之间由单向通过的门所连接（由于使用了奇怪的外星技术，一扇门甚至可能从一间房间通回这间房间本身！）。然而，没有两扇门具有完全相同的出发和到达房间。此外，Bessie 有一个遥控器，上有编号为 1…K （1≤K≤60）的按钮。

如果 Bessie 能够完成一个怪异的任务，外星人就会释放她。首先，他们会选择两间房间 s 和 t（1≤s,t≤N），以及两个整数 bs 和 bt（1≤bs,bt≤K）。他们会将 Bessie 放在房间 s 内，并令她立刻按下按钮 bs。然后 Bessie 需要继续在飞船内穿梭，同时按下按钮。有一些 Bessie 的行动需要遵守的规则：

  • 在每间房间内，在按下恰好一个按钮后，她必须选择从某扇门离开去往另一间房间（可能会回到同一间房间）或停止行动。
  • 一旦 Bessie 按下某个按钮，她再次按下这个按钮即为非法，除非在此之间她按下过编号更大的按钮。换句话说，按下编号为 x 的按钮会使得这个按钮变为非法，同时所有编号 <x 的按钮会被重置为合法。
  • 如果 Bessie 按下非法的按钮，任务即失败，外星人就会把她关起来。

仅当 Bessie 停止行动时位于房间 t，她最后按下的按钮是 bt，并且没有按下过非法按钮时，Bessie 才会被释放。

Bessie 担心她可能无法完成这一任务。对于 Q（1≤Q≤60）个询问，每个询问包含一组 Bessie 认为可能的 s,t,bs 以及 bt，Bessie 想要知道可以使她得到释放的通过房间与按键序列的数量。由于答案可能非常大，输出对 109+7 取模的结果。

输入格式:

输入的第一行包含 N,K,Q。

以下 N 行每行包含 N 个二进制位（0 或 1）。如果从房间 i 到房间 j 存在一扇门，则第 i行的第 j 位为 1，如果没有这样的门则为 0。

以下 Q 行，每行包含四个整数bs、s、bt、t，分别表示起始按钮、起始房间、结束按钮、结束房间。

输出格式:

对 Q 个询问的每一个，在一行内输出操作序列的数量模 109+7 的结果。

样例输入:

样例1
6 3 8
010000
001000
000100
000010
000000
000001
1 1 1 1
3 3 1 1
1 1 3 3
1 1 1 5
2 1 1 5
1 1 2 5
3 1 3 5

样例2
6 4 6
001100
001110
101101
010111
110111
000111
3 2 4 3
3 1 4 4
3 4 4 1
3 3 4 3
3 6 4 3
3 1 4 2

样例3
6 10 5
110101
011001
001111
101111
111010
000001
2 5 2 5
6 1 5 2
3 4 8 3
9 3 3 5
5 1 3 4

样例输出:

样例1
1
0
1
3
2
2
0
5

样例2
26
49
29
27
18
22

样例3
713313311
716721076
782223918
335511486
539247783

提示:

样例1解释

门连接了房间 1→2、2→3、3→4、4→5 以及 6→6。

对于第一个询问，Bessie 必须在按下第一个按钮后立刻停止行动。

对于第二个询问，答案显然为零，因为无法从房间 3 前往房间 1。

对于第三个询问，Bessie 的唯一选择是从房间 1 移动到房间 2 到房间 3，同时按下按钮 1、2 和 3。

对于第四个询问，Bessie 的移动方式是唯一的，她有三种可能的按键序列：

  • (1,2,3,2,1)
  • (1,2,1,3,1)
  • (1,3,1,2,1)

对于最后一个询问，Bessie 有五种可能的按键序列：

  • (2)
  • (2,3,2)
  • (2,3,1,2)
  • (2,1,3,2)
  • (2,1,3,1,2)

确保输出答案对 109+7 取模。

测试点性质：
  • 测试点 4-7 中，K≤5 且 (bs,s) 在所有询问中均相同。
  • 测试点 8-11 中，对所有询问有 bs=K−1 以及 bt=K。
  • 测试点 12-15 中，N,K,Q≤20。
  • 测试点 16-23 没有额外限制。
时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 DEC Platinum