1680 744
252450033 253570184 690822575 495394108 49689600 321304143 122460281 627247321 32484588 92175946 889012302 604024729 390649655 182628428 399666239 586520451 38768300 645604831 36781948 752313017 645481516 948932474 958947493 925170145 716534737 226868208 279385104 948151526 326557963 11307291 387083490 107661412 79378880 725770154 729315011 170207557 239850384 291254367 684330471 25685353 616040287 686167061 539207655 347630474 497591532 534091315 711957779 525254689 675091169 994793625 354135985 148898507 587338719 667295887 450494728 153178507 638536711 386631671 833469598 889970960 446873181 592515241 842588619 572217092 899896628 473361382 373450327 381537864 319885472 673376675 53518044 63502384 287166136 696048815 648242769 766865546 949748834 582669986 285623478 127688082 948856467 839968307 19807245 867893304 828164783 434846999 40118409 293347862 424529883 266772203 291066185 600123199 443391818 967571816 555530062 468486456 657997583 747819546 909316395 210005108 202435081 510301755 580767647 755343705 502770160 107598566 424545620 417528120 237562522 528236607 900232931 897682976 157668076 619917749 764849758 51802585 455397214 184762636 850078551 72595038 913287631 775956230 242667415 779868631 186763334 690815128 442883931 208607080 93558083 43648493 274711707 647965779 350363233 293466459 673507883 600514152 253132448 59991774 142596167 723858480 878426872 981533871 953522854 690639683 682697015 234475056 468502769 954106011 781187655 831637090 67671914 722504083 187774591 218631602 783061197 272438838 881906759 168299215 366375489 30823111 566578636 575654648 250039335 838327783 830496809 239826643 971272320 74863365 786152340 6226002 936927452 182911984 307979752 19316145 818083194 264280954 179247294 797322284 500105542 552213483 315226915 313116547 653583839 457477340 89509155 530070328 592820731 597910030 142058627 239730669 695497125 476127495 113773115 246935985 702498373 602084349 115388767 71231401 739516738 824602485 91911088 9925656 274234132 848236848 690648436 15983140 510521004 693192446 553561259 657873289 403258102 789604350 216181120 389932577 162561085 504577078 99213814 4685550 679225458 244449390 644559295 50374250 266499235 175877978 682812437 169759949 156534261 635962878 173635387 42484568 473788578 955951876 544037841 380417492 66672041 681175889 489830177 21070623 397900413 557182206 474883100 695008008 411164528 778097068 416633194 258672253 388907327 923614283 208270613 656179219 527043745 986785272 805747918 7256358 247261065 150250971 602142348 325199363 176406577 118895739 121315628 563746309 468939084 82863370 730133211 393331889 424898158 252567514 410033652 973304629 638323890 443636304 564439023 977708657 821950241 997381761 906547822 15986494 119466208 355312433 287935491 877351689 314914694 957159209 534653276 257195840 406261747 67335308 606883290 845848591 706640385 126777956 846765026 47058579 592783188 572642625 633397508 418648481 800010903 201501526 226072819 481761477 676038657 269945780 967536301 427786221 237638516 603562749 410795944 788996426 490215294 927746630 545409422 846138948 468807200 194918490 665027221 539002236 576077640 173137244 611575787 225385885 124902967 425404668 879060808 315968336 444332932 711818350 746911451 758420038 619688978 412158841 640695877 89429218 3288312 152248588 804345968 579594905 932637970 737720797 194169976 689562941 689996921 656990724 170652229 141748839 273225582 858540805 102669961 725317041 64498915 287214300 11375119 188171869 765592991 629989323 87001543 843039598 734195877 563283214 234462390 830502673 506715037 540226406 377912101 310782331 972428233 494762342 583337895 619784466 722631539 762327299 215612998 946868472 671281477 493879268 935459108 549961149 510527322 741305225 178724845 987018410 826519828 200856661 830803991 431218093 118933144 888840443 963400679 239992577 980581923 744180504 94866569 982402198 320278812 935300668 501757167 476089779 166495826 665588932 587566748 963236008 467479820 730998953 457764424 836007573 216015368 39032954 429586087 768594576 148388214 177417886 835973496 315230544 752971225 363205544 962866104 833308903 946940437 124871666 508793809 132634993 769699423 768629220 567547079 473823530 340896841 336976850 863135451 816520420 949780958 673835081 651079058 509225459 724145100 519387275 451706044 732770423 425669043 199348475 313172633 348920901 909187457 6460020 598112660 974151150 60536314 524104239 462910071 21439544 628399297 868246139 64700031 380774551 111582206 750798962 951340838 559952500 662687528 770296277 588290304 944337420 680303860 109836891 457432407 425119260 490110143 637647161 270661272 606900967 132752489 305776175 707244066 609271780 559057990 560071984 29269273 271200884 472307122 973154798 778597698 630831585 109455694 469501946 617512068 929948660 675700802 327940788 758323183 762659639 677549953 891678435 768295365 812618057 6782681 499496818 370503399 395676227 674698523 803722705 320842664 4001535 778239196 201422337 384440697 343084385 497118496 380988781 687733828 172754121 280530016 341239634 104155648 977968535 577353774 565093265 855079311 48534977 527284115 205642356 581582311 891793094 803694787 161537013 178000338 188755101 478191812 578907708 989741447 651238202 838687181 581510048 671902800 503276206 109824056 839915590 932212726 753452646 28471743 253768110 301743201 57955729 887264549 20079507 523376632 245512203 702692710 703875189 905474951 873181844 469061889 773241893 762280777 129759461 727266361 864308575 377473600 690073931 514049443 249842723 329177023 428156296 561910365 539797414 875017919 994348458 800734313 519152865 465386256 873596590 457275994 242946277 735117529 347798373 2387535 862216453 143221656 563012921 442524332 237368932 464549992 614039250 574963169 791831533 304467312 264295313 959077963 997274905 42112630 453178812 520264221 364371027 624619890 525596004 621526105 154855415 866838038 419783286 184914439 226411828 460175216 173570882 215493973 267770875 515392514 749735242 720539132 762328421 874906383 739053349 893726081 191928452 852052736 603806225 191093399 934427362 242657223 882289248 628823430 921498061 364931825 420485301 325780593 536299079 670365803 816832133 152131312 234273465 575240370 767579875 905067695 798418477 563371038 238421320 248225818 796923852 556247102 390591770 357777537 207464423 689855717 762423472 78968511 930848092 607799579 615503578 798752760 343151451 318699432 794571617 154902900 871150203 271021656 132445353 794466226 246801051 633386247 201989377 483507499 979869698 693341098 926117715 625904839 949312648 480239466 190583390 875683282 156129676 637770534 927410480 416239534 725527742 249212965 894567169 766132534 881788201 991506988 877411438 198172593 667797818 777131498 798891296 105912896 42078352 669687288 897205436 288246096 577556195 681033909 852429613 593153040 124230285 201787278 26068626 209341048 166368118 982654109 27836730 396438733 216493080 479976835 621921112 772073360 366319951 421411716 196856618 412261978 308142016 824006450 529523547 817254487 239276630 260419048 446386646 184887361 210224574 253807255 11555880 824564183 67793412 563343786 641020576 280235969 992811238 823115049 349565906 420227565 619985942 19284600 652333221 739609508 101585579 595749947 493906998 664406138 630391023 583783682 767032726 951772788 622164796 156926487 958670133 303628714 877509021 584354995 717470962 522601992 546439241 814757728 86559943 444366445 918360793 831884580 38494218 764075301 798473634 517841882 640927186 551317687 34389610 259950516 25205683 507323346 931897572 304451978 510204507 936316312 752209464 725639874 957744397 689557533 361245098 659303120 527046345 363653592 49122268 353930560 219387858 501253788 835109136 645680115 313699513 814825023 985929439 132591501 247482450 902296398 322699198 709218596 173741008 422546313 575201851 305372223 961835329 640408329 686576203 591862858 98039075 521277073 641412628 960149877 388467037 273966024 192898076 551200315 912160315 381162010 155524982 693059293 689953271 186262296 773553319 651506458 308342796 193727310 461103234 603852306 808072518 529819873 616451673 656170666 810845478 152099981 843853978 578612191 939405268 758243673 377045476 60326758 567887211 165568393 152234578 996096638 589420784 44708790 773921631 596040506 294714164 26413273 429200688 592584342 465299743 434091492 59212024 248851247 690000265 194931884 380240279 355311502 710859206 714499932 496736601 827766490 440983628 659349410 619268820 70820299 231700210 825415452 29168522 272181612 685494795 913950249 772143652 114224127 104461202 522680239 376902255 900830911 855625814 13642504 938880676 364780723 450155932 172725063 108964228 650413779 522572595 282988034 776289396 187184128 93846496 402059226 842848326 34774304 11763481 335677989 936646579 931132802 247705821 375339755 466708570 508711025 585174694 750874954 102832679 251891399 242403316 535876712 955624407 418472615 556512588 288251459 104250663 620137394 600114806 62390004 16056039 467004767 603480796 562902564 585570041 783527055 585236212 272787660 509049580 555660403 487508522 826856545 321043791 740063202 778639898 559190659 278038734 277388417 105791872 283847782 766276488 159089667 308912430 812761098 867392754 168873543 895303163 946926069 683468868 212759009 434235150 543261974 753520025 574581856 184595758 605552736 985387204 360515783 467105176 919407217 719210653 394388691 560112428 251847910 27988698 19200679 447618254 993857807 597529930 484691851 742099962 513907726 753789232 985029877 224033812 552327220 993193378 219643 169847160 901322140 323257912 106378529 215362633 59420851 966147872 459506208 682325986 149370368 794002602 867710149 636146125 841161630 223849047 503682470 478517565 588269879 864112417 637491533 28917003 739257399 377595201 136305599 511936924 801573847 249694938 742593545 82632541 699327481 677616960 535107913 410976176 279088984 843654060 50974744 549809699 733047019 956906845 4373741 248872570 318355555 889083288 924022873 634393426 939351005 170747352 345416217 97614533 662113303 696196538 416224204 970964988 923846899 711016877 252570458 690262291 706394286 596351770 673541797 221230047 322910513 243302992 158131531 572717690 41979571 790772586 616608211 466767912 254577631 286911780 515426188 507646520 170080295 621620999 739805190 981918905 960227168 968885389 288128442 285958637 988482487 650306221 132259408 895078763 76372312 438501535 190324636 293666918 334400380 927359973 14864143 191785655 431872941 613934613 298493466 485053676 818378134 114102771 748594733 403577075 66683057 16211418 302350175 998835307 423822431 856072789 256759767 474350276 634249571 188411033 960678283 996786523 169528104 446374525 294601630 724649569 509965574 262359705 777860658 64452833 954604646 935295840 400469921 719924046 804770023 499993641 435674320 990195483 49717135 962514815 585743787 914227834 892314537 469886410 310182705 832006596 57613871 616344567 859527168 301293229 558728492 156614435 211521972 524931489 31506454 847393585 674217392 444607056 518834995 362595988 664061982 206672548 894291712 332401857 518397900 965364883 499405003 316652019 688473165 62806298 763668017 221816311 557123664 576228968 897606710 213622086 173035262 479396725 817905905 385228970 209754477 654836325 762532675 904664172 35247648 560280080 371397405 474197154 996082571 602882800 478001649 242107231 189740639 939672115 836365481 696268987 483451001 239742162 859823020 775632322 73168635 357256138 550230680 117604341 204048992 637636443 849252804 436848816 554657301 162558024 674212219 247738148 862915906 222379513 288063593 240015882 39412701 680387259 995323125 557595544 349223816 885602146 28382281 377845883 715779442 430670877 804366543 465302843 412994664 859628314 694441085 578445254 457548405 801262776 50196864 484656665 413533586 765145993 837066524 171542062 348585881 449121151 11634011 311331427 686741926 407748680 103169566 553742059 28304733 442894469 661351307 472099120 977114507 875131731 652289851 404850958 116296777 712659916 782991874 100071930 976853240 178395270 2581617 87835176 482101722 308941606 489987678 85632520 219985579 282751850 35756112 248091134 957926971 807417392 621288947 963654065 256169762 887970790 752282192 339864944 186611646 591232026 190415397 748198191 283030180 244762047 579734998 699221967 582709698 161955126 957025200 310537534 847800120 535063027 174808849 959105416 462584631 855331229 2488862 84302325 318378801 761614018 454747960 866616984 736556988 647495106 955043969 129226240 555125346 883085675 735432356 783481862 637562777 252925816 190689589 154948451 707668289 738845934 118296255 566390442 134354488 28313115 269272323 629553927 555080095 205079388 103946970 683510787 708530968 966276258 431238513 952881976 451844649 929206766 427415457 293544886 525198413 270925586 198830240 836135066 621062179 383400664 443700600 368155517 30731943 979018205 163398407 550733889 777604055 416124412 982558886 826507377 332419164 520676870 191331145 121712046 54831249 248930283 953950792 862380447 297715380 83087271 631226786 293205541 344175868 529607400 413008622 651062690 144104356 972121692 115585366 401053788 336315225 983894015 824384987 858412513 760458293 639794583 951497835 259255464 498229449 136646224 352200337 55622093 902728302 147381971 868727284 299512694 777468820 438589396 406250906 206259162 482318624 521972288 891974018 446581078 16294206 130289202 764370589 60561706 273670091 367633342 383292477 93333498 10755040 621116461 68809700 926621720 865476539 675612811 945277878 364797907 635049545 923185930 464656442 677571687 162042518 196345024 551304183 569683895 518431474 757860724 133068244 638931166 716435462 77776146 424974849 925102091 964268977 992689042 716966629 561131161 853936060 578123982 415446598 593952074 17403136 364123487 33286265 620957109 987689859 615941522 99709431 505230544 626249244 669629558 191644998 354939619 944113678 490644132 431005168 610034737 622055840 656666530 288938693 854844291 316134994 555875170 760077118 826904703 840553134 206040441 397383120 267173025 761393055 520375264 20132150 463228610 29127206 10359840 319924894 467189615 866778700 413374864 796587386 794167804 226042472 783851929 863502272 153579127 816695296 714560310 926363819 202023181 23763716 620809951 558746595 670611631 470338043 911567972 439357366 610141764 896703282 714526453 506632082 319879425 466389710 578494488 347821821 105652231 953885168 167503544 249833115 80206706 909940860 733913375 184800083 340400683 253081648 980701004 881989926 286903909 739764481 429233730 520647113 728069924 525390745 188629362 945289348 828712719 696838633 601911389 235797611 918632636 268619959 928591192 707910131 885704420 445793824 812313009 258009287 148696196 931255133 786079113 749125167 516555420 309404373 549213042 23332936 639412704 946692677 329364477 876828642 160172081 976368474 801162360 123578661 167501651 421934967 131185773 42899103 379313076 141472792 627023099 83084343 660911513 400570941 528453008 512835228 391594405 870705806 993898635 521480592 86039105 125699224 168570359 546552071 59942948 167165546 617287293 996036512 783075077 835034162 794051058 362524109 977293777 257289326 768634867 147538678 346772707 179315134 447638483 317960039 571593023 183153408 261299740 467376866 20958076 621998165 144213764 19592894 397662639 882123877 237101795 847493721 39635038 269533742 177566550 964660078 331172796 625961141 326093403 939632289 201176823 300906954 933166869 862476676 914233439 921408940 797256207 519879849 906945944 820350654 585502165 775082981 286894512 222433200 841696782 179258923 488065400 913920893 19698454 490752497 863415222 489499700 561491128 66676686 741177687 579917622 280144155 703850531 461684359 818171486 79062207 817587295 553470982 725474534 269201532 449763640 93915325 140466134 100094734 660691253 141787323 688704959 185439118 320059070 763778147 630760169 905079255 612400942 171333817 506244975 529786528 978199287 41879725 759436629 519406656 222847605 61826113 268870465 757187600 587278478 739455293 338803716 654257192 845102621 264492483 30580364 487980561 577008443 936913396 41438819 787796990 127125976 62753611 889470450 535418061 172289243 40246746 624338017 174748479 743630717 246266487 356208862 687665485 432429751 350952887 215879583 497328227 515574332 134588263 999619489 645441588 246364040 329357158 324568347 898816896 233778553 510328453 952605813 510737178 380226704 659472648 941958026 995189124 935243917 347296020 206520468 144060785 966197019 333156975 869627969 405112417 59413037 877399225 830768337 505219400 519874326 825738115 118309785 852185032 944322334 446553858
600770303 540195793 698153793 740118143 781751696 563541226 967360651 225523023 103023209 398267510 868238601 272796949 285481219 20688875 332755432 957267829 354253380 625070052 989072135 894065660 441524404 641130375 922109287 24991207 421332625 309953857 608241908 779524805 145064869 58804388 343518508 885712074 209453253 16386470 22830920 123898548 974057135 564753958 734333083 942715266 895932353 228868713 636198452 138950199 608518753 645605302 450952229 643345951 680933792 637972169 598526019 563072388 466000104 725040241 402696987 174538166 371455790 736589999 529715547 859998816 17768611 725159773 615480114 112299267 556730090 662318986 589000449 882646993 652403916 899676061 606812609 768544312 850048920 107241344 702266345 371994800 873989350 448946561 264372284 904227321 208459002 740806358 712939150 349904902 337804407 68872022 335833760 127573736 795863407 263975805 635483981 578589115 438941037 665302547 101904966 679709467 670423933 600756313 632711661 859890407 489018323 135522375 916602765 820119618 142675299 845013093 206711780 209450684 759357727 755164891 238798839 894829660 465001241 525059592 506217757 168863665 714482466 209458890 946536221 636424817 852365572 223975857 945231324 421370706 465528806 338672037 753645784 988957537 928078734 802242095 291812936 831812246 722526419 747428467 627916470 258475955 707890272 174376698 276316314 216364927 164510771 24513265 455430572 913304644 14643834 235090473 118701422 547410873 143311204 404093366 207486030 386510591 414653396 465432528 915771864 466431890 759822352 437734167 91033967 811097092 506994250 735684548 195614225 455826976 792367492 623729147 83325338 987893387 135421587 960261602 647492985 187723927 684231129 834408406 12837089 884187556 373741113 418765641 75414931 436792922 819254328 623869638 344931400 81493586 688547397 252143209 940224461 354236488 330237901 996136443 582250337 819474434 839285712 614498513 505261445 393016154 987538110 191206840 778347954 827857059 213950010 283718754 4100079 467083070 253754678 814819581 925349605 829548831 160734128 630532100 93224304 563832022 308798647 287206520 131089936 507135793 594283901 718163552 695650722 767921697 842886341 611223550 17912131 647692756 298419205 184885096 888718410 532246001 736867274 46246510 642718939 358296332 148818959 787405597 785189056 567427161 805383964 882868460 728915243 291667982 780070061 111126415 389885604 228750066 604750531 29472746 884736191 398438581 470763386 288705210 211249363 514603331 142844454 306562106 445008708 850854927 783931925 653916443 241629427 211606584 133192511 356159892 685741457 461345391 894378284 357747541 745437576 279634312 552794059 243701518 36855593 229497895 765029682 355708820 462519094 911155205 215229075 538897382 55426355 185743622 965633008 72722007 548993408 997649644 482770283 971399287 588448863 824452130 268112558 743323789 852684898 37852497 511414331 191595538 66771473 629102925 711614662 268996515 983740028 677163551 228113101 763524394 45188949 953381633 660091819 34447911 486453937 204672696 179921620 939071705 378162370 262821775 551188403 398485473 352255947 231631088 121128963 806810870 876056773 331164039 29542153 61196932 935925429 742966957 725866761 682887477 247394358 433978981 553532515 678860891 291607114 686408623 49918390 878839621 523298207 903271454 878869963 704363597 446631513 174877133 12947020 454012994 547943953 600820829 951693082 524284173 204617103 669740450 178846191 986308379 332154548 94871164 191770170 323274350 440411783 586733178 978125732 757874539 597602254 221396857 760360164 298743370 299488122 574350370 964424621 96341315 566325891 252266458 109229109 425735880 156858294 803717709 81016826 466341365 527306925 400185477 953499759 659133573 232338540 901484151 78270615 196849054 677677032 697181115 901657708 502973937 162003774 248536687 32200931 334198365 101632557 276328417 683552666 7018075 988923431 515356793 369858847 731736620 338232531 205234840 841205326 685793910 683562547 522571992 372186372 894909108 388594929 511591038 670964446 297191834 262998865 403282029 69393920 312858067 172678387 78588766 579244531 643262595 737561351 641306522 885366390 470534997 485996481 479194594 32681042 162426290 360896269 811372902 913116080 651713119 230974003 379507669 466935144 214821224 796857830 487429502 677240526 16861271 673458040 788231449 719992007 399569037 706602897 181474010 552347430 721929116 784169798 349060855 822506492 252633432 102912311 615638040 358207250 91271211 389340412 555912123 282883842 946758602 969113862 118602306 120769095 761780597 788619472 760216897 306011946 387374167 180121972 426350225 982944494 885562659 671598140 318079541 448915892 365423974 412138673 218908272 295812113 906244991 783147767 966360144 942700518 699737840 73128546 638260597 61961122 387138400 187913850 735844140 101811639 569887843 545503794 372720390 750936295 286761764 74641678 741642136 992558013 127153432 653562785 723212984 453897683 532528789 486109634 23467293 31822490 517478442 321443033 455536138 380357099 907553879 254794226 292897900 890557485 819279642 3415976 628269442 166766460 832727608 63118836 236484718 607953017 630813453 817828932 713062289 859786966 62864264 417454103 224491692 425660763 236673921 514203297 813822046 989397545 997745259 260174126 550438829 921768291 475465817 541205020 43414094 126158116 809852372 620499762 471379201 287567765 227683898 580102144 787362820 501706890 870406296 826752864 187447727 591785117 440446974 980271757 333769652 253651419 120360123 460899994 232296576 604418317 794345189 872473597 653420913 265247665 580245489 806953277 855094758 725962238 845486079 617437026 541369907 756929392 848806838 538348334 860882702 288518202 593479300 407485982 681174751 31047210 579266020 999305794 488374635 561728795 679772274 946965683 851324080 628646202 625870203 765342779 595961355 212289196 834809697 833201912 178430680 189307265 369073333 973819566 526976084 543990077 653534767 179624483 851938891 807464578 916438842 390835536 700197412 106033545 137873688 532232371 909777210 153817269 911268866 997549513 18456905 125467709 904040402 421551901 945959553 494480266 429695899 833596118 513657188 774018760 88059861 412507280 707673573 732719535 63666917 474497441 378553428 375851455 154864981 973590706 168060313 430933473 635071668 421804964 926270263 671353344 644065561 628474351 596061268 538415431 940814033 295275710 195854489 494799754 5587683 279673722 685902574 371108505 495507555 380089114 669900950 425792179 798745706 367497153 628582722 729451889 59753893 942534446 845904012 978827554 428295208 22123668 244464182 171672124 916891842 88422043 234758002 22598999 864517702 211231055 326040553 275210508 198941793 445736301 587896660 742081478 546593820 750809710 127111688 862806026 987567273 947644826 992864075 654296322 129922998 205653813 733575908 681167818 57465113 327361522 645497811 20316992 564602516 188486641 595289483 268973784 699716176 666821753 90913129 340890647 126256773 720878462 526057181 73724929 980877021 379451265 300171852 171858420 652069989 964543863 342605144 742836660 699521779 236189893 268090716 45463230 610971277 621108456 570159040 307579609 404953793 87919295 519173016 456369725 921677088 57854294 549153048 974948911 586681092 212277118 102664338 18208543 277578491 425942190 119117095 640264141 119365130 751831530 995200074 247323592 638208953 373478946 715180629 149488071 331575767 65774894 949838448 748671917 654796598 103815014 573815145 328693791 656303212 67875765 797181865 701122850 535677918 261340901 709404301 543495211 443051810 974350639 137633243 615026980 743428587 608182975 319962432 751756226 787574203 28781445 852040039 159252376 816548671 287788679 893549159 15098704 906253804 955033478 482507873 701117293 582508894 731690682 79734969 722086607 461986204 168563649 508523427 236602507 887036346 22938058 193298084 792922543 798625620 673028346 162006289 789641581 581517823 841279918 461496797 231798509 875105677 124272568 904039098 696012352 471070439 768968701 826941319 597571017 88745817 756704501 221649203 166993080 213626365 273794517 278296983 999582956 573103393 188915992 740090168 979979118 485416038 949498934 290841247 945074265 205765642 286913964 403295521 106999658 775297255 882239571 786860354 732761913 911716411 784996805 304994337 91622334 874665487 98761847 513537697 676745555 656827515 550611316 296401869 936344549 351117206 960088271 999326054 336523851 466588721 986709280 383584136 120361742 72784342 661867510 531686517 80423731 553785849 180557718 101261238 201044846 676624960 998363991 324704342 596299174 102080738 79383450 785687884 508147829 322249367 742102320 263213586 248402322 967806005 822878135 299350368 270332459 788734247 823946414 962648470 929945698 306017839 98285101 801584391 466538849 910352999 624941311 777414776 409885753 878297282 486497146 703886869 292542018 550597258 239037755 198605580 823465608 440624096 6632674 923145608 731188586 754864004 340151149 172650656 905252956 106697355 285975804 592985399 592512642 611508125 640729265 472460614 737980731 815590505 188743827 638468476 253559695 196896640 815061979 870407496 386536934 601484198 922308325 70821468 897944448 798840886 241832883 759437087 670658473 462061979 567539204 657017072 672332311 357888447 615244669 832783359 939344051 17751873 322934047 830444797 690616801 35010550 929353325 165809128 650480909 308782490 762778140 531558375 96563718 59607271 495796767 587627818 553056744 456410536 144061854 175133075 714163288 147529199 730901648 206249314 237924672 495071320 90320551 513236023 540969234 626974739 171370393 376972801 272842002 345127500 975694061 265276882 172433507 806334191 445424973 394263216 656032427 36560571 896787449 23393690 449688947 332332722 389435921 764845021 444814782 873597979 289273314 690406368 827184716 220810104 674887170 284259460 678751878 271947168 970628208 723839639 60301615 273060684 192083123 193127219 397245775 269228964 833541257 15223511 466333435 14701247 947708467 672772217 438287804 178793957 942266123 741350240 882168044 201961971 36517967 826534150 273636132 447950198 608927260 384727397 908262795 738204552 625329969 507746084 537285421 402511207 392279029 582226954 238318397 901345162 536419083 500335204 408336507 954310983 171238319 999756029 354402000 475162004 775317502 665861669 126908007 164563832 799571677 624705730 426294585 460485687 685038393 632519650 55496374 359962043 362759733 117509573 809673019 621679425 936960948 883613763 61790724 46787133 705694594 666810464 957415865 723590670 258297938 135780195 946415737 916396714 274174458 364037303 400263340 839889093 191338918 299366238 854791543 395121843 709804765 586389468 306820591 389589907 579855172 491156120 663905731 238164328 751736944 791115174 93952154 926282314 527184416 594471722 376952752 545745348 465426428 8128975 496713351 387776979 89593227 120655098 882414027 370585826 396524384 399709401 235342597 881487963 971873860 115498603 179865790 578941794 553173761 342358673 627004633 830851860 408458882 610916530 997253244 882344613 687816537 617946315 704919008 825342068 235230484 22214837 207933156 219211598 233361823 27445912 427911823 931976090 998429103 352745989 840377541 283117688 563784849 200057515 371527213 651378043 766484543 290866900 871142629 537481180 277160220 242030557 425156626 593847654 699112736 135082224 291615629 259488732 271192754 824106399 18978368 368842848 375550607 761192804 339706679 521916588 441896189 971625776 612185175 970232201 143483035 800160319 956124106 441537812 680568398 179367533 411311089 592834158 621946782 317675454 683449190 403575201 577340254 91627207 430446254 744756877 73060245 532055924 984921977 727793511 37834261 663660905 209602234 654505041 590368887 3939372 253205737 631005280 445882909 267332496 747565101 256442089 946475001 894302224 201563638 862152326 652938086 559590307 455601045 360419146 932851872 942083022 507010112 820887709 660102373 226752118 602851958 545223529 495580394 962115432 579911168 329754218 773258727 672234550 934077168 998003780 917019908 487256543 945311796 597322949 788237298 616745051 593942418 871260030 454779677 21599180 765076489 540542186 782475711 460840059 57686486 402574221 459660786 933123911 421874268 460878208 583886491 15416278 647462325 414577829 578577562 827746995 767320794 430792850 479445566 484428071 739509700 471698859 467887261 283011505 575437324 138258974 805080965 948623432 170346497 188023535 295207271 594357950 735110812 376965376 596564787 316482489 865064459 254080004 718344156 182707925 757896384 853663733 259570957 229773924 85390216 223723165 867083887 233133638 678846200 205899689 982519791 999591915 226746033 645386233 179921966 847097598 844688886 244657842 97739588 168769272 501039781 808173732 89941149 389479454 968849658 127827704 120709349 799513361 556863911 554851769 628842187 372664875 249154951 129764515 763529390 92713899 44098012 789923531 789038737 647020926 841264405 288528081 23804165 804119390 270433247 474985004 431633251 347664286 562394555 53706308 115243706 486780681 464715978 185823068 60141178 965522864 555814547 537092773 940921049 528025123 61708240 740684803 998916153 229764433 782831171 248619445 902512880 838176923 263172806 115914927 497133848 13950718 671163925 547523697 28052488 151764535 299461213 851160775 692335869 333458664 653472519 661500682 103516427 663374998 858274167 442377294 918305452 240864545 61302900 82077471 707758935 397522203 931484888 769430158 3443226 936005216 696849955 957059731 921913739 418002067 120944045 732246373 284296480 327479267 623810522 293806026 2989200 850416605 233782836 556357077 859057823 19897839 870031713 500048973 659406454 473997243 366883584 548308354 156406052 562805197 754920247 264989024 526106882 626016826 739667131 321814288 973803912 351985632 679956959 270989701 809712874 157764909 186102988 426294405 515046704 610398869 704991675 193178851 896814173 251412048 711744393 421458008 347567218 462306250 790877591 548814657 331835182 865499244 797973810 173512070 436854089 184263217 639402692 845210250 3820239 812758405 195568961 514537184 606556926 451152720 517441525 417375738 397908311 460745637 375001638 73984402 359592114 657683201 397994574 454648647 550721920 329063710 245060227 293420879 837359312 192233966 479915190 866184570 267436329 567670488 277564000 335220977 186630906 536120226 74860280 88909803 408583394 71158759 482200905 279965960 226546372 873172737 868062552 868191190 227160297 230971319 709850593 923641737 86598345 816680376 569465710 350087091 836836561 672854036 825818109 54061598 314900317 142013945 475531108 112255275 413713293 305685338 399327994 256850672 661974015 90053794 319465519 882570642 464184373 549952510 666644166 845356911 136166590 165571600 545227660 737221156 263351162 494692860 432566599 842266858 991895512 276906121 438096908 511170266 131871126 557923344 589235540 107680391 910260119 171489816 267125888 309193163 119034441 398897225 954089449 336590713 303473052 201414019 79842277 844946952 948619021 386081365 975994445 513201580 828078386 890046377 821177168 585131768 915359030 488765227 838662291 519002157 523528870 448574759 38143372 645300186 327070380 49208301 892112137 729258285 332098559 343425017 222283533 184984160 404747885 218852981 6646439 83204116 670075210 599276315 880713671 482330812 737715411 213022406 148504915 727024597 447593980 947550396 446740774 341748954 910929220 878440006 606004351 216791819 24256477 156552056 993468354 314284583 273122097 402680333 67571846 412517775 726456969 400180597 726506473 54127273 786448137 295359274 532041353 640856532 266533517 882802801 895663858 403606613 999906892 715134693 7712073 468576150 603222211 33237601 352110630 118665441 673022091 933726587 28564036 558360053 259044514 70271177 928954783 993830611 207085935 300960982 180788133 495438334 269394951 260393281 755091268 955569111 777212044 990326380 322325326 897289088 661386010 735553699 602204953 253361992 672886824 418362427 880636528 916390468 284510124 630775677 879294801 914971251 273205674 540280505 547661812 867592099 949174747 845710400 115152552 574085502 49903428 827679793 679394140 856689521 983317557 874861457 508495100 617057900 388915243 724111024 233017519 592447194 813823675 152308872 250144665 439048209 294077452 823250301 850031261 246700209 110659759 194259325 477149604 575796483 741554769 251124774 502228654 575949797 33599705 152142309 900091191 484130698 153266929 266924246 489741547 512307435 629676001 981997460 468389725 477136450 588302613 933794569 317768880 243637344 763755610 1039327 603316944 725341789 528452616 686191899
2 321 879256198
1 128 317210238
2 818 384124913
3 1137 37
3 112 603
2 593 6824300
3 1101 703
1 712 210069169
3 198 1237
1 1213 749665128
3 11 1297
2 1509 342503653
1 166 619371146
1 1405 416229772
2 872 976735410
1 214 56284599
1 455 605513369
3 1531 1377
3 70 1571
3 1022 720
2 936 46597132
3 1564 328
3 107 312
3 375 978
3 428 1330
1 664 637169954
3 986 71
2 94 582043017
2 1617 151218269
1 716 865528613
3 1148 548
3 954 29
2 561 724099874
3 778 1104
1 1538 27361056
2 1472 182854279
1 105 730975443
1 389 4881290
1 294 752881142
3 1521 1382
1 472 430869733
3 339 338
1 985 852825500
2 628 139482114
2 404 740950249
3 376 623
3 388 473
2 1025 191843188
2 821 162282497
1 1484 677223302
1 889 956703023
3 1395 279
3 1301 202
1 625 471277687
2 261 301329063
2 150 285449248
3 835 1455
3 1226 165
3 892 1007
3 884 183
1 1511 118430432
1 334 585294908
2 467 214397511
3 87 152
3 1574 223
3 1580 1392
2 199 247524426
3 909 1509
3 1184 124
2 1588 4438868
1 145 782956467
1 434 460368412
1 21 462216306
1 281 808153779
1 1392 731846787
3 128 1046
3 1457 372
3 503 739
1 782 990501075
3 1066 1459
3 1672 105
1 1343 620781984
1 421 787968639
1 269 735596749
1 1056 585137420
2 697 112857728
1 1295 593572012
1 700 152511230
2 585 355748119
3 1440 744
1 1452 128114235
2 1635 85049230
3 1452 707
1 142 959497889
2 591 830483438
2 1078 601483274
1 661 603569044
3 831 1341
3 76 890
2 1499 985457275
3 765 1165
1 1173 658008663
2 773 798990115
3 1673 1479
2 1373 503852723
3 181 1367
1 1483 582971990
3 1437 655
1 1206 379575976
1 828 457189084
1 1642 280932741
2 37 490220131
2 1609 187567445
3 1378 685
3 767 1400
2 526 63832276
2 821 361086155
1 1146 126264671
3 63 941
2 453 187786049
2 418 540420396
2 1410 787857226
1 51 659060288
2 875 614401811
2 1521 941031186
3 1111 809
3 1406 667
3 847 781
1 63 408578605
3 1372 69
2 460 338822935
3 1497 1201
2 1068 503658753
1 1029 781016835
1 225 686987143
3 1353 1247
3 1519 328
3 1261 419
2 890 668746084
1 667 877017606
3 1409 160
3 1107 603
3 1234 227
2 205 225506902
3 1592 174
3 1169 171
2 1519 199382424
2 767 397530745
2 806 95003883
1 759 495178544
2 1639 961307396
3 993 746
1 1403 918297580
2 718 955715085
2 431 585661479
1 681 803802501
2 1559 949147979
1 362 177284514
3 151 303
3 1414 229
3 338 113
3 1106 1064
1 846 286468381
2 885 711059893
1 129 188430690
3 1220 153
3 1195 328
3 196 299
2 1355 44325219
2 721 274101219
3 986 424
1 142 343396255
3 1117 1590
3 1526 360
1 372 112383337
3 1048 40
1 189 920650293
3 1037 851
1 1090 731868282
3 782 173
3 627 172
2 1198 341522084
1 504 917735766
1 1406 948223475
1 1024 546717838
3 791 1078
3 282 1609
1 344 949665633
1 694 662774999
1 369 538568482
1 1333 143835260
3 789 603
2 449 426541426
1 1296 597985287
1 171 826908613
1 1178 675814746
3 1027 1599
2 614 402691712
2 211 25033973
2 85 666731327
3 872 748
2 1615 494885308
2 1364 489048209
3 431 1395
2 284 836549653
2 393 661396421
2 217 611879708
2 458 95545178
3 1634 319
1 1299 112055592
3 1225 1016
1 748 494274647
3 1596 149
2 582 816437001
2 788 369184601
1 1032 92061144
1 1439 869063161
1 388 664559370
1 478 481379196
3 1616 994
2 68 176133935
1 868 164284196
2 996 103743191
3 657 1459
2 164 674232041
1 389 861941285
2 267 766124320
2 1407 960251054
3 1663 356
1 1173 345398546
1 358 964900037
3 318 1291
1 364 325629967
1 1658 257961162
1 1273 425225997
2 684 22738481
2 684 650859791
2 646 802002977
2 911 328423470
1 1147 933603300
3 575 1466
1 592 487996882
3 1235 656
1 1658 772209958
1 511 23645474
2 401 369805351
3 1156 1139
1 473 205767072
3 646 195
3 688 1432
3 384 929
3 101 80
3 1353 496
3 1058 773
3 1606 252
1 1505 98626354
3 1221 704
3 382 799
1 356 256267888
1 1026 717745826
3 690 912
2 1180 854041922
1 1583 281574740
1 554 940701099
1 1639 356338557
2 1128 860846791
1 1270 530705485
2 963 221104039
2 357 270437226
1 1076 976612457
1 249 704249474
3 406 1538
3 1308 12
3 608 429
1 1341 804547074
2 1000 885656356
2 420 662463377
2 3 319918808
3 1082 518
3 888 475
2 1166 573273901
2 719 58218556
1 513 393289332
2 872 231548591
1 1272 240885563
3 661 843
1 474 566950825
2 1656 407595665
3 1278 1142
3 1261 1427
3 974 788
3 375 973
1 180 794558322
2 1112 551362002
3 61 1532
1 833 853261998
1 371 739757349
2 208 691290830
1 1382 78849596
1 712 822256368
3 1074 563
1 637 311113713
3 62 1086
1 889 404640685
3 962 561
3 871 611
1 375 172119973
1 1515 603065392
3 1549 1270
2 488 608133378
1 861 272394204
2 67 53702289
1 1426 67564488
2 265 487441552
3 1339 1605
3 1134 85
1 1274 822390399
1 211 684096084
2 830 75894847
1 745 528766462
1 278 81341679
1 1380 281914452
3 510 199
1 492 452757611
2 1365 989573443
2 190 951103181
2 4 943283168
2 627 94940577
3 582 418
1 164 709012128
3 484 867
3 928 738
2 201 785298652
1 374 957279427
1 1178 231777541
3 786 221
2 639 206548016
1 14 16818284
1 426 364924405
1 1217 675540679
1 809 248517430
2 580 869648112
2 239 737354256
1 1524 559495229
1 251 719992995
3 1208 1208
2 1540 389903325
1 260 937795704
3 349 1657
3 1086 1375
2 102 20783622
2 1642 401842401
2 795 39942227
2 1477 770691673
3 984 569
3 130 1664
1 213 175151536
1 1441 574966121
2 688 830592563
1 1012 764694803
1 1151 954349536
2 307 108332853
2 953 529799311
1 939 274451105
1 1419 223568166
2 93 816487624
2 1495 539918662
3 1640 187
1 1555 313855746
1 653 929443316
2 960 139533249
3 1435 763
2 123 111999419
2 1053 482113248
1 769 795923288
2 644 744791050
2 211 523182331
3 1289 1331
2 219 738873887
2 456 748238390
1 1168 360562906
3 39 1178
2 520 419368340
1 938 786867937
2 878 884170860
3 1139 22
1 674 348454391
3 322 1574
1 986 362895105
3 1414 526
2 1160 376597553
3 850 469
2 1380 699476418
1 572 18088369
1 1591 712515803
1 1188 180915424
3 206 402
1 81 785098558
3 532 811
3 293 373
1 1462 578117617
3 668 1334
1 149 962841296
3 223 912
1 637 912310664
1 575 579263110
2 857 973511772
3 927 226
3 1259 690
3 1111 615
1 928 679422117
3 650 982
2 1525 109261786
1 1041 583921405
1 1014 872182846
1 1149 32926092
3 1123 1644
2 1428 291239223
1 553 6004928
3 1261 1300
3 1109 1009
3 176 1671
3 1410 885
1 1352 566583554
3 1229 1468
1 806 989644140
3 1435 775
3 962 609
3 30 227
2 334 706116065
3 1409 1231
3 276 1244
3 861 377
2 73 705325683
1 1562 696053840
1 1002 662409896
2 509 369835534
3 693 1356
2 778 122925635
3 804 926
3 1025 1653
2 719 860265999
3 301 77
1 696 417439573
1 134 126556740
3 806 530
1 197 996903743
1 151 100940793
2 37 136964252
3 1381 806
1 1154 301667603
1 62 20635474
1 949 775449075
2 645 172361919
2 260 858524018
1 151 234900026
2 682 362745042
1 1232 718604990
2 1402 38937787
2 120 42131783
3 1174 246
2 633 955553962
3 256 992
1 392 691023897
2 1488 814150754
2 1595 617730405
1 1183 171555139
2 1437 39415799
1 1292 639266951
1 642 506675966
1 894 677049
2 720 540244272
2 1137 917115743
1 946 979959121
3 480 807
3 502 863
2 748 97432027
3 799 214
3 1454 173
3 1214 524
2 1314 113890474
1 691 29343233
1 1263 193033431
1 1572 216983248
3 662 927
2 1176 319920597
1 695 374505890
2 1178 668931664
2 644 610897262
2 1078 663164081
1 1284 19189870
3 1438 690
1 51 449742116
3 1528 1428
3 812 1646
3 1005 828
3 1108 303
3 1313 68
2 1515 974618325
3 705 888
1 1008 22169976
1 1239 730645017
1 727 187165044
1 813 522001494
1 437 213499848
3 426 279
1 1 377368738
3 972 574
3 50 520
3 80 311
3 874 134
2 239 826162851
2 315 554195558
3 633 1313
1 191 482703201
1 610 70482855
1 634 455605696
1 1350 63773327
2 1487 795754420
2 1146 738739080
3 297 639
1 1627 501864343
2 447 447315350
2 1126 358320020
1 189 491877203
3 984 1284
2 587 723659106
2 315 463510817
1 779 710966284
1 1481 825176086
3 930 699
2 1082 358931806
3 868 498
2 1371 800760188
2 225 141413392
2 881 932138840
2 522 250696526
3 365 243
2 117 693559628
3 162 1549
3 307 1489
3 673 358
2 349 562352307
3 1199 785
3 1462 1655
3 970 282
1 812 469455652
1 1474 772186298
3 1139 323
1 1412 355350787
3 1426 281
2 1091 571973033
1 1257 432887138
3 1260 814
1 933 38887476
2 1582 484364302
1 903 845375324
1 1454 177569566
1 853 893337013
2 853 404753966
1 802 57297074
2 1172 98888831
2 306 108325502
1 1351 46963689
3 416 1460
3 982 600
3 428 1251
1 1326 393035950
1 726 693732134
3 49 988
3 462 597
1 342 284560449
1 1665 642330035
2 909 675425889
2 636 304517479
2 1020 131152221
2 989 957798860
2 848 746963911
2 1216 252520462
3 1546 1496
1 1361 933452486
3 122 475
3 1172 289
2 876 232517843
2 819 128993096
3 1556 181
1 1082 812951883
2 392 443957354
2 611 713098573
1 835 370146134
1 314 692439860
1 1525 66235530
3 286 568
2 1456 908713151
3 1358 112
3 1370 1535
1 343 94480844
3 840 625
3 1125 248
3 1156 411
1 512 654345271
1 1529 966415523
1 962 54745265
3 1077 322
3 503 1015
2 1321 554375642
1 1338 375720690
1 320 104127436
1 476 501758869
3 2 1673
3 1129 601
2 824 512771567
1 1674 925561925
2 1413 345327213
2 232 89934154
3 1143 822
2 824 672415811
2 360 48998581
3 1500 61
1 1401 848665656
2 850 674760576
1 1524 420729774
3 894 1319
1 87 800492769
3 418 523
1 1194 151691985
3 1093 616
1 335 489583504
1 552 78386031
1 1571 849722082
3 369 728
3 1365 430
2 985 252912863
3 894 1107
3 1027 871
2 455 332543221
2 1116 718792660
1 850 193149875
3 1508 950
3 1459 282
1 616 461436993
3 1332 1010
1 374 49172293
1 609 710310352
1 1586 150477679
3 1035 354
1 1103 588382447
3 198 1190
3 923 322
1 762 655575968
3 1678 750
3 1208 788
2 330 635574715
1 225 658531931
3 1040 468
2 1110 457514826
1 1494 145065176
1 1232 839686875
2 1237 134018253
1 1459 342314133
2 75 420520407
2 1195 185305031
1 1257 982921188
2 747 658988857
1 1044 414086730
1 1079 64409227
1 1422 735647528
3 357 359
2 667 999596292
2 263 855902427
3 727 1601
2 1432 510877014
2 698 713834132
1 1253 223003608
2 782 620638477
2 396 402959801
2 1013 259296633
2 1079 628280725
2 243 42335482
2 1547 87054154
1 617 329478034
3 711 660
1 495 723564381
1 1185 981763306
3 1138 841
2 1649 209572073
1 647 351281941
2 419 427005747
1 408 186384698
1 589 435945757
1 629 474248723
1 1116 911061381
3 802 103
2 746 165004857
1 680 482787312
1 1541 422005908
2 1266 442154645
2 1640 399545924
2 1605 226450885
1 684 342334143
3 904 237
3 232 1300
1 1395 440571751
3 311 995
2 1315 145083252
1 1151 119165694
3 833 1526
2 1679 720140722
1 1524 101819826
2 905 224305229
3 1640 974
2 1120 361697114
1 992 168269283
2 1144 342127861
1 1173 138835216
1 305 122513841
2 1453 119750844
2 1446 931563692
1 701 31030900
2 480 237946015
1 1608 620454647
2 358 843595562
2 529 10097292
3 543 661
1 1198 132162216
3 1057 1548
3 161 1539
2 6 515349874
3 1549 945
2 714 923369896
2 291 482293544
2 1025 990334572
1 767 266705727
1 1471 433682313
2 775 248251071
3 1416 288
3 1319 345
1 1259 363384202
1 966 831512726
2 516 630963027
1 1393 465265831
1 700 231372589
3 663 1172
1 410 785219395