Chef and Bike

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
In Chefland, there are n cities and m oneway roads between cities. The chef will travel between cities along these roads using a very unusual bike. The circumference of the front wheel is n (the same as the number of cities) yet the circumference of its rear wheel is only n  1. We think of the circumference of each wheel as being broken up into equalspaced positions. So the front wheel has positions 0, 1, ..., n1 and the rear wheel has positions 0, 1, ..., n2. Each unit of distance travelled will advance each wheel 1 position.
For example, when the chef travels a distance of d when both wheels start at position 0, the position of the front wheel is left at d (mod n) and the position of the rear wheel is left at d (mod (n  1)).
Furthermore, the chef bikes very fast and the roads are very bumpy. Quite frequently at least one wheel is not touching the ground. When this happens, the wheel does not turn at all (the bike needs some lubrication). So the front and rear wheel may not even rotate the same total number of positions when travelling along a road.
For each road i, we are given the start city s[i], the end city e[i], the distance the front wheel travels f[i], and the distance of the rear wheel r[i].
Both wheels start at position 0 at the beginning of the chef's trip. After traveling a sequence of roads i_{1},i_{2}, ..., i_{k} the front wheel is in position F := f[i_{1}] + f[i_{2}] + ... + f[i_{k}] (mod n). Similarly, the rear wheel is in position R := r[i_{1}] + r[i_{2}] + ... + r[i_{k}] (mod n1).
The chef wants to start and end in the same city, but is ok starting in any city. The chef is also ok visiting a city more than once; it is the journey that counts, not the destinations.
The chef is also interested in calculating the number of paths where the final positions F and R equal certain values and the number of roads traversed equals a certain value (if he uses an road twice, it counts twice). Since the answer is quite large, you only need to output the answer mod 1163962801.
Input
The first line contains three integers, indicating n and m and t. Here, n is the number of cities (and the circumference of the front wheel, and one more than the circumference of the rear wheel), m is the number of roads, and t is the number of roads the chef wants to travel over. Remember, if the chef travels over the same road twice, it counts twice.
The following m lines describe a road. The i'th such line contains 4 integers, namely s[i], e[i], f[i], r[i] that describe the road as specified above.
Output
Output is arranged into n blocks. The k'th block (1 ≤ k ≤ n) will itself contain n lines, each consisting of n1 integers.
The j'th number on the i'th line of the k'th block should describe the number of different ways the chef can start and end a bike tour at city k that crosses precisely t roadss and leaves the front wheel at position F = i and the rear wheel at position R = j. Each number in this output should be reduced modulo 1163962801.
Constraints
 1 ≤ t ≤ 1000000000
 2 ≤ n ≤ 22
 2 ≤ m ≤ 10000
 1 ≤ s[i] ≤ n
 1 ≤ t[i] ≤ n
 990 ≤ 0.99 f[i] ≤ r[i] ≤ f[i] ≤ 10000000
 There might be several roads between two cities
 There might be roads from a city to itself
 Subtask #1 [10 points]: n ≤ 5, t ≤ 100
 Subtask #2 [20 points]: n ≤ 5
Example
Input: 3 6 6 1 2 0 0 2 1 1 1 1 3 1 2 3 1 2 1 2 3 5 5 3 2 10 10 Output: 1 5 0 10 1 5 1 5 0 10 1 5 1 8 0 10 1 2
Explanation
I have discovered a truly marvellous enumeration of this, which this margin is too narrow to contain.
Author:  wwwwodddd 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/BIKE 
Tags  hard, maths, matrixexpo, nov16, wwwwodddd 
Date Added:  15092016 
Time Limit:  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions