902 252
698722376 544666771 190469745 876171369 379243778 338970640 113006654 532524064 568334899 15779398 235571671 821151034 462053276 334186324 871792615 293445040 340772305 373561084 773724786 890750921 66082124 552341356 731548593 333369101 667959349 144949100 392550828 522701774 740717564 971314582 741608105 925258574 560138375 527860040 173108062 727694622 948125648 41403749 125575027 961291322 139268940 373219392 69883318 790728897 923204957 391014872 884080747 256108528 796835024 666497961 610309602 658926499 414648775 643524948 438116211 493361387 691074996 690178217 403027808 907663520 583405069 495582113 97903414 564996676 844054484 475049820 997800578 385870618 7034412 124287042 414896145 472450640 117727844 669287523 534515682 197405678 202002600 354904976 955375538 556204103 259831155 25739586 748842397 867065632 27831434 795460834 127301314 530685151 407633642 1054007 204508732 378504476 803128572 88730805 864288493 478244878 405615908 103628046 305040072 64604265 311045258 709136327 661042247 417012179 220400037 220793937 252440379 985352392 292421280 627615873 133229898 712578979 464765598 76522851 985450234 196400229 936010252 826271638 792489176 546828073 652025026 336730758 822785729 508795538 565229234 317026171 517125620 855261928 125890355 41699799 708935050 670285016 569750999 275151101 84581935 130094436 386068685 455272024 994616650 446588859 727535887 494460140 39212087 735820462 474945444 239943319 780851699 495222039 503533356 968074078 348109033 923664326 461683077 328926692 946678414 58057609 539096837 907966286 735720535 386630756 570743430 150142741 94311860 551151685 705417618 447182200 26967895 110303952 534503882 694216595 191714867 101678059 726524248 442205064 350458949 47538921 644080767 661106370 71727079 359455047 544898364 21189341 766581446 796243371 741258899 872097786 39736076 155999956 324401569 520236748 660668816 288069510 950218321 762112899 958376897 108151073 827477456 694275691 975357537 454593838 486724854 887789864 192564111 799801678 482687295 948622807 103756011 838101266 154322123 906448967 585903694 884231469 457855699 92288299 740318882 962225367 660934918 913296001 758154197 260749567 913895773 498022197 350897945 613088220 260902764 89148297 471871886 45714368 703190045 629705829 359671472 379303412 186058860 65396056 515658911 573323905 686229684 408546796 31389215 986878719 404008302 973472441 917800031 739746865 16892613 983039882 468228526 462046720 925607393 685603164 347829190 883814856 142517002 872091826 704680359 902296469 424233773 917861687 545379095 959813466 892142462 581898499 698404313 964060225 983956965 96147875 982184304 854866530 295508368 986968553 944532300 315710323 609030405 144055188 832734184 972389932 762877583 482767834 691927659 665976164 230586669 757999293 851230019 969362828 461831215 120724409 104575470 465300592 651228115 591406355 272213787 291992346 536169974 486664901 368119854 139693948 379205171 446318449 289139892 195162818 619542286 746881704 813567045 286135936 439764928 688281242 564107418 128901239 662757693 87372739 352016068 321799230 164754627 344941306 928350714 856787398 163549205 874338308 716274455 23338242 798581666 789401702 24701391 686926515 534220184 284933389 979607979 991757860 678597464 152972181 76100344 404644946 729454656 357435683 939660082 759798479 317116104 880495760 575065562 587471271 215952748 942842820 464793681 840136246 48489925 790208818 983785670 493314446 519184705 979513061 451234179 938518091 132697069 176582897 409660915 346210592 105891938 931390581 390390868 61100104 820261464 501223991 23104803 867974974 78047137 995520381 614348073 788499318 822758391 166340404 57428319 51187278 918858127 970801113 584350504 149061244 696679609 155468641 737096841 448115167 580607765 221783800 705687741 262255775 687622884 42545076 738812057 930536980 444817355 784536389 167162401 29727668 726218088 489676765 901004248 677832586 821262488 550530152 764895612 396048105 938069902 732624692 215023178 834649763 42569428 439896210 787281092 88515173 620194781 157385547 35394424 164460255 259076096 539116544 724743081 664863965 47030095 945433733 909921225 774034999 111506811 127891032 378784612 76340325 624946759 948158314 550545005 827085664 968878591 304761397 478758718 551654251 478886888 228629901 561441011 60715423 881904402 543654387 616650897 221163354 595914329 215553475 313640879 704149320 674628216 61572360 765995326 85753855 277379342 270974390 835462872 569241249 960553726 244017874 255637781 310946700 276414233 366136094 711396441 405965063 36271142 221548918 120850864 528320573 53364623 268740546 254949489 572116816 150710114 151534041 399044801 620757832 387590711 924918014 722870601 988458769 969616606 816694299 348335278 163226166 521606532 251156 381094857 541626560 844427701 178040832 773329467 316725732 603245699 743394439 383218257 859814963 309626619 161635174 727094208 862190293 839369015 218653926 623293069 946387874 86918588 36485236 103493353 742369926 652387459 18929596 122507797 124878743 886324211 921658598 682965127 619005185 503167041 720117392 179452702 796332662 368479349 392861216 632466874 607636693 361479372 43543105 649024491 948558541 680723312 236071034 522871092 592689779 885836096 848895859 454364230 408174643 301280553 533341370 480358000 984748220 938231691 176578425 857233923 276460833 899231462 546294111 576408923 606729744 462068078 854732217 313192612 878730268 98677364 877541908 842479166 149242970 404748146 77783851 946874520 86472124 335700635 253711707 195028247 837217754 660088356 523908272 586868676 924995744 784328737 277979018 797600201 591249914 67370930 570404063 417761918 66983407 441622974 3089794 459370348 219864099 321274759 394570447 189410611 918849543 927221342 365272829 159682086 313119568 418681241 731566486 488445633 316326725 653155323 71063614 571874598 440415912 132676970 40259412 312592103 933868688 113695871 275280913 525079780 571123767 555714064 839540507 482979161 433654213 385812159 334136882 839397411 409114623 41359779 741650854 240907510 465041839 883742802 468064925 5498107 527244616 545792740 332943266 338970491 428275527 470265925 691012306 32929198 532384902 494639940 267509196 979042800 703706990 461540819 555993476 636613346 568043699 859507235 618613932 499180673 718091044 640010051 652545690 784723616 182171308 983672623 760935267 34370603 611266459 828279864 634689690 227974677 363754627 57084900 220855025 302598914 917038331 917813673 876548370 916253819 996676389 52840609 149503555 852313624 850920603 121593540 505877960 334955935 415407170 740008844 882076274 722891032 341032463 116304265 461464246 410807937 301254493 329202677 270971498 529753718 527986903 426236731 961778190 927981021 742489164 674575685 401563079 196794022 771516330 295493547 83003127 114684419 353244049 96299246 604211897 591252431 515851803 576494802 46742736 623876395 588063867 159762313 754158032 845849723 665727983 185060544 189560227 868312300 422846842 371797421 475426260 148080018 359079724 849836391 979794592 955342282 457299081 723379494 713609172 385877525 534313232 955269318 14855023 416056517 188540445 529810464 440458906 492906155 977606252 637127223 184572662 403496968 892167550 761187672 851331645 314073761 42267822 460586616 782879132 1792670 216215971 249667230 401878161 884853510 700890244 48842509 270684010 589980439 446236716 568857074 229596417 394832100 53624712 193928567 636539686 958129575 840877756 816955780 835400890 730522152 590800063 199340548 840805010 9541980 383601167 25406779 351381801 873132432 384856042 58352931 180836703 609915422 151003948 841307379 113097216 346556907 821194898 787713684 281233134 482434147 185086575 317418931 589639609 335307992 1690186 287512809 25059133 744623651 220821189 391221200 20574033 500351797 755533325 505984794 597012433 438977379 749074062 234769871 872836265 111532328 758627862 468563381 615769919 590813925 385596372 479243436 86071149 233814186 875191595 274621973 581325260 748545875 739923024 485538956 809890242 562244697 532677641 688058712 106543763 518101749 233606624 671159268 958837006 600739681 903611437 107237045 890594694 202478769 496216285 611813151 470911545 813130481 249799062 19687722 424107116 718914175 145925414 394561186 455976483 823401394 394845947 313939703 362519467 435779957 742176463 67687031 631294131 838001353 768048589 461271510 494453764 372107957 962648497 60427008 7183258 287683549 348479646 896363394 650917461 864109684 559006200 10907178 564110846 386062879 87380286 448376320 933341556 508358197 463942566 687871031 74782531 640290982 72327895 950126513 34774022 583999132 250862957 782189399 636785827 23714542 775297025 826530463 712249741 275042069 259174391 713379097 640608192 613680729 75341566 692776010 814507106 522302263 727504179 62935464 569686408 683370765 957908432 473876222 374522631 944546589 812139358 939087084 73476855 851262985 88067444 567163276 851995237
3 471 721 77774321 837877700
3 95 304 246729779 341487197
1 6
2 18 444
4 285 632
1 627
3 270 480 320209957 231421813
3 640 797 656892978 236561250
0 743 35039080
4 380 670
3 503 587 775985762 334734853
1 837
1 520
2 22 397
0 469 29300141
1 464
4 288 777
3 98 754 630967757 342964023
2 356 400
1 481
2 136 257
2 364 446
0 702 925412755
3 0 671 76004013 623570849
4 584 817
4 186 689
1 655
4 121 286
2 272 644
3 343 432 688465723 206417524
4 76 353
2 27 72
2 302 691
2 88 444
4 709 896
3 264 375 63130506 232061161
2 406 804
3 0 406 410634916 125439801
4 724 898
2 352 768
1 429
0 46 866818058
0 540 565557270
3 212 244 941030352 896469125
0 317 173267770
4 65 320
0 187 204840377
4 34 362
2 62 557
0 163 558793295
3 338 569 281826159 751786516
3 410 489 57115068 129900744
1 817
2 480 853
2 0 702
2 402 849
2 411 614
3 168 779 682948594 438030514
1 61
4 0 849
1 325
3 412 491 130658794 920102772
3 400 635 788415526 70721480
4 745 808
0 229 106705691
1 735
4 759 785
4 88 394
1 498
2 407 526
4 606 868
0 118 304439428
4 49 510
0 202 182715524
1 426
4 683 866
0 863 126994109
4 5 729
4 242 535
4 39 321
3 166 272 616837453 282144803
4 109 676
1 366
1 422
2 112 484
0 132 628903849
3 379 401 361738603 722656261
2 149 389
4 498 650
1 6
3 168 489 85774251 878883019
0 221 697794317
4 113 560
4 0 345
3 257 782 74459689 267626660
1 818
1 419
3 660 897 779734907 752436642
2 0 688
0 569 985279389
2 665 813
2 160 277
4 106 499
0 644 727904135
3 0 888 642934509 763208440
1 125
0 242 866549898
0 289 416453615
0 284 785209862
4 354 737
0 65 802365569
1 889
0 718 461416660
4 103 767
4 225 501
4 236 432
1 198
0 10 826019270
0 795 559005648
0 195 862100401
1 415
3 0 872 702652655 818661942
3 342 641 940382487 875147634
0 489 884029568
0 248 278513975
3 238 805 576814658 694360434
3 724 863 792585564 586139465
2 589 659
3 91 487 520400480 507846690
0 410 42290446
2 0 861
1 236
1 904
4 11 244
2 670 810
4 52 486
0 69 309991691
3 223 542 359792976 324713242
4 524 643
2 26 280
2 207 905
0 872 155718528
1 281
4 297 479
3 376 905 976655258 616534034
2 0 431
0 96 576580271
0 108 359972101
2 380 419
2 6 22
1 651
0 762 930467895
2 763 855
2 592 728
1 461
3 480 692 74652519 211861448
0 727 899904027
1 486
0 275 773468827
1 284
1 115
3 257 616 683486205 345378977
3 67 321 705267100 54289641
4 373 563
0 337 158959774
2 91 633
1 316
4 160 580
3 326 827 27319624 540525026
2 382 621
2 351 655
1 151
3 541 904 18393307 606882182
0 239 285981988
4 33 709
1 833
4 324 581
1 366
2 494 669
0 296 34527430
2 350 895
1 346
3 535 539 109326215 472542054
0 244 71416124
1 499
0 170 944323679
1 311
3 378 903 604103670 78522193
0 287 298514940
2 159 477
1 888
1 896
2 282 460
4 66 107
1 201
1 383
0 414 243980130
0 265 137673867
2 0 480
1 2
0 643 331378729
4 58 902
0 574 518753716
0 145 452883414
1 157
4 0 642
2 0 287
3 618 661 650028253 473914175
2 483 636
4 607 746
2 365 606
0 166 642288520
1 228
2 138 248
0 794 203715926
2 0 317
2 299 437
0 713 216986941
1 292
4 34 258
0 137 331628018
2 325 894
0 486 487199539
4 57 66
1 1
3 3 575 345694614 118722222
2 0 533
0 581 549511974
1 624
4 387 607
1 279
0 775 797302850
2 557 889
2 127 592
4 0 495
3 52 821 160716741 291459581
3 332 602 869467335 233160226
2 122 885
0 420 90318278
0 10 891343102
1 502
2 111 750
0 161 104609541
2 0 585
1 899
2 288 610
2 564 906
2 108 297
4 256 878
0 111 826823098
3 494 564 862409078 139620085
1 40