P16873 [HackerEarth] We all know that Gayle likes dealing only in fours and sixes.Therefore the balls he faced can be represented as a sequence of fours and sixes.
普及
题目描述

We all know that Gayle likes dealing only in fours and sixes.Therefore the balls he faced can be represented as a sequence of fours and sixes.

But Gayle likes to hit sixes only in groups of size S (i.e. Once he starts hitting a six, he doesn't stop until he hits exactly S sixes). He may start hitting sixes immediately after ending a group of S sixes. This new group is considered different from previous one.

Abishek was told that Gayle played some number in range [a,b] (a & b included) number of balls. Being a fan of Gayle, Abishek know value of S. He now tries to determine how many ways Gayle would have scored through out his innings.

Help Abishek in finding out what he requires. As the result can be very large print it modulo 1000000007.
INPUT :
First line contains number of test cases T.
Second line contains the size S.
The next T lines contains pairs of integers a and b.

OUTPUT :
Print T lines, answer for each test case in a new line.

CONSTRAINTS :
1 ≤ T ≤ 1000000
1 ≤ s ≤ 100000
1 ≤ a ≤ b ≤ 100000

Problem Setter : Abishek

SAMPLE INPUT
3
2
1 3
2 3
4 4

SAMPLE OUTPUT
6
5
5

Explanation

S = 2
Case #1 : a = 1, b = 3
Gayle would have played in any of these 6 ways, {4} {4,4} {6,6} {4,4,4} {4,6,6} {6,6,4}
Case #3 : a = 4, b = 4
Gayle faces exactly 4 balls. All possible cases would be {4,4,4,4} {4,4,6,6} {4,6,6,4} {6,6,4,4} {6,6,6,6}

输入格式

见题面

输出格式

见题面

样例输入
1000 88888 42 18468 6335 26501 15725 19170 11479 29359 24465 26963 5706 28146 16828 23282 492 9962 2996 11943 4828 5437 14605 32392 154 3903 293 12383 17422 18717 19719 19896 5448 21727 11539 14772 1870 19913 25668 26300 9895 17036 23812 28704 30334 31323 4665 17674 7712 15142 6869 28254 25548 27645 32663 32758 12860 20038 8724 9742 779 27530 3036 12317 1843 22191 289 30107 8943 9041 19265 22649 23806 27447 6730 15891 15351 24371 15007 31102 3549 24394 12624 19630 19955 24085 11841 18757 4967 7377 13932 26309 16945 32440 11324 24627 5538 21539 2083 16119 16542 22930 4834 31116 4640 29659 9931 22705 2307 13978 22387 31674 5022 28746 19073 26925 5830 6271 15574 26778 5098 16513 13291 23987 9162 18637 22356 24768 15575 23656 4032 12053 1151 27351 16942 21725 3431 13967 30192 31108 11338 18008 12288 15458 10384 27754 8910 14946 9759 32210 18589 24222 6423 24947 13031 27507 16414 29169 901 32592 1656 18763 6360 17411 20538 27625 6484 21549 4042 27596 3603 24351 10292 30837 9375 11021 4597 24022 23200 27349 19669 24485 4735 8282 54 2000 26419 27939 3789 6901 468 18128 3729 14894 22484 24649 2422 17808 6618 14311 9515 22814 7617 14310 17452 18936 5250 20601 16520 31557 22799 30304 6225 11009 5845 32610 14990 32703 3196 20486 3094 14344 1588 30524 9504 29315 7449 25201 6619 13459 19797 20581 14799 15282 19590 20799 27158 28010 20473 23623 12293 18539 6039 24180 18191 29658 6192 7959 19816 22889 11512 19157 2635 16203 20056 24273 20329 22647 4887 26363 18876 28434 20143 29870 1417 23845 21882 31999 10323 18652 5700 10022 3558 28477 24390 27893 5076 10713 2511 2601 21004 26870 14689 17862 9790 13402 15256 16424 5003 10586 10286 24183 27089 31427 23758 28618 9833 30933 2155 4170 17190 25722 19977 31330 2369 28693 10556 21426 3435 16550 7442 9513 18061 30146 3754 21719 12424 16140 16280 25997 12530 16688 17438 22550 12950 19867 194 23196 3298 20417 16106 28287 16283 24489 12456 25735 11702 18115 20672 31317 5787 12264 4314 24356 20054 31186 913 10809 1833 20946 4314 27757 19559 28322 23647 27983 482 4145 20223 23197 2162 7130 5536 20451 10467 11174 12045 21660 26293 26440 17254 20025 26155 29511 4746 20650 8314 13187 4475 28023 2169 14019 9906 18788 7392 17959 3626 10203 4415 26478 9315 25825 25875 29335 20160 24373 11834 28071 7488 28298 7519 8178 17774 32271 1764 2669 13986 17193 3103 8481 7628 29214 4100 4803 2626 30528 1544 1925 11024 29973 13062 14182 27433 31004 17506 27594 13032 22726 143 8493 17223 31287 7901 13065 8361 19188 22414 30975 14271 29171 236 30834 19712 25761 4668 18897 7286 12551 141 13695 2696 21625 2126 28020 21695 26577 22659 26303 17372 22467 4679 22594 23852 25485 1019 28465 21120 23153 2801 18088 1927 31061 4758 9011 20316 32171 9577 30228 12044 22759 5110 7165 7883 17087 3488 29566 14475 29578 2626 25628 5630 31929 25424 28521 6903 14963 124 24597 3738 13262 10196 32526 1265 8261 6203 8117 5031 20327 29012 30772 6412 25548 21154 21521 14925 29791 21764 30189 4941 20852 13830 18663 17714 30901 17579 18959 8366 13008 1201 11478 6440 26059 2304 12761 2325 19358 5109 6478 14888 21114 19802 22851 14461 22429 12994 27385 6541 19406 28705 31112 12836 32357 6073 29351 14486 18824 20557 23217 1627 9358 8527 13358 23272 29338 23870 29362 12897 13023 10113 29618 12718 18697 11586 24042 24130 24424 4566 24230 6560 8933 22297 29856 12054 16963 3585 29735 6655 16973 14370 21458 2964 22533 2484 2608 912 11636 10068 22849 4676 12939 2224 22143 6512 23755 20176 22742 17826 21460 3222 17871 1627 31935 15206 31784 17399 23851 22280 22702 12194 12735 1638 26535 1994 5557 10177 25706 6963 10549 301 15882 14414 16642 19856 24856 11463 13143 27612 30878 20425 32679 1753 18444 12674 28297 9314 10041 876 20073 611 12819 1018 14933 28113 30696 13170 23832 20041 26489 19091 28686 2590 19498 15146 25991 19315 19354 18652 26741 11259 22045 336 8760 7606 11193 12182 25265 3830 28504 20609 23776 5998 29293 17550 29557 25562 31628 6468 29542 26130 31241 27814 29175 6078 20602 8684 20216 8214 23993 5602 25825 15760 23393 2671 26429 4085 28028 10076 18787 15499 24971 6288 23848 504 32605 21222 22664 2364 5707 9011 22172 18241 27490 12165 25543 7620 20914 6705 7592 9233 31819 751 25206 1540 4976 304 11423 11248 21099 13585 13649 2972 17865 11076 22914 21546 28713 17547 18679 1770 15263 8520 13986 15945 28290 2866 18541 23246 25509 27871 28319 9602 28324 21133 24473 25088 27153 28571 29764 17104 29902 3528 14424 11601 26970 5566 14016 29 21544 2089 25348 2944 12638 22410 26464 4682 5050 1589 11343 609 32061 1759 21222 20889 29955 691 14147 7950 12844 21431 25621 749 27068 4537 20784 18036 32227 7039 15186 9854 25630 11225 15749 3360 19924 24767 32258 4945 14956 23319 32727 21026 25412 20356 31002 9497 22550 9516 18585 17965 23343 8076 17914 16143 31197 21949 25073 14607 20427 24430 26174 6706 32405 20627 29813 19376 30094 16037 16566 14737 29142 5995 30815 6653 8257 23937 30839 1356 20483 1132 21016 17842 18231 2012 14626 4187 32638 1651 19691 5663 21635 10354 10894 13453 21417 7263 14009 5455 22234 16304 16635 14257 26304 149 11125 4214 12318 24029 27110 21081 29201 16859 21319 24051 24156 15265 31362 3677 11904 26910 29644 3562 14903 24949 28490 1283 13654 2221 30675 5403 6924 3832 19370 3879 20260 19009 22620 23972 30004 9782 21946 12393 26505 25314 32686 5590 6699 5939 12723 6411 19038 6235 31462 9962 12509 3960 6494 1516 25270 24938 28870 59 14701 13972 26265 15118 16216 7816 24556 3040 18331 29289 30213 1955 28083 16086 20711 24485 24775 8381 29816 6542 25952 1680 18116 17111 25899 789 23074 18133 23978 28690 29957 10009 26114 12942 15791 1724 21364 29 25185 7201 24779 1886 5072 1072 21975 11334 22868 14296 26154 20826 32169 9677 15630 2599 28651 3310 4694 4687 30081 10117 12250 1529 26668 7865 26680 8406 29422 6817 8827 7517 27727 28667 29088 19965 27682 1341 5687 6022 11663 6065 14722 20416 29310 17903 29874 17125 23942 31763 32746 27532 28424 4807 12269 5603 9319 24308 31908 1013 23482 21137 26631 24115 26810 4085 23557 12291 21294 29153 29997 1055 25346 249 14709 7492 13713 5132 30115 7959 16440 24723 29705 1053 6996 7480 25270 18239 26424 10867 27919 17660 32499 21197 28487 7463 26634 12023 12159 1147 18393 3926 13038 10648 29459 6603 30808 4099 27831 14601 29293 7279 20800 18353 20449 541 13883 4576 28316 8763 9568 18398 22337 19898 31419 13852 25829 24231 26817 4450 16926 230 659 10941 24521 15148 29561 1656 25163 793 20676 22362 31755 16399 23147 8715 26947 19570 21189 8639 27664 15076 24516 476 11522 15616 20529 12571 13235 906 9465 19558 28963 14162 30525 12550 17470 331 31924 14334 28351 10911 22926 16337 19738 1279 18338 7637 12394 28165 30715 19950 31592 2506 19136 10005 13338 2624 16338 9971 28665 25609 30569 7086 19282 9153 18374 8195 28653 9877 23827 7573 28397 6250 14641 18820 29175 944 32612 1942 20290 5566 8420 3806 7586 16217 31451 1616 2610 9167 11065 16075 16894 13510 30301 9574 19696 13162 15590 17969 31173 26032 27359 19427 26269 10423 28511 8780 30775 23553 30911 4183 25392 5765 15496 875 1365 14903 28256 475 4461 6973 26822 25548 26123 9790 21578 25606 30196 7951 27595 755 16344 1013 2482 11673 23440 5913 13429 5968 9763 4416 24409 1909 17224 11760 26435 5205 29487 959 4320 5946 26807 8167 18701 11368 17693 21788 28533 30557 30975 3448 5022 18284 26223 2377 29332 26949 28584 12724 17983 14777 22019 9221 31112 23857 32183 8926 19491 4325 6487 15970 19678 7535 11644 15678 22669 21992 31069 7784 32197 7728 16829 15872 29427 10698 17613 11028 18704 5546 11409 7186 9509 24238 30239 21314 26444 8851 22502 2112 25129 23651 28150 1455 11193 682 15870 20268 27466 17714 19794 18635 25473 20973 22831 24902 28443 5178 13878 703 25771 1382 14365 8824 16591 2238 8024 16596 32180 2328 20170 12043 31311 11059 28183 7927 9488 1671 32529 2259 5652 7214 9861 21287 25784 2743 8611 4473 7129 5842 18435 3504 20719 14868 24866 1882 10939 9258 22751 18599 28615 2662 28459 26064 32757 20279 20808 19436 19490 6366 32076 1387 7587 7834 8361 13331 26049 8929 29493 12434 23841 1736 6767 11600 19811 11838 21893 7329 31983 11370 29353 21795 31245 6609 9253 11648 17433 7209 9536 3265 3498 23244 27650 22016 26842 190 16101 19813 30649 9524 19852 24475 28634 27201 29892 9991 19855 4920 25698 17781 22579 12932 32545 3341 13488 900 22526 5539 8484 6194 7493 25012 28253 1561 15835 1841 31498 2786 18530 18806 31541 13393 28792 13211 13550 21579 26980 9278 30972 74 20194 1621 21498 13827 31277 6583 19791 11160 13579 20419 26490 160 3450 9073 12925 10381 27009 10209 27968 6478 18504 15371 32608 12075 14197 12612 13723 19020 28762 11057 12891 16684 31164 13717 19933 2742 25453 4955 6814 2863 10397 15461 20616 2600 10905 4681 20137 9199 27033 14388 32585 3518 7241 8671 17007 242 18883 3524 25250 12106 31759 17096 29622 7297 9917 10179 15679 13580 25059 12751 27578 14008 23730 2996 24082 2679 24677 20900 27754 11785 15566 3094 13609 6173 11244 7515 29930 5056 10169 5974 11192 6749 8923 5652 10987 2145 16447 26518 31578 14630 29917 5875 15792 15470 22913 8147 30694 9092 9816 26858 26950 20641 26053 237 8552 9488 31227 16956 28163 8395 23184 16098 30181 3066 27066 2514 9262 12579 21079 14141 16879 4612 31948 171 2446 13490 29976 6150 24751 3334 13866 17283 22215 27008 27433 8897 16368 4883 28523 17642 31811 2188 7232 6480 6706 6322 6539 19448 31352 9647 24209 22277 25760 30190 30423 8487 27667 2029 3456 4861 29615 11778 29254 12504 31349 10862 22432 12456 29083 14198 22107 8753 15822 17297 26282 24456 26022 15948 27125 9136 18319 1775 11377 24999 29860 9254 12075 6923 10636 1644 28889 8154 13233 4748 28681 19927 25679 6451 14802 14200 24962 20856 26364 5717 10574 23246 31562 6474 28275 1551 24354 1182 4288 2700 18111 17466 18644 2530 7173 2113 9982 4382 13477 8248 26891 8806 16672 30033 32373 3990 9321 15432 23166 9659 11294 17207 26579 2207 16949 18167 27172 3397 16698 23695 31021 14789 15530 17985 30110 11970 28979 4016 21618 3685 16627 9169 17907 12098 25929 24391 28119 11786 15200 14487 19200 12421 20711 15814 18272 6086 27416 319 3581 1332 7268 8388 13445 14508 23187 4361 17828 26432 28075 7153 30272 4694 10269 338 19886 17605 31312 407 12678 7769 29023 5001 19414 543 17538 21389 30039 7356 13290 3182 31648 13094 16585 10762 10988 8218 20494 9502 17483 15666 29448 10754 22105 15085 19096 13526 30222 3965 21782 4873 8107 3344 3657 22594 27081 14869 16081 13714 21412 3252 20969 12080 27217 17041 28769 12934 31532 20664 23780 12260 26654 2096 27937 11875 24366 7721 26836 8977 25681 5726 18456 4072 24809 9157 13560 5603 17833 7906 10441 7376 21563 21963 22886 1837 21081 10798 31203 10081 10509 5341 12077 9059 31494 7741 8547 20475 24774 8881 19098 11073 23336 708 23401 20667 22956 4142 23589 12482 17169 19397 28316 1010 16226 18137 22013 11456 18763 743 25044 22 17923 9249 24513 26019 27369 9715 23718 13291 17651 3336 12760 3170 21896 5304 22641 21980 24200 24792 29106 8682 18662 3653 8754 24034 32030 7043 15988 20084 26254 11421 15815 12245 32719 7230 31064 18865 20653 4770 30471 15006 21048 1595 21488 3277 24327 6541 21324 7680 23991 24711 32589 17946 29272 28471 29222 20184 23590 4979 23956 5007 24780 13263 20136 23488 27197 2089 29034 12936 19780 14791 15994 18966 24963 11002 19106 11808 24568 2670 3135 1458 32672 3546 12999 13598 14219 8839 14845 7373 8564 21029 29265 14724 28802 7605 13491 24228 31602 11198 23693 19772 20364 22364 29302 3566 7722 17422 23446 496 18611 15023 16742 29152 31813 8056 23016 3394 8739 15280 19883
样例输出
427 161 537 132 525 566 524 480 56 396 182 753 91 279 159 275 248 43 394 843 81 21 27 556 588 73 64 803 11 223 294 631 183 894 366 333 177 45 81 132 26 847 67 595 637 522 328 5 53 411 723 16 205 685 319 720 879 554 231 411 281 467 391 105 18 228 234 550 54 313 186 398 51 518 344 519 504 262 310 126 69 115 87 582 256 536 364 580 177 204 446 947 495 119 323 163 190 404 294 322 294 503 372 22 518 223 241 699 288 248 35 161 256 148 197 532 191 121 131 265 136 450 775 55 337 417 242 299 499 461 757 452 97 320 669 85 531 633 93 846 191 376 154 579 80 312 113 92 20 558 667 323 110 113 65 116 15 269 702 175 135 65 3 117 210 231 268 570 325 529 39 164 105 113 440 210 314 338 4 26 91 283 604 122 247 331 101 115 457 153 101 585 414 90 502 512 238 775 198 349 521 97 777 376 386 708 69 381 939 108 399 72 717 359 48 824 155 540 115 599 31 248 259 555 74 79 93 379 79 90 391 446 13 716 836 739 114 359 704 63 804 108 133 1 295 73 55 474 480 321 6 93 292 732 131 347 106 546 94 150 218 399 367 289 356 456 53 376 754 31 47 379 117 563 492 273 357 361 271 178 96 532 887 535 34 556 319 313 368 538 898 148 313 110 410 127 277 772 260 84 267 589 346 647 308 564 476 401 530 105 433 520 421 597 215 20 308 240 235 311 350 264 804 221 915 556 650 429 624 74 130 59 72 193 425 403 109 299 191 677 11 42 69 86 667 545 449 772 249 345 245 30 702 458 555 134 422 349 153 277 367 288 107 618 546 441 120 129 52 110 861 147 116 509 459 628 328 241 525 288 320 93 166 828 91 359 537 516 285 309 33 628 248 549 517 96 531 114 170 682 244 174 163 234 514 584 478 8 386 412 375 76 88 640 831 39 898 161 231 270 167 302 546 610 151 389 122 148 96 594 629 484 60 34 551 16 241 200 316 74 25 117 109 150 520 82 129 239 238 356 432 371 485 517 466 623 593 992 186 139 405 116 205 355 259 442 470 248 93 643 721 84 237 310 47 845 610 267 428 436 547 772 693 132 297 132 164 362 157 603 810 925 524 117 626 57 81 382 611 124 166 160 46 19 204 608 257 346 636 672 78 47 801 16 81 543 276 632 493 474 672 469 10 127 291 475 215 23 504 43 51 186 168 80 179 319 165 149 246 876 200 200 729 280 515 79 356 233 204 40 449 3 613 473 430 397 443 469 98 372 269 225 361 18 426 58 103 324 442 387 350 93 594 46 38 421 78 232 581 328 352 347 271 279 66 216 213 487 60 149 386 617 333 654 139 224 219 8 92 836 223 142 444 766 355 133 117 26 389 206 255 511 662 11 158 400 192 436 330 396 472 245 472 197 18 687 337 278 636 145 527 315 277 389 430 80 17 338 248 737 119 643 417 159 274 121 25 893 556 118 417 96 695 127 333 32 157 328 43 525 252 204 226 64 181 163 484 696 94 4 218 217 385 139 257 153 447 144 399 641 523 135 349 390 236 17 68 485 45 176 668 550 74 297 208 481 296 445 396 38 231 45 315 13 520 363 227 337 231 384 805 90 184 320 136 721 118 198 220 400 145 375 48 307 270 274 345 259 235 428 327 381 276 121 125 564 228 433 52 291 865 383 787 21 223 137 125 724 824 490 204 265 146 469 141 316 525 176 184 271 648 642 250 685 556 614 516 535 147 709 891 5 120 231 513 66 445 124 772 183 331 301 92 274 89 429 540 716 119 609 316 271 766 189 114 4 255 513 755 333 278 485 626 530 47 399 538 333 201 52 233 212 66 415 462 204 208 431 218 496 125 441 345 106 62 33 409 839 202 388 111 168 294 245 72 72 268 346 787 513 149 348 206 199 106 592 197 351 879 109 636 119 373 673 244 375 356 759 33 299 644 245 846 3 624 43 730 857 245 572 302 279 525 358 263 66 50 299 464 330 113 416 568 263 284 754 433 6 321 74 498 479 237 297 29 190 660 5 318 187 771 317 536 773 282 738 165 757 372 140 383 869 486 109 272 253 734 417 226 473 181 56 736 606 439 270 427 202 280 765 287 285 312 444 326 54 233 103 297 675 902 289 325 27 378 422 724 333 199 658 3 99 29 40 197 384 507 136 193 304 28 109 75 197 305 91 646 221 387 1 798 141 315 27 169 782 22 94 252 538 247 535 393 3 185 216 107 102 406 485 428 34 164 8 134 736 693 18 343 589