874 221
817609646 512965573 521724489 141011335 174369343 602372488 484839417 455328882 842528179 80107203 740936678 908934144 360653727 748506032 781129701 457193940 7389280 92501647 436512871 58327854 658399941 391555299 690582963 118223330 967341944 592678702 191410738 586478692 202275485 570626729 909376487 309494954 369272546 524770239 373923981 946286903 163251768 40168827 127670577 660125476 337844164 89570859 403877766 922170123 115023517 160798972 717385643 425304262 308675601 450038795 991075541 506629916 6766023 595951994 472850140 851881011 310076477 427770885 314440170 79424081 350397432 393285359 160437085 490716617 675564671 838600795 825095569 83044000 510835830 247538274 187684689 364503783 824824788 305218441 81675575 715149761 654912063 799358183 635533944 986952876 637112572 318839621 786233240 546560916 891801392 160789213 659950156 393621156 661758033 89043641 741040219 88257666 413625015 984551535 95095557 797240927 955243729 78690426 433686371 422452450 62988323 675305242 679294888 794383255 330572950 149095909 347634824 298455660 224686590 706611131 473448669 718004493 30902712 289855514 893698705 169539325 42565391 991016446 331178287 514253269 187427226 236638233 723438091 700294350 576821965 738614920 511660263 12306750 681269800 306636815 628814024 107499978 517371247 571840693 757498542 796008454 558813798 822211479 138284362 157126999 408507688 853093275 95805053 770268858 419959511 425646041 661156467 822624214 770329480 966549952 572308711 311726132 240366519 503937051 763391715 689192670 112372494 166040631 691975576 918195288 163551327 893651959 564486789 544517232 969730431 980761638 204315389 561793986 30464722 261247909 421171100 381697307 814254046 41702006 334073529 271009514 101980757 298768584 959127198 55372154 757755122 508421202 132717878 361106865 370372203 615481325 167898459 18828738 485079822 694921529 21685384 122271596 733058095 855110265 349379862 231048980 546390417 517633851 442292553 214105224 721385781 759188314 756300971 641981739 645123469 62987410 668340234 972665550 391932025 260005412 426355856 67780390 821810794 722683123 469740238 447814340 428970 255049945 663746022 337831919 189305010 404779245 301953695 537361387 986333236 524202617 199054751 266846308 527912260 546083038 909627594 970682341 445128725 180413620 707897827 586755605 588010477 742944575 789890250 652981825 45878142 480311659 261398447 775142164 484560287 710647774 658992595 266820031 753491378 80945819 301976099 386356834 181173026 722503103 89064047 453928860 362188036 610033412 963786422 698403536 502597301 436777939 505011453 292967523 752963295 385507886 263758438 178041849 672864741 932477828 514395133 937860528 461273877 806395125 435401196 319275358 16124811 143842339 987342252 239788729 512482581 969543873 332723034 694126326 957393456 345320564 445164197 408622858 507106218 711264251 757317185 817295609 776990517 593349808 800868736 608064382 498140807 152983109 654470121 267556061 995770560 251186669 482874588 511792556 544915189 675632180 906995133 480710206 88706425 690764387 779522603 857496695 976664446 356427220 983363465 43039273 266576738 562681187 457491373 907882826 150649051 102354410 441625059 447859038 509799998 441531842 963655924 129852325 349786603 675486004 394476836 233185688 144254656 753892560 744588959 849234244 293057538 859921073 169553671 158392299 705665479 61904675 745719566 857610418 458936672 390724782 906377662 822614477 31320634 693043679 463956640 949921667 338046046 275094088 743078039 238534290 1813761 672720446 167427453 399309817 506814034 869645833 177038237 643431468 750266623 807578316 990765749 408475631 91507274 980938216 717552229 325332707 103940529 702911564 80846351 32654552 148099560 764717201 802571808 734895139 757107156 266573999 51948843 948413386 696364074 108036393 129131505 227884248 973593122 558670660 337433375 428230139 581292863 303933302 887307233 227837116 328538585 856954264 770571923 68311003 222338940 287345033 97935333 832642903 329024848 531163903 417260625 304751592 353600165 117595624 342705662 606964172 203666327 208796559 244392953 147303622 872246863 138429503 622438913 500627394 907999181 916110110 324964692 628102194 953350277 531458329 452871656 440708248 859675863 965115974 533925903 725798620 569306938 778597363 898492988 909992054 685597484 296538080 67972752 700908821 466669094 786010315 47526546 199969187 205155610 448246748 158248589 661268878 902884175 673813939 575744480 205133749 792303052 185348062 360228903 913023024 141002887 355501219 692623323 909358827 987559661 977128938 935299524 658828100 857580973 648294313 167755494 539291338 635050047 132819476 201784245 491622061 767808001 859618983 129158155 736774888 219845722 866759318 992973847 349782007 356935868 104096602 226906639 970871556 412002124 44608082 732324364 713205531 637407827 504711256 910549874 76073905 517745577 189214207 433797663 521424736 960933545 80003350 971518489 770498649 410143665 222528572 891770900 599861754 929689370 955393859 358337238 115619360 958019295 543499285 435295829 413141173 938864736 342698785 226735726 237089016 451845217 850501731 660595349 874578069 578910504 54838487 570184454 869440279 22277065 9002363 442246307 399423601 417551434 13406396 919489650 395950160 501474635 377445212 392782680 595378199 809781979 106794370 512043515 951542124 15610206 302860463 440922237 527927848 194237015 251817643 555479904 179507592 76396550 974774449 239849497 927541671 529241638 63582564 707155353 15896286 198844327 635932300 196670486 105922596 24940279 210512176 598769457 838562228 124554853 294256729 679924169 764804443 714633448 570583847 158912648 224877144 161476360 469513435 860719584 20166411 511151778 271092047 158705177 458148340 866568879 73069676 734245285 183172467 676579369 30804416 291370676 416860028 551825423 140143805 950943562 720433129 587212648 609472470 46629237 450041843 78882574 165190123 222360459 836639648 952334838 277923764 58757819 822396346 381850576 159286925 761413336 543150878 531386645 398835314 196059086 333153756 334475557 85476398 304606405 130158867 716104268 100940185 951976557 614288351 853801957 840776268 955620511 807045341 590768402 64672388 232337625 493507034 766676371 335586536 901006731 237100459 693581947 64493513 88915480 485471898 180664965 5816089 626644871 476677182 867067550 879919835 616170014 311018447 845698302 254118478 849813853 288658699 186619457 509463975 215866194 853652402 252859851 835396865 491138985 610303664 525522254 112075655 533740256 13544906 545967806 565692551 117973646 51140396 633484689 17458174 816310717 735450808 747360333 973529317 24021342 644684516 18041604 356105634 515160220 617720355 844285664 27412728 509288571 661464243 952337002 521111486 760927577 326873404 37642223 892056787 429242593 734455985 115232228 332643831 403798616 30229020 379136036 787916930 403298541 193757152 386938501 806803688 213595751 166198205 822872993 880450758 988057286 278336037 389761433 590266146 780851578 923132413 741456904 502612283 525813429 884309074 39406459 957110907 577356222 404873628 802031947 500987098 243973966 99134801 951549309 883523312 685529206 652107462 668468201 850437652 654931384 914124709 705920163 12159530 279543747 661257229 823613244 849038333 615742282 852200602 15183851 980564789 900323017 886918109 299952573 779888854 740254458 534349645 248830170 771366162 289214576 139998088 744051285 582255531 721516869 774131725 639777234 45514335 891098432 863260226 379762297 422521994 377046586 960597527 609229914 284393463 773100223 31647879 183638746 325652691 535099666 537816997 298584212 482671907 162456324 133652433 707128542 315825542 94543627 685092615 95657453 886968563 679540404 901449267 6875154 228006585 643451702 930738585 189758207 813310988 328615259 920777081 317259886 803297546 766823607 676975785 780134678 912120105 879117858 98708395 957557555 359172460 914862826 337345847 306666068 556447349 599806046 465313618 462995293 37848224 867128139 614224333 534776303 656099827 528565186 700236094 947875262 439615944 376505656 486967278 903882211 286841363 27335617 787480904 899828148 187822609 316766358 650748171 374045389 769106094 415766666 576698716 234198345 377442419 453715833 231757802 795964746 445879055 976181951 590397265 708576168 901613609 817045659 37697879 407923283 520476673 933327646 455994678 68362904 107817900 106914097 480983403 548696464 877061854 878103826 328370997 497132310 117510061 811460679 343653537 226337545 960411428 918945955 609785732 411382799 179401036 65951514 125535453 218720002 483154494 135544406 196758440 417731645 280846232 908110202 748782867 777566130 89973509
0 613 359456552
1 834
0 24 836475503
0 518 159154509
0 589 720497232
4 676 861
3 162 877 901190975 488592111
0 682 262446160
0 701 471932421
3 673 879 790505392 679746930
4 639 713
0 442 437513005
3 0 610 220156945 346146625
2 80 350
0 763 430468614
4 228 575
3 0 275 608345922 814945306
2 404 775
3 126 436 716320231 710881997
2 493 614
2 277 352
3 0 446 240318531 621650874
3 499 876 255798492 19271307
1 14
0 353 168135682
0 380 623048219
4 99 785
1 428
3 260 291 939397791 159107391
0 500 693547175
1 805
0 332 940138025
2 105 379
4 696 816
4 289 882
4 10 463
1 107
2 575 642
0 786 891555237
1 399
4 384 790
3 70 787 946188540 990908916
3 748 863 60219564 485391154
4 136 450
3 75 544 581691247 308827611
1 513
4 130 519
4 275 289
3 0 210 654141523 562603676
2 0 334
3 408 880 579263030 291378646
4 71 392
3 646 787 55387470 67150423
0 74 563264471
0 650 882969811
2 862 882
0 494 407236562
0 789 938056878
3 166 653 374103880 483501044
1 584
1 786
0 234 463094503
0 449 516800990
1 582
4 580 849
1 347
3 256 449 872060442 493864801
4 283 882
1 174
0 351 518727836
3 680 739 260345361 356412393
1 42
3 54 853 523578551 816761252
4 7 610
2 88 559
3 734 834 869682050 276101252
0 651 650006304
2 0 577
3 305 508 94390658 693874838
1 67
1 474
3 397 536 375415244 911203091
0 181 96040250
1 707
1 83
3 0 851 556879557 270975588
0 759 615850942
2 636 835
4 447 880
0 304 217445942
3 235 703 188579693 405925009
4 108 519
2 309 546
2 2 501
3 261 467 594342455 536989513
4 82 780
2 139 732
2 57 559
4 148 321
4 336 534
2 237 622
0 155 611000153
2 0 755
2 343 842
0 8 913975868
3 566 807 329206516 955300173
1 561
2 163 800
4 52 761
4 513 882
4 111 590
1 781
3 259 881 804996098 564890287
3 375 520 191660966 519581945
2 488 733
0 432 357834066
4 62 102
1 304
3 131 533 427305671 547575194
1 861
1 519
1 358
4 188 596
1 647
0 762 137902264
4 313 878
1 203
0 319 480902019
0 565 233191248
0 183 543653064
4 586 769
0 232 574724380
3 0 723 250548323 669081839
3 0 541 938324420 54141867
1 439
3 675 842 725574599 235152093
1 512
1 523
3 421 598 967452292 245247010
1 157
1 192
1 753
1 601
0 626 516866798
3 89 504 85752387 806335469
0 632 29675836
1 482
3 281 788 754504995 235216009
4 114 845
4 663 714
0 96 40080810
1 662
1 576
3 158 708 783339729 812377058
2 687 717
1 508
0 277 797857668
4 154 284
3 244 298 304045115 501233639
1 241
0 247 913097559
3 0 773 222118846 640915458
4 82 305
2 54 874
4 0 206
4 262 874
1 349
0 788 352606362
2 55 282
2 504 688
1 842
1 332
3 0 458 788312222 861211463
2 167 872
1 765
4 232 386
3 584 607 184455241 277289194
3 258 391 880817945 449010970
2 261 826
3 633 848 908999618 193590211
3 124 276 878468673 100865445
2 196 795
3 604 719 851908178 8410837
3 356 818 698747325 631615401
4 523 806
3 405 510 7238587 201856113
2 400 829
2 285 509
2 0 633
2 416 871
1 298
0 151 406218898
4 21 856
1 90
4 453 820
4 198 561
4 699 769
0 474 586709119
4 276 368
2 156 513
1 369
0 213 337853568
3 173 871 71354068 307931340
0 120 754501719
4 259 772
1 556
3 299 871 504546208 931245791
1 405
1 821
1 820
0 601 226130384
0 445 222104224
4 32 151
4 402 502
1 674
0 765 348644326
2 734 737
3 0 674 383271680 896483294
3 571 574 422761372 464567622
4 247 870
0 337 377168177