420 337
143706396 914880293 807484007 973736881 506912130 55534898 104963293 1731945 666789329 356989659 89222159 91264049 134212662 732262425 532631608 39023593 363355778 817638914 160136174 189781985 291431209 133137158 923022348 672260229 142594756 80363383 307915888 177827824 545650828 30886452 183783218 198874933 841940058 148239690 350780912 765217302 600717204 877867486 536776696 526926474 97517768 246060108 535596862 191107371 795857005 449057380 241890095 783942196 461561314 451444923 294841232 975770950 305500536 720366739 360120838 743385588 242985663 726450561 355991109 487521258 679766745 119337956 839606166 565854522 830158204 423117612 21627012 87056911 976612594 270164037 590666194 526286014 889636954 39152737 824990653 284926191 780785727 75899463 818134330 123361858 495825397 38710823 798957977 370338444 901135589 412247405 516299729 116428446 351175809 792449247 281770529 124323048 462114816 162431288 536999612 476258421 794955179 36952907 640814102 171659896 337450133 473453464 475916863 138753431 102000931 369726239 750538585 583252503 675108282 124014146 626816888 359869377 99289748 431489377 796360650 147276167 429145783 243749447 62530763 654360281 162649822 36455574 16730670 175143380 853126612 618958921 200054901 313617301 430903764 396095231 474577476 86830573 956698481 140968249 71830753 498994510 889123655 201864625 310757112 927296699 106584382 892415716 285275692 425523662 998788479 457528075 633061251 693764328 495789994 102156043 367577701 374553142 48813260 406050557 410424747 364002459 717374051 58557957 177046456 654036817 182183235 70709668 282772258 198192879 193255393 16112826 94572033 197158613 460561731 891110331 99408447 270692606 958193223 830751527 369375532 255894153 803390899 687480769 709410099 437187468 830018041 88078858 772281355 528724921 344421369 122744771 494779466 488528073 501712918 940969827 985759942 643854265 219443290 447965977 207523074 38893705 723011687 142284910 971533365 180978652 69316651 77689223 508601181 987581144 65393607 773283412 364629035 230587331 830666052 200625778 257710095 824063325 834324159 829651490 184600391 836578401 910010581 775773987 532148109 67689416 267743910 602968938 811701842 218804684 659811387 99586453 742682691 130248967 804066241 886205868 275397055 736219867 439325126 227316230 720600979 756477630 832685634 724941231 506104344 606250246 909303818 901063919 589840769 819348713 182599320 504958896 754509593 110367040 223983663 94097998 934254577 411052914 667419170 434816233 781942558 51798774 76969247 956472598 985345753 242178525 344040370 300079337 667195726 627846176 92571507 920041175 753130839 963901592 35150950 434598152 194249719 768850353 147484567 746299282 110983545 359878874 988680424 534912226 191697631 358660069 839395881 735884907 740821461 98494533 759805791 379834150 266023131 890073662 923590505 795558683 154162719 383284166 167663194 468751149 371824395 9093520 658319497 141627711 582993280 309306200 614057463 266723510 316794667 137148424 662992237 971207484 202922304 435774122 918405616 459151126 312281777 263681699 689065057 854475328 931005809 776960025 457659085 229487987 127056469 749208767 918711771 758074121 594078970 558125106 741218919 206570655 292267632 272485941 736404455 302200384 829005445 224154719 579230821 145648358 521163950 15083605 582037599 96826077 635717416 913225188 967822347 125207250 655653005 974542212 902030304 370502826 645657059 735363019 683694912 965001863 317770902 964140682 20069941 752090769 344641686 860638166 581826823 154922681 753580541 613432881 989296756 473459478 989952016 221898184 271077445 670241172 925312569 815230012 753075269 272250288 855022314 53720891 412548712 704767446 366115572 462365102 327425183 433403991 971942512 724133781 314528316 629017142 119448282 817279862 17511552 410671662 759634759 142097165 122768282 704939170 852779012 930749546 359418796 924280074 616442727 162647012 568544753 325824500 955908598 997149119 230911251 499719615 23321356 275452901 342389261 653470194 272186456 217267786 783823059 874473649 535309605 434478496 401441210 836588302 386317776 891172752 353294832 705834471 30190078 586783914
129837706 774651275 431474944 89811753 338431037 864584839 610671897 924782121 974592023 450119573 107301468 511784438 9045402 486011816 452703880 820448734 4223903 104850070 989492979 584602013 935323450 226604183 460782796 855932036 10154405 267273067 247578792 704787090 690356171 829796403 223835741 925049015 308459962 862116238 771700709 307428321 505260049 751740425 247846426 545372054 179334980 886523870 934212901 101601547 509647201 403833702 977990899 302506252 263243262 933348949 656931686 393449505 740401875 274423390 282521595 891718672 352393621 799609973 934720734 25236891 775531148 7016458 473147865 582380548 311818366 779907610 340812513 801047973 989215489 165944702 996091068 943919913 539046384 735968866 460509599 438681841 331548654 798934668 568639805 763873972 21132025 807661176 783327097 638318111 15831518 839841841 851829088 803586535 739674548 653052263 625103751 673351119 327949185 296570538 792244368 201616869 884326016 640720305 947905219 332717663 968413206 710664208 690569875 848258665 892069924 346577187 665128547 389632332 750294150 593168785 640350227 229525811 398871566 806915713 205937086 868361517 565025646 339575547 522664046 467096423 925062701 858918204 425552648 494832338 5814699 910324371 728868570 303596540 409006755 661281103 243733563 319985695 443345685 21962199 467586537 498101098 121287677 577197164 60972729 812537035 45477706 514735673 240356026 606812016 329243829 415806422 12286501 872714354 166085135 416020937 689417320 199676898 91100401 759028460 926660785 296710016 218686911 749592428 837520630 664720053 234462363 278920104 781168126 102208601 147787838 738649953 626122339 287882729 59237954 930715386 872624887 281175476 238728631 713108288 95830394 962397068 660000755 675794213 366366463 771906566 860758957 266682937 436855723 575356023 616098243 82290116 432364915 477338541 604888618 842514508 899603714 480992445 692392859 986199130 542983901 46979277 437765115 6675622 283124824 931233869 827105450 437322963 88886410 498347402 442111976 462744629 10963962 859462345 556474112 545182483 288312427 781843131 351000151 99546347 614053257 223543961 292769730 587597796 374564118 284038622 521798899 476481073 453328629 189957587 467821298 275056917 769013430 975126901 132827956 674876813 242687036 428898304 953385842 568262396 449752571 886806212 45390496 547084728 408962919 688528758 801687553 3187531 327656518 28370547 834165713 940640907 935167981 819583890 314684352 24346432 980900560 745541776 159344660 232531457 661094625 421642324 982273592 321846279 385193897 651226135 789965544 955550508 985324003 776633204 236300843 956590149 989434102 499904029 525382661 772266880 774200352 805743313 847765577 281995902 960855419 376732901 560741570 418755702 596861662 749804770 600973268 212659018 553386385 715102533 444570549 658218796 770580553 130636813 345105196 533154309 251289562 603345546 305419032 457606031 320531691 784889937 206720811 524460692 319533949 553167619 411926612 224546451 230198511 370322068 679523293 954236811 66664244 376385975 938003670 378099336 957044039 19650157 197259160 278714945 833210820 536984805 424201319 831909793 239992275 593719438 942747730 284634779 219971575 911808638 294145779 32053623 503210201 924601802 490185634 396033915 293917629 135459623 372089602 198508478 627557534 222341753 70663570 929490619 755542931 568891099 113705797 793804832 95522461 284109724 21091564 931055428 915176248 519138106 922772031 749744875 747546484 295969913 318745551 599804683 608636240 74111007 337959438 504958542 455947010 959495390 527851781 865861580 525277705 448365111 336050380 87507728 248615615 37885356 195100114 752722393 122102254 25060960 694510263 415579731 649851603 260050376 51888151 169171116 371577628 701803711 151045968 25596274 443094009 283843429 469464925 731083563 67714581 373043968 417144864 375034803 57035893 902019419 398346031 738944612 668012290 314794038 905386995 924866283 605264809 235423501 613150435 153403723 687869686 71668379 79712885 793005540 995577782 351229784 522121150 901128740 493616196 539181745 726014114 43883548 376489112 227533853 853760819 653091422 430273614 548218316
1 285 5758149
1 416 250252811
1 251 739134802
3 347 146
2 293 302103054
3 215 133
1 367 132090067
2 357 796350817
2 203 933544113
2 96 646894091
1 229 487363055
1 406 282538386
2 207 884789479
3 349 133
1 340 352770670
3 78 416
3 216 63
2 118 955306175
1 370 632611797
3 134 39
2 260 930249451
3 326 316
2 377 280512078
2 136 797972092
2 110 184394410
2 202 891509939
3 365 92
3 214 67
1 108 21301377
3 218 385
1 152 247407104
2 30 484849819
3 356 13
3 286 133
2 90 395981549
1 333 490684132
1 98 315354467
3 392 212
2 127 148560538
2 78 59024534
3 398 379
2 384 733190467
3 365 72
1 327 828088806
3 281 178
3 28 319
3 246 98
1 374 529414451
1 302 593886326
1 322 675291023
2 179 279332415
1 287 631729316
3 264 133
1 371 325663731
3 125 420
2 335 490177952
3 355 140
1 146 542449184
3 271 339
2 326 694522866
2 80 879829191
2 86 791673274
2 90 786472751
3 39 8
2 404 430774636
2 343 711506656
1 75 112825748
2 103 75184530
1 96 49978853
2 81 882783114
3 420 242
3 258 8
3 366 9
3 202 157
3 416 272
1 227 105619199
2 231 842347505
1 137 884521360
2 13 483985587
1 127 841122885
1 257 740798529
2 131 125402983
3 139 49
1 64 211719028
2 375 318233038
3 144 296
2 390 879560071
1 70 766259416
1 209 381216686
1 415 115965716
3 29 317
3 339 263
2 377 834753046
2 53 325905673
3 233 228
3 101 266
3 223 47
2 132 226432901
2 364 562479046
2 16 125169143
2 104 571770087
2 124 819348189
1 224 435117440
2 350 131975883
1 21 922665866
2 105 612183849
3 280 211
1 207 895258673
2 289 773836833
1 92 289374319
2 340 441606425
1 212 610340633
2 106 394532524
2 102 94671704
2 412 591680970
1 28 889092104
1 258 494303665
3 417 92
3 144 405
2 39 485007327
3 239 174
3 65 278
1 264 263191454
2 194 99238310
1 331 283177915
3 284 141
2 5 62586364
3 226 45
1 188 675035154
3 260 286
2 195 718004661
3 119 170
2 205 189881642
2 3 413211778
1 251 964697635
3 272 402
1 116 542208225
3 397 241
1 95 362594099
2 408 392858829
2 143 387044832
1 276 740941063
2 390 862013761
3 398 289
3 63 270
2 41 877103813
2 80 397592400
3 306 78
3 45 297
1 300 725628242
3 189 398
2 237 10063853
1 103 165599116
1 59 335462265
3 305 87
2 352 973908067
2 367 889024557
1 403 267864577
3 262 202
3 336 399
3 230 38
2 207 850887896
2 354 860936059
3 243 18
2 15 376376097
3 203 266
2 76 761928970
3 124 38
2 227 846871665
3 279 293
3 312 64
3 331 122
2 218 162703187
1 256 743052685
1 68 99652659
3 283 183
1 408 805626876
2 330 397750364
3 382 418
1 359 77108871
1 373 413101461
1 289 554109276
2 308 190036629
2 137 370943734
2 97 89632997
1 5 65746094
2 161 313657694
2 358 75636882
3 319 106
2 4 154794949
2 237 255267718
3 185 152
1 139 301962144
2 375 427606238
2 22 302733054
3 344 172
2 81 616071314
3 160 379
2 59 316953912
2 199 677724670
2 91 75652423
2 175 78489099
1 159 908005611
1 406 603615609
3 198 96
2 399 703030956
3 315 127
2 157 558727782
3 189 347
2 329 42865066
1 202 44831469
1 260 744664590
1 323 768210291
3 158 351
1 143 323490243
1 188 762444639
3 154 202
1 5 680525060
1 31 768317913
3 324 77
1 55 380499412
2 389 416678609
3 142 102
2 65 664627780
2 155 674292452
1 331 766082577
1 115 244425038
3 371 391
2 12 4190309
2 236 830581960
1 140 609575998
1 266 879969133
2 240 871340494
1 83 181634925
1 389 667572614
1 123 986874232
3 333 159
2 117 116065881
2 137 653887515
3 149 360
3 415 52
2 362 705231806
2 86 422983346
1 36 26470914
1 63 211388263
3 229 194
3 392 299
3 140 123
3 292 79
3 128 224
1 410 221845192
3 221 359
2 370 722645929
1 341 67370343
2 73 294739935
3 73 98
2 390 37199253
1 317 217980518
2 129 24156450
3 339 351
2 368 438533616
2 352 947184639
2 2 612145448
1 85 988928540
3 375 214
1 111 347958627
2 199 639186190
1 273 362304664
1 379 936514674
3 118 242
1 68 553611667
1 402 163424513
2 214 21494146
3 71 41
3 303 34
1 325 265839854
3 357 102
3 401 151
3 223 30
3 235 17
1 196 185458042
2 200 303754497
2 166 544821100
1 176 518879467
1 93 138377175
1 413 311449319
2 185 426410444
2 50 293196761
2 356 825933639
1 43 898008831
3 326 222
3 375 114
3 406 134
2 311 320751209
2 375 614649978
1 5 854445152
1 74 496028602
2 382 536454428
1 349 107538693
3 327 61
1 91 282961197
3 349 88
2 6 939746255
2 213 22466913
3 236 190
2 420 269941517
1 210 225099811
3 328 129
2 256 491737170
3 326 142
3 87 343
1 255 489994426
3 411 201
2 17 182640111
1 62 366424109
2 198 982785146
2 84 472452331
2 100 127595500
1 216 435571450
3 419 179
3 382 49
2 195 960273705
2 355 429827579
1 14 158973837
1 260 750218475
2 408 123795803
1 219 371925283
1 294 8505975
2 143 834858195
1 13 973140262
1 155 934824156
1 307 181179357
1 159 863173401
2 14 876116329
2 30 772392362
2 237 607982572
1 224 921686333