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 x0 a b c. The rest of the row (N-1 plants) could be obtained as xi+1=(xi*a+b)%c.

Input

The first line will contain two integers N, K: 1 ≤ K ≤ N ≤ 5000, the size of field and the defined size of subsquare.

The next N lines will contain four integers 0 ≤ x0, a, b, c ≤ 1018 (c ≠ 0), which will generate the ith row.

Output

Output the sum of minimal heights of each subarray of size KxK. As it might be pretty big, output the number modulo 109+7 (1000000007).

Example Input

4 2
8 2 9 9
5 7 9 3
9 7 7 5
7 4 7 3

Example Output

6

Real Field

8 7 5 1
5 2 2 2
9 0 2 1
7 2 0 1

Example Input 2

10 8
78 51 99 77
27 95 37 80
76 5 93 32
92 48 56 64
93 17 18 28
70 30 15 73
60 69 36 56
12 11 63 57
18 81 55 60
59 92 68 81

Example Output 2

18

Real Field 2

78 73 49 57 3 21 15 17 42 8
27 42 27 42 27 42 27 42 27 42
76 25 26 31 24 21 6 27 4 17
92 56 56 56 56 56 56 56 56 56
93 3 13 15 21 11 9 3 13 15
70 71 28 52 42 34 13 40 47 38
60 32 4 32 4 32 4 32 4 32
12 24 42 12 24 42 12 24 42 12
18 13 28 43 58 13 28 43 58 13
59 69 17 12 38 0 68 6 53 3

Example Input 3

20 5
2956 1596 6710 2713
2626 2791 1425 3859
1874 6262 3248 2238
5856 4491 7062 2271
2722 1707 9943 7035
403 2209 7057 1975
7211 9708 3898 6949
2426 9144 8440 2974
5034 3983 6243 7717
3877 37 9002 7373
3021 2549 7277 5516
3673 9640 7775 5355
1563 9728 6671 5484
4342 2971 1237 6834
3589 3662 5391 9672
780 6008 5239 304
5095 4370 280 9403
6295 118 822 2545
5649 2519 5412 6501
2901 2829 9801 846

Example Output 3

38811

Example Input 4

30 8
42190820083565085 13910582960072682 404339598526125697 18330389877395687
13136432922739892 360508552206096544 840939247896706683 166851773518294104
195629367891644832 133017412681920741 791801761173755587 953548694494513035
930566226452148080 212263842828807811 175150807852323258 261521670663969864
223183990889228375 549657188306426129 227104892059916771 710982591168543028
622099644118414985 984577533571891185 802914550839341535 577466815316077292
363883415474075556 913215986569797 257759523922291507 129711072317319582
472381530848232370 587974020968388203 95939647385371737 421772367107774947
870958993881230243 98076059799725034 955829596729745763 73827358022047846
50043465537791007 178000244851301580 686791668222702403 230423627799787034
41761070639181344 703749524391633426 575680731101407438 948818018258441027
74006463131502635 534256412790647769 117842073420805101 689203117404347787
720627491787492218 206756570671097114 5074687913252083 402683208709668506
583558162725379851 516050342346753246 792500576162473842 130741479957823970
709539139438259321 132262390506172747 780941668119266465 575886488550729150
518457490774399283 781644026117044419 451050302936677524 319690456859518311
747952274084607955 433194299929591864 829471355224525516 87759356942462111
472230421696663981 150197958929639709 699963373353260575 156451405305679606
379767724942828073 307602673656652612 536339937437228412 450095461910438107
130196535602142550 12133076804665744 944874740331622465 112002748054899251
384924669386020020 895364022010504585 562727215734096434 364228612518853658
2558159832040223 42876494731943717 303029667687965036 370694399470107119
801915657644445462 610444723365908160 304599053734522278 593616674445351229
318887526987442235 390853723621574162 339872209606293879 308835452771750585
476033942116470840 213009419015490269 20470342994674399 282092030038623628
582424275023334455 712867665674241464 17697708714929958 654849385199113364
475223303973240030 425222042042672679 12723252770801578 591938517391534160
538033927835846645 318295777283007977 593613359214212470 772515434523625506
612174705584217229 415458073586196348 508007743847849815 965297054583491903
179981864970425260 975763652798172152 215122546620747273 113899093042760092

Example Output 4

641904340

hide comments
morass: 2017-10-19 21:17:34

@Rishav Goyal: Great you figuredit out! And also glad it was helpful ^_^ So congratulations & Have Nice Day ^_^

Rishav Goyal: 2017-10-19 19:37:47

@morass : Your comment was quite helpful. Thanks :)

morass: 2017-10-18 23:23:38

@Rishav Goyal: Good day to you. Well I strongly agree that your algorithm is "fine". Anywy for this problem the "so called" imput storage is also part of problem. It can be solved in O(N^2) yet your "algorithm" doesn't fulfill this :'( Anyway I'm sure tht if you will improve your "mulmod" function (optimal is to O(1)) you will get AC :) So to sum it up, it is not about "big constant" but "unwanted" logarithm :)

Good Luck & Have Nice Day!

Rishav Goyal: 2017-10-18 20:17:24

@time limit does not allow even input storing complexity. such issues always spoil the problems. should not spoj allow a big constant to pass the time-complexity so that people can focus on the real logic? for ex. like Codeforces.

morass: 2017-10-14 19:37:09

@mahmud2690: 10^9+7, thank you (fixed :) )

mahmud2690: 2017-10-14 17:28:14

Is modulo equal to 10^9 + 7 or 10^10 + 7?. Please, make it clear in the statement.

morass: 2017-10-14 02:01:22

@[Rampage] Blue.Mary:

Good day to you,

A) Right, fist is "N" second is "K" .. thank youu
B) Yes, xi<c for each i [1→N-1] (so first element might be bigger)

[Rampage] Blue.Mary: 2017-10-14 01:57:28

1. The first line contains two integers N and K, not K and N.
2. As stated in problem statement, it's possible that x0 >=c, whereas xi < c foreach 0 < i < N?


Added by:Morass
Date:2017-10-13
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All