Welcome to ZOJ
86 - ZOJ Monthly, January 2010 - C
Escape from the Pyramid

Time Limit: 2 Seconds      Memory Limit: 32768 KB

Watashi is a treasure hunter. One day he found a special pyramid by chance. He was very exciting and rushed into the pyramid immediately. However, as soon as he entered the pyramid, the gate was closed, which meant that he couldn't escape from the pyramid through the entrance.

At the moment, there was a voice speaking to watashi: "Hey guy, look at the wall. There is a map describing the construction of this pyramid. It has N rooms (numbered from 0 to N-1) totally and some unidirectional roads which are connecting the rooms."

"However, the roads which start from room i are not always available. For room i, there is a period time Ti (1 <= Ti <= 6) and the states of all roads which are starting from room i are showed periodically. That means if the roads from room i are available at time t, they will be available at time t + Ti. In addition, all the states in one cycle are given to you."

"Every second you can choose to stay in the same room or go through the available roads to another room. Go through the road only cost you 1 unit time. The room which you are staying in at the beginning is room Starting (in the range of [0,..., N-1]) and the exit is in room Terminal (in the range of [0,..., N-1], Starting != Terminal), as soon as you enter room Terminal, you are sent out of the pyramid and get lots of treasure. However, if you can't escape from the pyramid in T seconds, you will die in it."

"You are given several seconds to look through all the information then I'll begin to time. After that, time will start from 0 and the roads' states are changed. Good luck!"

Watashi was very calm after listening what the voice said, and he wanted to know how many different ways he can achieve the task in no more than T seconds firstly. Please help him to figure out the answer.


Input contains multiple cases(<= 15). Process to the end of the file.

At the first line of each case, there are four integers N (2 <= N <= 50), T (1 <= T <= 10^9), Starting and Terminal respectively.

The following N lines describe the connections between any two rooms. Let rij be the j-th integer in the i-th line. If rij = 1, there is a unidirectional road from room i to room j; otherwise rij = 0 and there is no road from room i to room j. It's guaranteed that rii = 0.

Then N lines follow. The first integer in the i-th line is Ti, then Ti integers (gi0, gi1,..., giTi-1) follow. If gij = 1, all roads starting from room i are available at time j; otherwise gij = 0 and all roads starting from room i are unavailable.

There is a blank line between consecutive cases.


For each case just figure out the number of different ways watashi can achieve the task in no more than T seconds. The answer may be very large so you are just asked to output the answer mod 100000007.

Sample Input

3 2 0 2
0 1 1
1 0 1
0 1 0
3 1 1 0
2 0 1
4 0 0 1 1

Sample Output


Author: MO, Luyi
Source: ZOJ Monthly, January 2010
Submit    Status