Daniel's having a lot of fun at the ski resort! Halfway through, however, he notices that his best friend Max isn't here. Now, where could he be...

Unbeknownst to all, Max Sun has been captured by a gang of ski cults, who cannot stand the inert heat of the Sun melting all of the snow. Hence, they must disable him.

The ski gang is made up of ~M~ ski cults following a strict ranking that orders each cult from highest to lowest rank (the ~i~-th cult has rank ~i~). They also have access to ~N~ types of cutting-edge snowballs indexed from ~1~ to ~N~. The ~i~-th type of snowballs is only accessible to ~G_i~ cults (which could be none!). In particular, ~A_{ij}~ denotes the ~j~-th cult that has access to the ~i~-th type of snowball.

Now, the gang will attack Max ~Q~ times. Each time, all snowball types in the range ~[L, R]~ are activated, and the ~K~ highest ranking cults (lowest rank #) are allowed to attack Max. Each of these cults, if they have access to one or more types of snowballs, will choose exactly one type of snowball to use, though each type of snowball can be used by multiple cults. If a cult does not have access to any snowballs, they will simply avoid attacking Max at this time.

For each attack, can you tell Max how many possible attack combinations are possible, modulo ~10^9+7~? Two attack combinations are considered different if any cult uses a different type of snowball in the two combinations.

Note: this problem has not been tested in Python or PyPy

Constraints

For all batches:

~1\le L\le R\le N~

~1\le A_{ij}\le M~

~1\le K\le M~

For each snowball ~i~, the cults that have access to ~i~ are all distinct (i.e. if ~j_1\ne j_2~, then ~A_{ij_1} \ne A_{ij_2}~).

Batch 1 [20%]

~1\le M, N, Q\le 10^3~

The sum of all ~G_i~ will not exceed ~10^3~.

Batch 2 [80%]

~1\le M, N, Q \le 2 \times 10^4~

The sum of all ~G_i~ will not exceed ~2\times 10^4~.

Input Specification

The first line contains ~M~, ~N~, and ~Q~, the number of cults, the number of snowball types, and the number of queries.

The next ~N~ lines each contain an integer ~G_i~ followed by ~G_i~ integers: the cults with access to the ~i~-th type snowball.

The next ~Q~ lines each contain three integers ~L~, ~R~, and ~K~, denoting the current query.

Output Specification

~Q~ lines, each with one integer, denoting the answer to the ~i~-th query. Output your answers in the order of the input.

Sample Input

7 4 5
4 2 3 4 7
2 1 4
3 1 4 5
1 3
2 3 7
1 3 3
1 3 4
4 4 1
1 4 5

Sample Output

4
2
6
1
12

Sample Explanation

Query	Explanation	Total
1	Cults ~1~ and ~4~ have access to both snowball types. Cult ~5~ can only use snowball ~3~.	The product is ~2\times 2 \times 1 =4~.
2	Cult ~1~ has access to two snowball types. Cults ~2~ and ~3~ have access to only one. Note that only the ~3~ highest ranking cults may throw snowballs.	The product is ~2~.
3	Cult ~1~ has access to two, cults ~2~ and ~3~ have access to one, and cult ~4~ has access to three snowball types.	~6~

The final two cases are calculated similarly