Time to Study Graphs with Chef

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Consider directed graph which has n + 2 layers numbered from left to right by integers from 0 up to n + 1. The leftmost (0) and the rightmost (n + 1) layers both contain only one vertex while every other layer contains exactly m vertices. Vertices are numbered independently in each layer by integers from 0 to m  1. For each pair of vertices which are in the adjacent layers (i and i + 1 for any i (0 <= i <= n)), there exists an edge. The vertex which is in the layer with smaller number is the initial vertex for such edge and the other one is the terminal vertex.
Based on a graph as described above, Chef added k more edges. Each edge connects two vertices which are in the different layers, no matter the adjacent layers or not. Also, each edge is directed from left to right (as well as all previously existing edges).
Chef is interested in the number of ways to get from the leftmost layer to the rightmost one. Two paths are considered different if there is, at least, one edge which belongs to exactly one path. However, they are allowed to traverse the same set of vertices. In that case, there should be a multiple edge in the graph. It is also possible if some edge added by Chef connects two adjacent layers.
Input
The first line of the input contains three spaceseparated integers: n, m and k.
k lines follow. Each of them describes one of the k additional edges and contains four spaceseparated integers edge_{i} (where 0 <= i <= 3). First two integers are for the initial vertex and the other two  for the terminal one. Two integers each vertex is described by are the number of the layer (edge_{0} and edge_{2} respectively) and number of the vertex in its layer (edge_{1} and edge_{3} respectively).
Output
Output a single integer: the number of ways to reach the last layer from the initial one modulo 10^{9}+7.
Constraints
 1 <= n <= 10^{12}
 1 <= m <= 10^{5}
 0 <= k <= 5 * 10^{4}
 for each added edge:
 Layers: 0 <= edge_{0} < edge_{2} <= n+1
 Numbers inside the layer:
 In general: 0 <= edge_{1}, edge_{3} <= m1
 When edge_{0} = 0, edge_{1} = 0
 When edge_{2} = n + 1, edge_{3} = 0
Subtasks
 Subtask #1: n, m <= 6, k <= 2 (20 points)
 Subtask #2: n, m <= 110, k <= 30 (30 points)
 Subtask #3: original constraints (50 points)
Example
Input: 4 2 2 2 1 5 0 0 0 4 0 Output: 19
Explanation
Consider the graph without 2 edges added by Chef. There are 16 ways to get from the layer #0 to the layer #5. Now recall added edges. There are 2 ways to get from the layer #0 to the layer #5 using the edge 2 1 5 0 (0, 0 > 1, 0 > 2, 1 > 5, 0 and 0, 0 > 1, 1 > 2, 1 > 5, 0) and also 1 way to do it using the edge 0 0 4 0 (0, 0 > 4, 0 > 5, 0). Note, that there is no path traversing both added edges.
Author:  malinovsky239 
Tester:  shangjingbo 
Editorial  http://discuss.codechef.com/problems/CHEFGRPH 
Tags  combinatorics, dynamicprogramming, feb15, graph, malinovsky239, medium 
Date Added:  31052014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions