P15434 [HackerEarth] "One does not simply walk into Mordor.
普及
题目描述

"One does not simply walk into Mordor.
Its black gates are guarded by more than just Orcs.
There is evil there that does not sleep.
The great Eye is ever watchful.
It is a barren wasteland, riddled with fire, ash, and dust.
The very air you breathe is a poisonous fume".
-Boromir at the Council of Elrond
So it all came to an end.Frodo is on the way to enter The Evil city of Mordor. Frodo is with his friend Sam Gamgee and Gollum
are on a quest to destroy the ring.The time has came they entered into the Mordor but the way to Mount Doom from the Black Gate
is quite tricky.The field of path is arranged into the form of a grid of size n*m Frodo has to go to the Mount doom for destroying
the ring,But the task is not quite simple because of the tricky magic of Saruman.

Frodo and his team is standing on Black Gate(0,0) now and they have to go to Mount Doom(n,m). Frodo got depressed because he is not
getting how to reach to Doom.But suddenly Gollum cracked the trick of Saruman the White. According to the trick They can walk either
RIGHT or DOWN, to reach the bottom right of the grid i.e at (n,m).

Thats not enough Gollum in  greed of his "My precious!" tell the trick to Frodo but  again ask a riddle to him,the riddle is as 
follows, Frodo has to tell Gollum the number of ways in which they can reach from  Black Gate(0,0) to Mount Doom(n,m) by following the trick


Frodo can't loose now but he is not good in mathematics ,so he ask you Brilliant Programmers for help.
You have to give the number of ways mod 10^9 + 7for given input size of grid .

Note Consider the following 3*3 Grid

Hence the number of ways are 6.

Input

The first line of the input contains an integer T, the number of test cases. Each of the following T
lines contains a two space separated integers N
and M denoting the number of rows and column of grid respectively.
Output

Print the number of ways mod 10^9 + 7

as explained in the problem for each test case in a new line

Constraints
1 ≤ T ≤ 100
2 ≤ N,M ≤ 10^6SAMPLE INPUT
1
3 3

SAMPLE OUTPUT
6

Explanation

As explained in question.

输入格式

见题面

输出格式

见题面

样例输入
100 930886 289383 636915 692777 238335 747793 760492 885386 641421 516649 490027 202362 520059 368690 513926 897763 383426 180540 455736 89172 595368 5211 956429 702567 21530 465782 665123 722862 703135 174067 979802 513929 723058 634022 898167 133069 18456 961393 478042 175011 377373 176229 544919 484421 898537 413784 594324 575198 664370 798315 803526 566413 268980 776091 241873 759956 999170 806862 497281 906996 420925 702305 336327 477084 126505 660336 621729 750846 925857 661313 353895 616124 100545 819582 233367 898814 990364 515434 313750 344043 426808 171087 947178 117276 393584 695788 502651 705403 612399 392754 95060 999932 993368 549676 210012 947739 698586 636226 297539 348094 480570 140795 960378 651434 66601 97467 612902 710097 570492 573317 260756 926652 560280 997301 209441 724286 429689 953865 346619 228444 744729 558440 108117 958031 905771 738097 890675 834481 698927 120709 777856 704567 872353 179497 276965 254586 964683 455306 28624 406219 332871 51528 48829 805732 530019 409503 363368 258270 486715 959708 518149 226340 700723 747796 2245 142618 493451 122846 243555 892921 597488 192379 888228 537764 792350 469841 441500 165193 87764 757034 324914 470124 275856 936987 346491 373743 148365 322227 281936 709859 452551 151432 899228 316437 975407 153275 276121 901474 794395 468858 661237 36029 573793 908235 894428 65818 231011 366143 639529 335928
样例输出
226255161 340671683 578609748 258736622 864377030 15631209 370273620 729863646 172231053 787987115 535645505 991132426 920359294 310978246 298528921 679823180 599033579 870797980 167719978 799838909 35568257 749816814 836317095 665332752 78693994 264071838 936893604 57608155 497253935 941125846 924331959 286484066 627349455 755543630 167633878 914711829 839547817 606586853 795053174 438876001 886447303 803068785 281186310 225019593 92105449 786661274 151310423 812934393 996992921 404456608 635399816 428381786 761382508 511510997 351740670 249178409 754738763 223547065 317905768 379122677 356713995 993042562 697396098 319585005 165288957 768707011 157718175 119091921 964713466 771256930 925489073 169415127 4499441 211798027 847087453 624420202 268638983 242886595 319793799 84945354 786825872 394944545 891835892 320179304 835813753 676569644 233231315 831578185 932048191 73397466 850210328 752863191 882433283 131481472 191799263 170389221 770334594 340452421 382548278 197609855 558961468 764760856 157939912 970095429 65613626 140366460 705932583 629655965 884952750 457351810 975812683 692938618 540686508 509115730 207940649 498689251 464845254 962493061 515488535 894383016 163680000 165321316 482231989 284666765 817086091 656405996 813074491 114997589 45010170 797591747 403435418 454197167 512138938 623247379 162613427 775904662 869203919 330463583 864492136 603147317 209897250 570579054 466653814 59073829 989094807 563257092 590030096 972919060 220851197 361787601 829681233 606105970 812203438 45127460 227846125 537736838 536181055 787317030 112180188 537654626 166360010 335002108 734554219 484753256 878258592 553520172 723969162 99058591 804939100 111111652 180424042 763356874 567344875 956852402 914672580 267254893 491594280 316515630 709571010 859697737 401817917 778662583 598430080 88997789 870699755 12423468 987308179 518718306 778641757 214993234 49963792 500416180 770408441 525030377 613328096 342195517 832178425 640652868 893803389 654034152 238246602 877618621 668596188 468472972 318006078 173164597 936508280 387963772 595055096 669836783 33610232 212047326 658549432 647126694 484667133 39963168 105434987 409204403 840804222 641755920 94544953 189759525 284366003 997342673 259038340 432987661 69531200 394081362 531143907 219870438 867112162 182784008 505264003 959269011 402340305 833961144 466768454 68260878 346313445 533580371 496966034 692801609 489762787 372817529 903045464 117297255 287940739 910267376 576828820 968649761 624203164 168117795 567122100 372650453 704239887 543052491 235329256 96055287 793317241 89159066 747643648 58200247 12380723 628524168 205941145 152659506 927551659 126810924 931500911 504936271 97865583 372177786 455211990 124501386 291245090 91957503 283725500 989425577 714024919 643706495 896321890 647936836 853174037 947158706 410929882 593090092 961768317 233212229 211644780 267357705 588657223 379667447 238511324 242167028 722988777 466275606 471271189 977944927 892050907 566417387 997577328 148345094 151308314 533123995 524430567 720786059 162458600 595378180 290380869 240281065 290930270 965213799 410938064 561371013 782415419 613605399 902944221 820505729 745475153 755658894 625326250 805245466 101417744 943793748 491305965 340369623 997866186 483036688 160862827 22695061 962652110 803420538 248157903 549885082 453067387 994080215 191113633 217963529 733625882 765525119 237923066 719286264 582284829 627922062 706294447 726163206 281052757 127907377 390910056 526113538 202535906 24294591 923916793 783359618 158395060 5086062 427963273 922799568 766780554 75506110 674568690 947426259 571400376 498359782 430064760 255974288 96549671 818586982 271296475 468133485 133575115 43934182 718368459 425482686 387957915 586877879 914212258 824715664 61533964 879137375 864445946 220173624 315442149 520812767 214960614 145748506 902039225 123789281 518474276 708642275 448923878 391533716 372637096 986868768 497959215 760660390 530681823 663995751 591952743 732968744 6238448 339979288 422276983 189221336 475375899 43563895 528719566 121473230 702997118 354754416 852944293 882030996 184598228 106540251 862968946 272169415 641517404 160853048 991105362 805302576 652421523 822927430 595765990 643815178 863086119 69902266 197766417 590331941 430644037 658434334 81729503 608540924 114268330 93429913 287243784 910448063 396141895 409231735 888883550 259294129 783469465 37610697 423942960 195243129 16878544 678770698 833405079 593465029 663661054 326321958 520689905 984039141 478081618 489503086 193211529 856277369 500852796 695536689 50480766 154413821 370434621 278831880 321863578 406638779 283098850 22545753 93412914 638046886 886814934 713310667 609663778 266540603 400629736 213414722 13947710 397791187 42180654 858292794 234693036 941637596 737213583 28393217 401377486 685347624 960671173 145714469 661862934 520092229 925950955 367566188 490828669 721600424 659446293 403377349 308078754 942416941 551062623 569547022 350186636 109523101 434643495 36272752 436447846 330954007 723321922 399749636 316124576 876934666 816666961 115334397 611353484 524283950 470679986 56843433 408561704 508878740 959392243 978981687 560323001 291171970 603444156 254633720 431608920 474253231 671788507 351914032 149702170 25854332 829051737 690494838 563378271 208692113 382722207 276687981 614104392 398055102 15910506 915804059 173652356 194013320 573643030 889059898 435671630 516219530 796065996 694078556 547909499 660647917 296325152 749822670 53045258 203370168 850173141 111384143 225724222 893252858 361853338 72750117 650928654 369254176 278195978 854082732 97432455 63129900 127763732 485348009 205553153 835718608 651179587 320772358 953012855 190182933 250525901 72151652 878721234 919108756 884755067 926605677 145439524 886270045 898407505 599975118 536408037 805803290 40376837 704803674 801805766 421444549 200939721 8852540 667425430 729384082 799787542 764458622 814497723 641684456 370319778 405111261 68352154 698202572 942798761 338271546 462718210 576327324 617653978 968330023 123575163 13973606 712212952 486160643 276489327 378591598 256775007 381648866 861722987 373872320 983453623 810100594 738616483 33521359 516306630 471293467 375196652 818246317 92626179 756532367 553974462 82789069 216658902 433781893 178509337 546066591 565595499 508948077 866287341 303711652 764781373 418494943 713121705 337562653 325832956 138131049 905914323 329651724 172405399 510920259 747778131 659368766 770497061 208096530 963630273 307325440 633669561 648571899 633140350 877219858 208424717 691235777 144490864 618036621 763210456 171447190 313724366 822412803 242558155 338829472 384094943 931097414 414034024 936468968 381328746 902656220 434995415 964487068 596262338 653823068 991319762 558667600 838868979 703848989 463869280 394301556 53818250 827852461 159212200 528247743 482658667 67460328 998141067 41671391 588192059 417135512 739703331 95098270 889448041 505941151 82346119 467866614 552731044 635407533 329754592 34944302 789466888 61492546 859952710 595862029 19983922 267576643 987125152 531220255 125605280 394843779 308182528 622031193 415551095 542989747 106181939 78494884 651283750 566995827 844275145 560619053 666903294 617734719 796863110 450504173 443408277 569507783 889901580 739521185 5427614 149235690 980019995 223024324 383095706 200688397 110094054 867234591 564422449 480010959 965399567 298011247 710565821 723998063 698469510 651654586 978830077 751094203 436337753 816383479 398788123 669510598 514331583 795439438 887930317 536604459 107956807 721218915 660530898 593103207 904856563 669234911 779228802 14277999 684261495 49354524 485563650 832446018 642018827 16542976 941418766 680296700 768379969 232260872 614068049 983784554 18842712 616382879 249457167 609303339 170083284 876356551 178413777 442629434 579508543 876927510 89520398 83731858 182830674 840674735 90428558 237541363 381584939 728151799 93093997 873226756 326365201 470099279 608348150 316229407 119937766 117744076 247421284 597754960 229809322 81743436 475283853 87343373 107359937 625252338 469020275 537703986 285981848 599902578 853492878 178228739 196064072 837487623 616104623 483774977 763717192 166080501 844097491 176107920 271954819 40188409 81181396 894408775 622450224 491501963 409560928 55996346 478232669 147509422 531109578 641870225 354693207 890941339 169097401 999118619 494121827 47344229 194428269 453633838 665113211 981049753 713257312 362025651 537222417 974768316 162110237 434645927 259115008 227144213 842373000 920940719 616347266 55914093 668809704 454128018 59675011 255172393 347667591 424735209 758189195 584210555 905730098 646038928 409247145 614965791 225272037 332788262 716546483 921496719 549755100 453542132 930147235 378125052 809794453 256783606 784315537 678171086 245832712 851204693 986659596 374769735 895400718 432775405 832352688 643530479 977170758 264232894 552599207 355112009 948851993 28382434 875944776 948035868 199288917 235998872 471055279 522358230 740942480 362745949 506863677 564445445 854040370 460418584 51405161 152695222 757583279 282836782 320627054 487595880 382696608 537638264 931406409 956622535 934790769 53745079 22944823 496191712 39986100 404899835 426118418 980640207 141607669 596560539 152984733 207413592 415406344 733593998 339448236 816554276 238209308 274849789 149363801 973151798 876726286 251647478 574034517 373387818 797465062 69066491 319428007 521633620 674237058 12891371 209288245 704013575 876345814 44698552 5000438 434911958 216240397 460531602 849371352 647771302 485601958 81793555 889415058 940033747 448190311 82030308 61680274 769355595 499435612 46583581 787428771 616783313 44140431 801555481 667326881 158311981 606434308 18419213 195468089 335614751 173030175 359212245 221851902 896913093 682298871 609362280 417667402 112740230 31408338 944991269 441551273 114819604 393777752 778754238 495780524 568766204 191152364 716137431 795950061 207536015 750403891 584574801