614 403
355780244 250607319 89451283 246748767 469323646 113038441 468430453 375316315 345344276 706527801 754631546 514313572 266535171 831580487 505540134 808137204 924445514 957500834 11488322 468488274 633862773 367042173 801098611 529547879 741750833 674417724 305880204 659166297 108464907 103425096 188333069 18147339 821216366 893716716 943760693 258598062 620310272 963226821 387007327 538240566 109149974 802253290 685770674 457484687 457284255 635328969 823622011 754062223 927310189 196429188 242297925 433495437 582465780 19558504 458860824 736231068 439707384 224492335 239924789 279061412 214180761 400263584 574548770 320461916 484725316 958976004 231050702 815790059 473270982 574195797 957863854 704782867 380621022 622834372 491952692 717118204 303883845 9101447 558952239 695141341 867570199 429357098 655879328 745370205 498387703 264674166 260372314 473874516 648631394 511721814 306054267 614804259 945313765 159712810 37124060 887522883 141002922 603690997 466267430 959055260 687998789 92278476 587244318 432440215 746540318 778058228 239638151 794071581 150608141 632981007 992538477 752062740 26326117 103279109 576121365 885733406 363181018 151065196 903674740 62962537 18426730 772727876 43670171 120633275 576008819 576120784 743878860 535357549 111760901 562790530 456592823 603843733 414739644 878876566 998856976 71138251 221421919 734306699 763819432 893814407 663460951 690472707 484232448 647387189 48111471 922642375 171732459 588186173 893111422 452007353 866126348 692779229 542341655 187935660 380075297 342943248 571154024 836151123 371628789 219038598 241601318 607922550 131598781 767240162 964482092 542588491 500209076 872613810 951354842 266322248 773625518 106822021 161015562 345550283 570096816 68769712 953370586 565180234 476409078 815759545 950771803 36526610 634141693 935556547 138971729 362681921 737292698 147420702 397026001 727629474 464840210 116826418 535523667 670516672 68499152 402838906 197467913 887900792 550844844 794421838 320226636 537727827 490957418 126853693 704013146 449142084 326798823 665449437 120789287 791057866 469560193 492497052 280384744 634100975 918801895 894317452 55375847 124938477 690146219 42808265 572341407 649393210 505303350 775266589 988846535 421332100 156125424 368626552 950829024 119033089 395505926 801676593 369224538 565914447 379939647 552021164 250725814 406071477 862667345 254691218 764405336 91318455 18101377 119885470 329501155 184274187 361946632 415772061 279532427 543805037 286360158 54047528 88576779 326802552 686423340 753487924 629422853 443669519 149079581 353063986 153807890 656724280 939548493 380601253 153063926 396516814 311813259 183140287 962818409 950921384 916238253 904867283 826015733 682597534 683933932 419865708 373703593 567796324 259847099 254295686 853657493 922278727 712029637 487311234 344221867 545697184 142090391 913312746 687200422 226327434 963464989 375686062 971716486 572126518 398885000 794339266 226814262 172249974 685345704 29486668 682608298 719123402 962615716 359098472 354782568 814733637 965601696 385283297 708464130 832561858 420953245 549767725 25491940 289122965 701351140 636007913 830396706 176093106 261613127 793204260 201692222 737367877 735369124 340652850 795243571 443637188 97170900 990732307 881061624 840139395 598931082 684101470 366713726 813246849 370122395 450480861 641639063 632744524 397439837 694279231 411781550 154707860 970931216 361204583 335192432 380621629 53798443 448048325 713836829 600550637 204012338 276544086 279147882 576097062 68640679 433214447 506346954 364682635 802419903 599743366 7178799 37170082 112760163 414751384 598467493 379645206 699747839 465863800 447375548 853714117 939453693 642708087 969050387 270030906 919599848 188468299 645885907 324658765 579578938 375883132 953906879 758951563 919766821 767085252 890202461 376385815 215824175 803951014 725400552 268677445 453904752 897858714 788316835 522271290 867963924 858404063 589854188 759232594 184417858 393716289 486465102 269440796 980132637 634515453 505186523 399406242 804463324 430204989 477212848 47227416 740890140 288762926 423935195 167373311 430483016 972535594 287576050 869922798 678871634 858756542 837357967 424256985 649690982 251340848 874057905 643779841 603335382 12221633 423447848 292413278 212522636 498070268 826093630 141306322 219606653 121577548 945611581 158365611 513016048 218075773 801869423 599960590 264205807 969646089 381352729 439526524 879023570 496457517 207126163 176454404 81968748 135813200 221964686 684072097 299040612 418732754 369661118 985514546 826425745 904458699 433654363 926860648 84314227 394179538 421171940 547699925 146267416 706884352 956315764 8546808 75194683 719802834 305042860 584018409 382567814 806044116 703372981 124001153 588226069 571403432 971572259 419006515 558985222 474768512 756352820 330238468 23787898 732955436 416005761 557950770 237587025 680168167 952507004 747210995 610659747 975554412 914558510 132976127 326880692 313029425 944017979 319065751 992377364 780616854 898837501 331637639 412208785 679340064 851819968 54436469 115904103 342511937 539760423 442324819 756855159 754441150 173347946 15794501 130481906 375220597 584882960 628268632 245991172 43253344 808461036 704199701 920445918 809657689 421436733 606542980 212374465 864801764 732218754 4731067 957048301 174267073 642994078 230632039 193865292 191072166 85467990 644145052 869862174 321313704 889650750 112511367 320296319 276064596 759107929 272998504 143725132 71193828 132110216 233556053 201669297 366905624 980456615 490147617 943478714 522150660 629803389 963373353 705849130 15523829 485773178 448071767 492708035 204968543 848602264 44651950 95078129 210598568 833323339 874523458 169405735 56626194 252621177 481457817 483391245 459640980 918259643 724579400 65384553 851474885 959439693 526473440 678456550 326219595 312171772 625428917 336881198 821528157 759199539 489433952 927337060 406484807 69299216 89147790 96497736 647028232 429706992 289103445 513908680 660076655 238048318 115418656 942912198 643530022 609252473 951976590 707658773 964740843 140616528 583361378
790480880 286417525 648321925 666839440 835410043 768772823 709054907 959896516 305377672 912479142 51749007 938048662 981744464 631619100 769964040 862891407 598626809 825327720 781600084 477516666 242170940 843606726 776067024 469103412 592995965 511154113 546398631 612646618 133264583 766197358 979578190 654423286 670464714 73547576 727670155 223686109 687472206 313638387 255599487 402696744 628194468 991831340 290602462 121675256 918738424 833956436 539870040 44744136 677993641 860436704 422537014 236712726 972705323 574129666 610854159 989929520 986778205 179070179 325025725 962272341 650715868 395889897 574163746 889388099 291188361 892382198 761578658 904982025 167745883 635418809 66871264 187321213 886711772 378519480 376104101 820972223 104754750 925341726 86959583 705988033 122060855 17393532 82137678 576386085 195666303 445052269 909710720 161985677 872722971 90194705 852113452 733975732 644033726 649646921 175283506 308697491 984305223 849695798 285680477 593762463 89931383 186061451 16242102 166717859 487724638 334987935 552788847 658898566 818956536 118966910 880761751 799633129 802719579 300791605 142768416 405841534 812833949 76585412 393646118 692658229 501810278 802800778 922316727 473534474 815061251 9621146 767079548 976648335 631097475 19156932 364778575 486747299 237638179 370735043 678920026 694370782 968632894 979200040 701761085 725613244 669240695 398566253 527277854 291328756 540452620 329550559 869387080 839638998 46129089 744769384 566507757 562165230 812700259 748900090 949681266 825395108 103318300 72256890 136581428 699698877 925799082 678747916 273208473 655155918 798313515 476556442 237386777 968808556 421343779 427935166 4219497 719391886 312113925 260069666 600670974 905917109 61924198 724947372 313378089 418448293 409951862 702518608 85224551 991464912 883862438 638836060 680830967 638947759 567400477 241873532 394810230 362964050 643661774 443144615 111735523 512249629 494510522 860176279 273625297 602619481 859533588 367739847 449500790 865724449 156568436 734770878 855698635 262157651 45538078 101004277 359274149 427192552 996390494 242807330 225603882 555958848 237179532 239646608 125832694 401773830 412565551 567156319 435651478 111664307 84321350 458100800 352194242 293875947 150696997 232400038 965484358 50495820 950636698 354134582 499944078 773058384 602974052 435959237 51200015 818023976 818521982 752469909 181710256 617457249 422409667 873743057 202301223 559844260 278774950 873624750 402025275 990809629 634798154 948430646 668617276 93824953 724416267 435514239 818855734 923191761 152391584 320557510 179224436 124502749 132360310 608958969 580217230 712240928 317966001 705394642 533717414 365188449 34822255 458434478 412777453 994349882 685025196 641237329 426834214 849539544 425145339 546828906 602590397 845125551 689030290 276024690 651370815 298342378 80969996 890349706 71742220 3353657 665736012 455267599 996883214 974111943 104644216 279797109 658106356 266429061 875187516 99815786 49475085 354888506 112174939 289862530 231772832 240286600 134258193 716840443 686357547 905175815 104536244 10666894 951896912 174925979 950428340 124287417 928359026 366829257 929843490 962879963 326199814 401042530 613769896 126866343 346068688 986595042 225206129 301449268 183697178 303698316 202995746 836904858 862128232 768861153 878451016 524343181 89446205 660987639 63363440 420654106 394220779 95120154 394408642 36113260 7218879 77932288 307447951 165903433 869272704 104309972 601815551 268126203 626352192 296972344 180393076 660957569 257825597 712293034 431913540 26639139 537298577 861720058 403593875 754090413 281382009 660381020 537913642 526076198 939569029 317621804 37283244 222522011 197495452 924136622 857515627 577371751 661615885 217057580 474539707 280715371 206782769 807493966 939661301 262064100 482548795 26770508 414655090 954385622 87044488 572127229 474590704 640122819 650245024 39000437 212003837 38737459 644770813 529209910 425980898 780352401 851493117 901495454 640766470 542027746 647709410 402164483 316233325 856586476 134680265 161413027 974339112 795854774 331109579 867227635 348959769 61626855 404108372 255753749 39995163 466945760 270763686 797781159 108043205 408573883 345647458 29799284 64282627 157380248 762511094 371463768 828313283 164471620 879062111 37093329 183079069 181734566 761044844 506245803 869393158 947796918 215707836 916082044 365053850 663641983 291411924 830753910 556215659 910293707 918845063 172954704 82967579 597256053 284794329 381787328 474439896 417805157 46709437 481302926 953956253 117725608 986758059 649668777 418435733 679537481 713632361 562378650 401599784 26111455 83229899 954828866 191473916 947349321 810293587 522788678 725389559 430452622 669835458 683274844 300950724 789591906 308443133 870396886 164254553 416321189 884608864 214549880 623465395 808603435 988142820 152922613 307931932 643889822 111057849 80373357 438814196 263719942 522226843 308272581 217380820 746594289 82367033 34091117 957029840 630487254 475824487 431015235 618551493 431709418 876228655 604340621 699023341 801463039 609683799 673540668 420543028 814875169 879717115 987314602 278460834 424478457 819238733 134937389 422989478 710749710 815285330 540214539 172518786 659808572 430935918 780373964 458284003 35088330 971630576 791972943 21674398 648590217 45296515 936118073 294940049 975703433 213225671 547620730 411121782 989868391 398775836 999426829 531688756 468647824 530524850 741391940 112724804 85113248 593091478 151745730 138933832 858113818 58119734 862631170 261526531 546185357 293608795 456584191 453399280 442199381 920362602 34736495 708532710 185761441 696932109 857469263 486032900 78190203 801684689 364467687 11420983 100256864 219993992 761485998 867089253 549652576 421376343 715501922 46749311 795129402 9889520 609750608 801339197 863203650 812405381 813988699 998845357 368863763 959174919 533713197 303745861 69529830 683827628 315881098 767539190 570338204 93017537 684001535 128374462 884165107 281305702 516008851 188525423 867686931 932954905 913558625 457430778 647960862
3 273 600
2 148 90422771
3 357 517
3 74 558
2 22 633750718
3 486 287
3 410 273
2 243 835324247
2 68 534171949
3 379 294
3 437 216
2 123 652311527
2 51 149298377
1 312 579978892
2 375 858749134
2 152 900387661
2 438 434989210
3 579 193
3 509 1
2 295 705778965
2 558 172200453
2 92 759632773
2 594 329379985
2 48 793407005
2 337 468880267
3 349 15
2 537 39632499
1 454 372867512
3 412 200
1 181 354202338
2 186 249510627
1 346 989302444
1 414 916373849
3 45 446
1 604 956941450
1 390 147758283
3 393 151
2 450 17637129
3 424 176
1 71 698584739
3 403 14
2 320 179756776
3 432 254
2 127 700454673
3 435 281
2 324 455966162
2 107 420247458
1 532 417941203
2 241 145181297
3 314 219
3 601 438
1 503 71831900
2 142 241650771
1 283 539653544
1 105 397863077
3 505 300
2 567 943981739
3 610 133
2 485 936027042
2 362 733818604
1 561 387939255
3 380 235
3 59 431
2 526 778013794
2 283 379570902
2 565 882336948
3 326 119
3 474 274
2 550 653278831
2 314 18567908
2 173 672440128
3 360 604
2 446 553428373
1 512 153020223
3 211 310
3 605 612
3 329 80
3 529 191
2 219 118644475
3 310 252
1 98 933722805
1 225 755087454
1 359 225091920
2 473 204117119
3 189 82
1 303 808399001
3 14 180
2 253 355947
1 576 152072386
3 459 260
2 541 109351325
3 594 415
3 319 266
3 342 253
2 236 981378110
3 323 145
2 300 497977827
2 358 361038907
3 24 606
2 235 815402699
2 445 744611522
3 599 132
2 534 134630875
1 535 322578106
2 427 255237603
1 509 368728777
2 291 264185482
1 160 761647727
1 282 825923567
3 587 239
1 127 632691472
1 194 975658181
2 298 425890555
2 170 166776605
3 363 67
1 562 658513578
3 59 256
2 341 480833245
2 15 490424212
2 31 339335768
2 528 539714796
2 408 440395608
2 279 655619359
1 499 624277416
2 169 206658192
1 155 308517624
3 317 497
1 413 653594300
3 416 287
1 134 271047731
2 603 867628822
1 60 577320436
3 283 190
2 26 572534752
2 477 847410097
1 285 623712680
2 191 432179660
3 501 165
1 506 761674823
3 494 550
2 113 363071715
3 182 557
2 334 166237735
2 290 129314144
2 569 934988242
1 11 979226332
2 103 962215990
1 155 840186852
3 447 207
2 337 800552666
2 436 181159733
1 549 960078092
2 410 8100365
2 109 811746174
1 544 301540712
2 359 334550055
3 156 444
2 26 643914973
2 489 332062578
3 505 206
2 476 529793703
2 213 208758775
1 493 736904700
1 252 332873654
1 11 610927145
2 336 185951746
3 561 40
2 209 250890671
2 327 951317371
3 440 127
1 528 530068802
3 433 288
2 44 466796765
3 93 339
3 203 602
3 486 249
2 18 161572118
2 462 878203804
2 457 29679408
2 367 961372144
2 240 873184255
1 280 218551959
2 67 395447999
1 424 238728633
1 229 30472171
3 213 100
2 168 786535552
2 538 303586777
2 414 415834103
2 73 683995589
3 99 20
2 489 951926136
3 578 273
2 442 315284029
1 402 773499037
3 581 240
2 412 661903809
1 408 433960288
1 466 701838265
1 467 339858871
3 521 268
2 98 803873042
3 7 466
1 72 601962405
2 1 610795484
3 587 417
1 29 787559081
1 221 52151082
2 349 962699010
3 433 277
1 388 619580863
2 357 953255123
1 584 203571848
2 142 67139594
1 579 273004649
2 174 725618331
2 517 271435808
3 562 23
3 551 27
2 482 775881837
2 4 280832703
1 535 662169262
3 570 165
3 578 139
2 158 909879410
3 88 422
3 432 604
2 317 735583909
1 33 949500611
3 499 108
1 551 614837378
3 9 361
2 600 172928816
2 198 370780334
2 279 250704520
1 608 827034186
2 493 176368571
1 440 907431919
2 279 347846240
3 360 184
2 169 104508290
2 171 900557455
3 432 47
3 261 391
1 389 606243442
3 458 537
2 600 95317258
2 171 251778155
2 172 872094896
3 570 54
2 6 237874877
2 506 216518553
3 179 213
1 294 506362190
3 58 373
1 241 589402266
3 497 217
2 566 40748471
2 152 966851032
2 404 636324418
3 268 235
3 479 265
1 342 386164301
2 265 991859362
2 425 591562906
2 25 797064932
2 351 802786925
1 145 406214936
1 109 638260779
1 241 494140436
1 302 143214534
1 72 836457381
1 475 273274706
2 611 529736876
3 397 243
1 600 74215239
2 262 22752192
3 450 146
3 222 461
1 572 293258288
1 403 376627598
2 156 401423164
2 86 26486936
1 11 421185289
3 455 412
3 137 352
2 479 615951181
1 21 348800731
3 432 299
2 15 186085423
3 351 304
3 408 597
1 162 758227734
1 571 581652550
3 227 566
2 95 12100521
1 212 646946510
3 430 216
2 408 520411763
3 25 500
2 276 592988963
1 85 253361964
2 53 726452182
1 202 471279042
1 121 645219523
2 471 941801520
3 368 343
1 441 669077818
1 202 308806302
2 356 65364305
1 589 35729831
3 554 83
2 602 374898530
1 102 937111127
3 248 267
2 554 795596679
1 486 607116808
3 3 326
1 3 926991254
3 388 76
2 32 481748005
2 212 914701340
3 128 149
3 536 393
2 428 190665815
1 414 627245132
3 279 172
1 26 131118971
2 205 318065241
2 370 374704767
3 56 148
2 14 415421234
2 539 673267202
1 19 251519572
3 361 440
1 246 793815562
1 90 951764822
2 8 770291629
3 332 144
2 565 491724342
1 525 503369441
2 301 406078874
2 465 685734472
2 320 700942180
1 327 629498595
3 104 306
2 128 364230631
1 501 980505243
1 99 905936423
3 25 211
2 181 918431989
2 237 356841215
3 402 33
1 61 911021075
1 342 420620997
2 13 39461179
2 280 973335985
1 557 702150967
3 409 174
3 215 281
1 11 919199286
1 366 772637060
3 607 209
1 204 259151271
1 165 185908941
1 209 319591582
3 437 177
3 282 419
2 178 564496602
1 551 949330619
2 559 684057125
1 347 459370683
2 231 432756222
1 320 926133497
2 437 792228584
2 76 33536385
1 402 515660880
1 78 511618909
3 604 198
2 157 453507968
3 392 190
1 93 151439530
2 381 416592112
2 228 494504933
3 351 286
3 358 107
1 308 550287765
2 611 651925410
1 158 208533152
2 117 225826109
3 525 90
2 131 845424616
1 11 218783724
2 588 127994834
2 79 573227268
2 193 414825910
2 420 931506915
3 316 188
2 386 820188799
2 416 916099670
1 503 225955689
2 554 580780869
1 248 406668014