
ZOJ Problem Set  3289
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 N1) 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 <= T_{i} <= 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 + T_{i}. 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,..., N1]) and the exit is in room Terminal (in the range of [0,..., N1], 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 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 r_{ij} be the jth integer in the ith line. If r_{ij} = 1, there is a unidirectional road from room i to room j; otherwise r_{ij} = 0 and there is no road from room i to room j. It's guaranteed that r_{ii} = 0. Then N lines follow. The first integer in the ith line is T_{i}, then T_{i} integers (g_{i0}, g_{i1},..., g_{iTi1}) follow. If g_{ij} = 1, all roads starting from room i are available at time j; otherwise g_{ij} = 0 and all roads starting from room i are unavailable. There is a blank line between consecutive cases. Output 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 3 Author: MO, Luyi Source: ZOJ Monthly, January 2010 