SP33008 ADASQR - Ada and Squares

As you might already know, Ada the Ladybug is a farmer. She has a beautiful square field (of size **NxN**) in which she grows many beautiful plants. Each plant has some height. She wants to know, for each subsquare (of some defined size **KxK**) what is the minimal sized plant in it. As she doesn't want too many information, she only asks you for the sum of all such lowest plants. As it is mentioned above, she doesn't like "too many information" so she also comprimed the heights for you. For each of the **N** rows, you wll be given 4 integers **x $ _{0} $ a b c**. The rest of the row (**N-1** plants) could be obtained as **x $ _{i+1} $ =(x $ _{i} $ \*a+b)%c**.

The first line will contain two integers **N, K**: **1 , the size of field and the defined size of subsquare.** The next **N** lines will contain four integers **0 (**c ≠ 0**), which will generate the **i $ ^{th} $** row.**

Output the sum of minimal heights of each subarray of size **KxK**. As it might be pretty big, output the number modulo **10 $ ^{9} $ +7** (1000000007).