SP12807 SPP2 - Recursive Sequence (Version X)

_Sequence _(a $ _{i} $ )_ of natural numbers is defined as follows: _a $ _{i} $ = b $ _{i} $_ (for _i t_) where _b $ _{j} $_ and _c $ _{j} $_ are given natural numbers. Your task is to compute _a $ _{n} $_ and output it modulo 10 $ ^{9} $ +7._ The above is the description of the original problem [SEQ](http://spoj.com/problems/SEQ). However, to be a problem in a regional contest, the description will be slightly modified to make the problem a little bit complicated: for almost all integers _i_ > _m_, a $ _{i} $ follows the formula given above, but there are **q** exceptions n $ _{1} $ , n $ _{2} $ , ..., n $ _{q} $ : _a $ _{ni} $ = d $ _{i1} $ a $ _{ni} $ -1 + d $ _{i2} $ a $ _{ni} $ -2 + ... + d $ _{iti} $ a $ _{ni} $ -t $ _{i} $ (for 1

For each test case, the first line contains three integers **n** (**m** < **n**

For each test case output the answer in a single line. Refer to the example for more format details.