5000 559
444760791 418667729 977559095 627092764 958467588 364028143 532171620 133241560 289938096 768996897 642192009 546896670 277837597 54008677 10485917 631543052 58429462 884250868 730084215 503390457 559618697 606675699 244666269 114911090 260454026 433446439 987683090 615370981 151848042 197745948 22963282 951859080 128745911 498646786 661193747 751005019 455205966 849142552 263466341 189760848 672140314 929816390 594509337 307463567 12771488 881142547 298470561 410781290 626997983 755354046 589524643 556278057 479625196 612887788 902126379 975202190 406615504 735148492 693805515 731435497 59480693 688115195 391986532 502754885 658945757 172865081 67170024 332388911 290666444 859209308 943297424 711188487 53628310 340736934 388766701 576477785 189179010 638317235 607817008 329727038 734043960 334704763 726969836 184372231 899381234 791209364 593084638 563431755 544973356 56364716 679414000 858564326 972968889 462423492 264243715 536185328 125195850 385724204 294443861 721585375 273606295 828402171 193315171 362194454 510928611 523876251 453644082 416607382 489487119 923893684 587620263 4989736 414938791 54442211 903974291 478469337 135262545 701029429 901225536 19375970 779725203 450206861 205094118 513938123 883233990 65128802 206354621 77838418 640811318 469147092 958949990 366194391 642863663 108056275 941625680 290667175 27445728 431759226 738894219 850279231 34016271 254564059 795120804 896689017 506615340 753990204 501997976 25341472 871893246 811265710 155376610 528445179 663156467 667698195 43124374 748261926 580918765 730872655 693585315 592483559 596666994 784227178 918892497 69427785 468399649 883078293 575485655 556846614 167799455 903563927 454390613 177311525 952025671 798096465 234793457 711308201 488163359 210396316 531657322 353340481 377021237 320486084 790878559 71712194 859319663 750509909 837852017 291836102 467115906 996075918 738469973 582518500 257304001 610906256 4421277 594924744 996276389 377899944 25255631 148004445 584364492 793299827 538032656 676714287 471490869 564294055 800604461 567983090 159996042 650199945 766095411 438740853 905456124 203112986 28203817 685924930 235263741 554416129 55776469 23831364 669642336 338047363 116649731 817511448 717300776 838591305 694610127 959041889 464396274 355474959 824433953 6080318 891758640 777122106 308918545 940603906 406622867 232175289 796734672 384548662 921444032 827103701 776994842 854074470 181151731 994049431 743758657 772233826 908027753 885716864 897734271 865557599 830569246 962328425 251014182 86771786 282807681 43589979 85182279 53890328 457991012 350231168 20556982 534166607 932876122 215367353 771322412 936736013 921471788 53459947 486514416 472073721 308904893 897220292 379430087 352561333 537588116 763514541 898945432 528137548 423397060 420016442 406750976 665862750 793653468 211107408 934706316 762768392 638949274 613385422 938349773 938911080 103107955 184807458 992535199 586099306 707687536 59351394 185702036 620803661 137060707 504752776 906410702 280377412 393814530 680493963 679864830 817528373 852933821 993548245 493657533 254998866 635971079 816193235 562972424 161252818 788620635 705606607 720175290 873220778 86301343 849360347 93359732 362787214 773778466 945732238 469299973 634295183 764763026 837856256 872124775 425453029 989289701 297127946 111898737 231729227 871006510 564109724 290576523 110115819 75541799 354872130 27252714 401999727 797233722 50159314 386191063 970917025 671518397 703370165 252231793 245757319 883327159 124734126 139742606 236611299 629754109 680877114 236863184 719005394 218484084 884361293 567786665 903215591 199626255 929787289 773874716 657712544 455096223 494289262 310039273 267027341 219271413 668170282 578329850 606517533 794325466 467733311 390380401 814627581 530592118 361428916 117950303 609409695 681706357 347830665 499040565 106458482 318301759 195703172 273723882 673476342 785553671 83661699 75142443 46609455 40005703 665768779 114819245 196111540 325111720 348694944 101134399 554215547 124607829 57511030 465371901 923979611 378169585 722430034 481231746 367816777 563679303 433680721 838071626 156222685 195196016 509174182 750583162 189095748 526011643 450673440 296931361 103566421 597664275 678872597 238315948 517558294 176189942 413698405 839436701 235448734 291698263 748334268 282606247 13749207 651970207 836312660 329290299 378426824 257810332 914157446 518566995 86750076 284062227 591425595 333391199 6241081 162540899 461641441 330361358 472927245 926320671 892943030 369289349 200983246 939830179 917895829 769075608 529085607 450211890 293252465 912592149 987064811 603619340 917308999 697239872 804932737 104567926 935994913 16544821 872630818 175991320 61712387 126119632 323058266 806791982 629688305 73914122 168243630 268730954 800187523 136992656 142565729 378030958 908333590 523095240 765909161 630011959 465584876 593795354 315850360 637370291 995038649 547705257 242455915 172706877 762397848 713186617 764086984 613998281 420624668 884600472 471494397 933626924 623013175 165398176 840125126 272572901 821133174 975956062 519161039 294242246 472526650 646172504 479665346 250500700 554744876 601981023 3234508 671131232 975335987 7056179 202774104 314714155 846614052 413882199 583982425 689192093 730304241 984911150 944985380 267144619 214399793 796545082 804754457 793929332 658904808 891118416 900210691 795936889 65564170 105626310 970185048 289892002 466967696 331727504 300888924 622537435 550379605 990840858 566960723 849380660 460584414 716453238 202786746 606474921 110099835 894905837 286466349 138029755 715357745 464752695 64596807 720891353 425666144 822383217 25850050 50685645 535273571 703995910 104692552 419991311 59968139 238164007 65471592 81926748 993996290 659948027 585399036 126492391 251369917 473164139 956569047 670286293 440160917 823574091 434890752 798302971 907003938 288858407 318211342 893446787 480098337 348705521 210708292 247600130 964790659 41905879 864157734 221876875 67908721 696986733 300182731 140116323 191258363 248338250 269342343 65533534 589059733 835623414 350369054 120471554 833762131 691957232 220344709 667796058 226876726 698006709 658743067 71015213 152951427 725957219 29618116 98256076 35458654 785041187 702629027 267178683 903380745 681865485 441578346 172414923 199001175 747828899 53856555 470597117 935245057 5047344 356697436 186009764 590719831 629262500 523858788 845928534 595138211 708617990 815560617 717335917 106847959 848031554 642102935 903562258 597857106 540875732 4209563 148276405 251141833 72458222 203173222 951849949 525272418 123109459 495478979 777814145 292265019 586010214 457147074 54068208 761467924 674102296 143115910 151499053 323779379 510723401 905034043 707056952 448538914 499152944 100442093 921028546 797181479 593385173 215518193 332305188 149784440 761821725 705942478 610994134 527556303 814061733 788261066 178113873 586149737 46031565 397329298 736398825 129600510 536654036 97119775 187928399 804571411 150338280 679637927 274859620 201572130 258844319 973864025 672168085 773761128 254192478 844634345 506031667 417851495 601482601 213300176 595801767 25594251 522533442 138495333 119175162 281414252 571388885 141531536 934527805 481349343 398869255 855885265 638149663 448832298 468737261 671993615 23988827 477932715 294242494 773153449 170932901 76925193 958726907 669625348 138453755 76073862 262960782 632309581 117207649 699677521 642315617 899551155 512863858 668541698 379620794 827354622 591201709 125453638 605945300 855163885 480336226 98040769 878665234 160980201 697488354 479993678 658023993 921660212 968093659 979425945 35759235 566926986 621198534 330593909 680181410 493493317 655756145 747660560 938909889 961594924 820750637 211530645 230305287 934105733 232436005 121047451 699042611 928116232 64339381 925863794 444279883 161478667 960342793 957252836 521270368 411600048 412789869 390214333 788514129 919244040 962432335 870916132 924380280 718779478 865717891 785174762 955510097 907972185 448348215 61188756 324996995 504962822 807851754 768522652 249276346 45760983 64926431 637880064 603906337 877106882 436589424 286096528 980464613 297779015 467194303 958893044 233318726 857725885 718555366 625977289 562724201 702688299 179759324 795309464 495989153 476410102 274017203 848640391 313592757 237532882 485730687 159962551 558489461 914056406 719467980 936213047 154465643 765177644 157478651 32164416 747186882 889483028 476926769 526780505 980143018 67828900 16886212 39825839 127442159 889609463 730758974 8463495 537853901 906837585 131284444 102397071 872360150 356186092 679029049 676291419 158453 200591927 517086027 193251072 801038787 807435325 851839644 258554527 327213005 268965115 524341941 626440550 142386594 807397852 269112692 40041302 191729053 644891084 5476764 678703817 814754303 548066259 311879053 991264393 223038813 460802464 289879865 93185209 552349861 373331878 264489958 308628183 412731718 979172759 210315462 951754340 310598462 388663339 159490628 166025419 64157454 621824546 218419837 616571120 366321665 533202913 873063058 75329415 226565789 174070873 829736542 167347460 515244951 364258100 186403209 49575655 989457823 814523313 213114867 402603710 903107445 908161385 30375428 947897286 453268021 552378 432466524 242177879 125458370 232270 263427818 10413628 544432157 547535739 703578603 952953103 935043763 972824423 35822969 178236219 109692360 218088714 168117828 536636603 639293421 705760143 525204368 828244892 272497062 389602970 771898213 621583175 736483025 561516398 639437105 78568099 529261227 68907711 883221850 288169923 589143579 469256957 575244673 510107143 839378773 865101446 857827821 4309550 416178293 607401496 109533092 544647906 19984298 519049295 905966612 351352136 42579527 71966883 302236914 491440537 976355009 398425168 792938951 799877253 34475259 134044565 409677700 15217671 289672268 104396434 190357713 318090303 801244134 900063918 829647607 800048857 996628978 276370823 715422236 492756957 262244943 974142463 308760695 974626380 484857720 640493499 855607143 126013538 313775638 291015155 157934653 30852455 128832898 73660812 734255057 504657640 406302010 440878811 670052956 540165284 948015403 143513503 312714125 463137218 953588431 99460307 99310617 557882019 699733462 176103286 682749646 761986691 854587763 286477516 209804138 573493616 237565879 397407794 987334785 213430969 674392057 358883158 476170556 515703738 960098839 304281016 56489070 222702497 989645415 658965450 658954629 295754625 318391994 403974878 788747533 428854553 978061494 448710077 690987855 980006929 147042702 492330792 473022626 659741204 189791930 989039362 81507439 323587293 630586180 624750176 327543286 371812073 259185522 887366536 887463075 834098570 870311123 407442879 652331368 964859767 411139139 325833237 155000134 700207062 183301116 941707228 609460794 509504136 945105932 967749630 610446849 198075362 487186663 55007406 963409193 73168327 68767396 546825216 663756763 516270849 630119853 629272076 744499594 742403045 308310741 113984446 436702668 542536611 932092874 343492104 408318295 104017512 815030205 58574722 1551717 837641864 648573149 978448033 886046523 583313227 894282302 47624520 709614536 712264684 764163027 141670421 737119604 132532896 515602785 23564288 946214800 521266014 442506608 114773045 13452949 558555848 896162086 604344505 438171321 383019830 3664141 518996455 461635315 585208812 938006645 66969595 480779642 851941587 930254034 893569365 963980089 372110587 688642211 312562052 159008821 513117543 43601290 320908017 619333230 425778487 381984219 390993877 782868026 432515228 267829427 537091508 585064802 956503849 59375666 205689499 269725514 654152585 1983750 80177449 890274886 720331400 662629561 546065958 165636021 338219180 694098751 360203473 795647394 280533838 491528005 516435505 732134267 964674930 674071090 937938205 258215020 850185777 911765290 57312787 266272754 427813150 812493944 337478272 749643725 227462001 236294535 975835745 307968230 67191144 352509186 1939072 690324230 120584046 447729781 112746839 799144702 141440628 630105811 313846420 918954355 438753132 52645346 526852460 529650414 73494902 919188673 126105130 726947972 102689416 950074879 360625092 607225755 545087974 548839178 654866872 459014708 763929051 946330981 828736693 707914725 665848898 925501132 147926873 339053361 78826186 816103126 850185432 815313060 79692087 639660496 925456867 980250497 65196810 712447499 996060367 130905389 509391054 184117353 555698444 823980391 881628063 657275247 868522721 585314415 745835120 947701640 759696301 498012439 853962926 435946354 789551768 186213122 579211894 662733151 654990189 561925134 709314625 33204270 340555840 606362583 541956839 427132013 971796463 847705394 357049476 993786061 833655374 296753146 920393748 845511933 714761693 15460806 945085951 958991551 584944387 648086619 365813434 293702900 173423136 44460207 465840557 314634640 265839263 507499493 305612486 570294690 938202129 623957965 993852031 550979487 848554337 730404908 181063506 482655586 468587636 333795789 485071800 112052099 245181451 382943498 747103359 427793597 551649552 378027669 389397602 657571291 488420434 673716163 78048834 388679696 725717140 919010176 239629773 69343830 12664139 160535675 954630461 894007987 668342501 550242492 81038687 749990067 189686880 565174299 195066437 508125730 309721083 109179409 482133585 120148525 97394807 755118798 248892830 397518810 225101005 543711383 903268174 131935434 314011705 922338185 6633796 623964883 781853828 800747460 434309553 100239432 460820029 490463041 632540699 696295430 878416871 918083790 428805267 82133549 492485842 613669917 645537794 801419147 268408681 782636529 924291604 983045487 951367002 803214904 5205053 935979205 638392704 81430964 905815846 462126921 953939266 837894270 183821635 450355323 830919901 433954254 477490783 257591868 84032627 504516390 540732694 452355506 280402833 973313676 130445883 361274256 742751023 931126272 368806861 830511819 524213266 357777577 731427729 318308985 434162078 681797695 884851200 528612549 129508656 17727862 399966521 731484719 838412662 844463826 272968930 543799333 147370061 178226734 21902361 436256206 263502010 122669327 863208405 894475978 932250153 114434594 305537577 429873121 19769553 411286700 320784319 271522861 717868621 475413867 576578475 544410462 194892537 177870775 64630083 386621065 683307696 368214449 597923915 395673161 97405247 115973603 994270241 928728768 394651397 985774359 691488497 741297620 817598337 298970747 521640817 22900936 991159132 340358651 780359766 516435104 84336655 483897893 440277025 694021080 560813799 400758353 617145868 545541303 205869872 332570396 518187625 907740300 397942600 626862073 862294380 328131521 893808029 509927003 51574718 381019501 442736134 845427214 665770586 717371875 426153375 141211032 97464727 479110962 855135659 965646061 600719299 764269511 395519962 897234266 559252140 147644685 434090083 176419416 562376893 852748092 780039686 864216323 38381156 967116053 993554335 13432111 410146099 203191158 216058536 378881113 38600078 623849858 482205783 819831197 756529369 940208514 955160153 976949755 417330153 403882996 100178769 77585784 78471088 396102425 430959936 347999240 822777440 942217548 321412127 374056771 717089926 522621941 746847975 861424466 704192617 577879283 106975761 38303448 682524498 166943470 806746146 983933950 649014116 156663052 823418530 641045926 846565458 586174215 558937589 33425717 662517381 30278264 668764545 834652811 539164917 771424563 279953131 306413799 141131775 365466224 50835924 581994237 396690047 515102127 872416148 410839205 142230856 14218079 634693992 960373681 300571855 573393888 27969460 998077002 653686642 540714036 970104177 244439457 706192142 118904533 43694334 650335481 801782973 890644540 166783452 999611350 865007387 382605831 846148892 354300087 15654805 128977161 44471702 79896533 513107100 802600919 898293991 599108652 923491872 472354135 340831932 524381118 584073654 645560368 86951193 264505757 617317090 718141314 763410349 502626488 677451483 302856829 159145447 749052313 825379370 254527814 739123563 294567973 959852585 236908004 971973321 594171370 305814346 807622871 42020743 690792585 751013356 916202541 393848817 318359747 657808552 453230271 133838762 817139994 607597832 714844571 41796219 156412131 645597533 668141108 629178564 394707328 542521956 868428200 948295573 997368149 228688739 96876463 399674553 750155814 94143414 356016439 960414895 943643588 606097415 614068659 306042582 513496462 589011556 307714262 601079252 837232211 937893698 881795220 717716876 334971201 412782036 696711311 932472763 87791186 93796733 498223979 867226746 681869192 130714023 237820084 437119211 765545175 211454739 599144518 599561009 747121524 568716326 285563808 489377509 90165366 380628818 725285731 55800912 394351550 916077252 426427341 730377021 320793688 752198904 224863645 484377090 74442639 550585624 786296649 974924764 748220841 762131937 913923525 400303721 24484803 429135773 765944231 617713026 335324664 709738107 613689869 651636633 316239248 746069269 763746955 310440565 400354627 350822034 348850606 393230310 532167310 998907554 960738611 37255689 245855404 88704905 608084708 990124702 950215419 627306460 893155162 976391206 734439879 167179351 56377014 43715280 441981502 899296463 221503174 255347668 154012517 249560372 731389016 195021651 469861024 885165596 456002861 652620195 825313759 215805142 899401208 516036364 872394405 907653003 376899163 659851422 590710640 139647965 897278525 465484008 291565112 369290716 567708237 331638219 750217600 878271511 48261775 189929923 964329312 590360892 448731724 229695391 574748525 737079386 559534970 772196294 514851873 803907827 393472349 513714415 878599198 897843455 623147943 228258925 90292800 45061967 106356413 754973791 299681660 457492965 666176966 662563597 569534568 655034250 744072751 628186838 568306544 911857371 177206477 549275504 157090443 351033255 19820932 324094532 144687036 425708989 586769194 276200526 379259669 972209765 638768982 681194834 704828929 425102507 41004978 159746245 396779928 292655076 541517972 703903049 974729652 708276180 781329934 159106925 411604289 307030799 885793628 555396468 789868945 987648522 944451194 177359440 899186538 463155683 815167095 434161985 857479594 419905411 16010906 660192631 168751431 371203511 211247451 690416487 128656791 992064861 405827455 438592503 132924936 481950128 9258264 990251536 660414161 927729140 474966305 506913571 814472558 442906312 922947955 271656306 801993476 109462404 622351352 195040199 443162024 585226608 130154774 61188696 865542517 136595968 773166461 355049840 498311630 436051315 235947228 420736716 759422328 446525992 409554877 200641164 895032057 354082419 995434928 557856924 24712770 411546333 842654985 647525546 432195232 356936617 633458913 165808665 335046205 572328259 546903802 900428229 523013233 704164739 544176910 44328292 991367553 210146633 21013748 965975541 212244617 172918573 841490121 851819998 351781420 799484544 125195529 534314366 475840757 843756419 10939336 546989673 537859259 938329870 306491997 972314860 280958271 544104452 318658934 389032572 69437887 521056900 21793423 7813943 611728772 390091509 915376989 277172765 746769780 308746849 560528592 366821267 669091768 379139439 345792204 392464464 567315748 577544889 79471659 105280042 819334259 30232085 45816848 514564571 92564601 442908134 247035835 476697586 550046136 673714619 656301779 294976673 15259041 152463930 105031029 728096316 292425308 323437266 837304513 107963513 380245576 343678141 857838667 230132909 728755953 919743288 919981874 828158852 75587552 827359952 101912505 201819341 466874436 304364090 600200222 464860294 858352491 782993877 557854157 449436058 943013169 897221917 222881187 251751045 434391105 586471606 367596316 695805520 936100943 982060450 151166520 159855997 563980009 760150764 126802335 374319814 662016493 855300688 763581971 147467495 195537621 90056095 214569276 352386853 690108577 354748889 475720873 330655938 737005965 866131557 160182523 257883759 184136603 515432213 486998142 243795924 52153534 768159833 312519841 693690217 373245155 312075371 312230306 689927225 892422847 228615731 658469183 599217785 610476345 773816277 716617136 610812845 389227054 166879685 329463747 853916553 484970664 190564700 762702914 73272992 204741639 467616070 90883327 118219124 771346419 438958938 310949735 568682318 902885853 82523148 425809447 925509728 34804604 823960962 108619104 95875336 152759333 447526502 354569947 704035165 345581215 36347637 594756888 400940571 614010326 84451464 148482482 288703515 954213473 529877299 886370010 717169646 626719684 561925037 573201517 855409535 181815322 745904231 205908705 655931401 266180592 728743360 834202633 963226260 922288103 641082554 437617020 943988392 758222555 820004891 856172441 352232572 294557063 125777016 360055966 59870379 792305202 435179468 367018294 262940143 587074413 583026596 666014142 853966046 644866430 267358794 111909077 796163069 748449221 264326889 555660994 332224466 245918861 230476045 222198056 267966525 8853910 305088522 129329887 844912773 13830351 660454317 523786603 723383949 275322745 546602199 634531158 669295311 807777159 359730415 444347064 722675066 273815504 682789235 877728944 885547637 130520740 950317247 143287312 320726517 987563816 440883921 136124123 506811716 13603432 203544065 802014586 789320690 913428338 411235747 802440116 993004090 853427752 281546189 568888138 971842503 437455632 36489219 65006642 289045632 432785083 707668558 29293245 600507450 541473740 953589047 97691026 480407233 312619700 916852867 599123377 176338263 668214475 384016112 237636642 262149150 49678831 854044447 629485609 858297383 149274293 656349553 412427031 445265846 986909518 519464574 17540731 637638192 148929443 638543559 243517190 88364999 889136232 382741042 861659764 830238800 228189817 355633588 419125978 538873255 504593516 171709289 341643938 301350457 701867713 824811485 396055719 684294742 91320592 818726995 71052130 662246899 341111676 669739890 700953770 191540876 534604707 514145188 926287689 337375221 754078299 323059829 889885544 66565292 587147180 667771671 377104826 286425177 15698786 63944757 196774927 739477424 813863495 862134645 876722638 773824655 666103567 264456567 690592838 390529184 322526697 114085825 878199365 650495127 120321421 758369205 215790934 23987567 988032112 952290872 470102668 55919276 304060804 817276608 223103811 540198148 606550223 896181387 294348221 6451715 793810629 362872545 659841989 18176903 290300718 174821892 239084232 688771124 933651319 773629251 478816414 507894679 490341008 37012362 422088356 695903395 844047792 24105485 708873690 361516876 242880805 280069859 67585253 110325252 881838005 657222416 474745249 832823570 580625987 807623320 873600149 441526273 72128242 849259437 415916635 221736025 577197494 785869983 607930388 652850215 69779410 805588748 100408954 391345529 547985646 725737544 779052803 274981459 562101611 191672616 215563446 98526852 567843105 282777632 899004874 885874977 134225317 769738614 866434199 738403734 985291879 65017928 266825692 794113378 832138791 995853500 808681169 582863800 708998966 567897772 878135370 638414394 795675488 907011752 608743495 81980274 141379500 260024140 775984752 959749621 683899010 749260703 990074943 150481602 551704695 297728451 563879777 503979420 215415765 371655133 163116038 924357404 648047494 800915403 338648319 472495527 824407158 594347357 159982210 473495275 275739998 609024433 218400554 430937772 169268656 500475208 24483893 832729590 615386626 282257809 821361135 159682726 923608248 281326087 867448298 920039731 786546811 387836228 999167460 746551417 554998947 744659458 655792841 627500423 827617014 384183726 583752950 905336503 872955709 619462569 301328694 314306848 931438931 12025974 622110276 691075966 555676378 773137730 240773457 26606471 875215254 135355449 100385945 962365149 772006995 638848753 447786315 169111959 690338505 613552969 565886946 98028659 235152694 557615785 77533567 471807753 935858109 768878691 81394869 40147560 950259902 404169491 715907362 407694073 95133143 753983312 504984016 588296364 171358919 36429479 158316631 479408940 303426690 53806264 961408783 718552518 596195401 690486019 881509980 830969019 257854937 234616969 276228152 202022105 66458355 593609137 390583633 82157353 14088585 171225466 594263968 778002518 928526075 178513040 680665379 830060727 513026722 413608210 18359797 884853062 440168127 237119350 306003836 621659608 804179899 922318238 192615864 67463338 870278954 872359939 975122686 29076078 866967680 231434472 894305344 276808320 136969250 248545937 159213167 200798633 477852381 660107791 989172443 496846844 887871216 777169822 473434528 244915711 695269930 148280375 121083078 720579686 867469367 759103858 551896086 503056311 850123130 904808226 768638120 294079229 257701723 153276821 844002647 980955122 410012794 52990208 430932301 94692407 868183475 783955242 943529619 192346055 991892298 205943011 361045730 839166289 894107382 569212226 127810901 975943406 4233862 569224126 895192739 697677706 645394213 717916512 49485926 638325800 892492305 455221095 295181770 283609258 672149107 317016422 586117088 737929859 716801115 202613855 299365068 207028077 219030886 198440309 649994718 132821687 529274678 580287981 295641458 254183612 725007102 774144865 214271383 500503005 506298183 509506856 932352617 433798894 268148059 135452615 600453912 235413808 312614118 323248543 862282010 749451351 306039539 128894487 782987761 339015835 217402254 939793083 191687517 729744113 896579735 28192402 410906662 240301396 371662398 506011593 492917621 993996811 285777564 501717167 511876411 328235039 102397714 842660535 580312496 186843517 294319397 100670468 572278997 620312362 970279343 229169528 71776614 149363972 387105616 798227396 394117073 734195082 427062148 951791664 368130271 190115193 248955532 547124221 757410065 58134521 244759245 923623478 196124338 401137972 565592838 939581434 407377545 735250570 279457147 581395103 782150070 734811522 123065740 526383247 788917044 903704903 593771252 41815607 678316823 960434468 95049184 714055987 748910611 174735406 985767592 44999731 725342077 22974100 804626834 89489047 215324131 996949491 786870948 387787158 696015056 455146347 81868668 404010509 718393711 933795219 467860624 1035211 831822047 759826643 34860899 727140384 695800102 86286019 867901568 552852013 844135984 613366853 170977749 421784017 487595548 338318265 899476504 558185060 563655026 527981747 791734308 622733891 968503540 623068998 326222334 196906772 93740398 892652113 422395752 673877912 917783258 15732542 764999920 516965733 921347902 547897032 457161605 629897449 855930271 79209307 741122211 213440972 356818958 650326701 871337454 641644040 260092558 922471488 647011617 804481761 957228556 169775227 428137666 962191619 764810634 52832970 371294597 228808918 59809888 727278851 986092706 920834551 492885598 898563591 782654910 866928102 592085482 68766656 440411723 838660023 736114214 528276752 152198845 515671059 927695498 189195778 275765601 698162534 128555775 635038447 60142505 753237571 895551841 151810943 493942757 598704576 276710801 648683196 236667204 253295046 958007017 825202662 445836353 919185671 290148572 729006927 586727723 940296068 119828569 858230946 931904140 187347047 387679102 521472227 343109063 937261678 767471059 802452008 595178551 994833908 944191039 30221573 852451960 608796591 404937436 430720445 879057509 33167206 580362848 370474340 604899456 865546973 294871132 172306163 251771610 947986047 823681253 515201253 498507548 18882922 97537592 714400654 182913759 732386424 78768601 306001437 547083359 24201672 259510519 184058445 700673824 963262909 273154495 697336512 8792782 480911578 382725880 603563407 533451242 490124702 659752496 83668273 643608485 440362471 711063228 461573605 793372564 923680791 464722197 54514015 470612161 17625305 319760859 342266774 957219522 788813722 588502677 767630005 406946980 174947891 8806671 989600228 635586635 396435946 637204436 650825257 601316742 729050906 899211825 670796355 280401724 379883712 519138902 363287222 990892993 917689726 720621979 62448804 391022082 999447190 572067649 687445431 121011570 451247423 470593576 329061778 491081605 107097622 211689225 144078475 408977128 652065275 118766579 264421174 62631718 987690958 756874205 927458137 734334367 163997031 203269177 683593288 437276761 225970593 207418296 310415216 572425505 756960656 256850099 731843637 317080120 679953918 794533773 526872147 724682689 381676239 224708436 177012073 579754832 125419665 209557658 575679315 222673174 828993325 763112625 299167987 467372778 798272688 99628369 594457425 209718358 604939123 203338480 615534119 355766978 777766118 231381114 788285880 165875293 167589491 573438705 174257447 740857366 620542440 844818885 372275857 767718148 381127125 771900912 567850322 637762265 840741703 823458494 766849051 145336273 199521220 271236595 212930680 659055076 943988460 156416435 603799026 916857555 194773236 906522419 738212764 500087706 399394636 880542661 763536123 778509034 582909635 8464122 140590698 265689871 686734352 550022045 759077153 515309574 132748736 940423390 716914040 829738670 462666416 36420123 535943383 152237048 105582082 69962217 598782912 854619787 883256815 576323429 255575383 128962561 425796801 921510731 872372072 133388029 454549927 446892899 501307909 251081089 186519520 813138909 230671750 828716480 45186913 481291722 289527606 313604877 463113183 559699244 259743360 994980098 460895012 645079583 142681341 127297508 119032553 152076326 121959993 872651172 272400533 55632332 856752819 231841660 254396480 386056890 631176640 297013481 969964527 667226626 353775904 706386233 372718579 869127209 367366698 683971606 280060040 251502151 358195546 507609833 366858217 562882077 34072149 571206474 585321417 591743127 974471690 224563558 515535053 931824369 908757021 687234530 440911056 664590381 816098953 537920176 508046867 579417933 451990140 887397559 834065367 508051617 545893681 90907332 904935471 578234584 993798376 805779340 340958711 534940212 305737909 982851857 170230998 589152228 595122727 591667323 532492638 595571839 730027483 729173091 200242460 13857483 199303010 625782713 276100679 309248514 553601616 365588402 223324220 60172767 491119828 886282463 544235313 953688364 183687532 577718697 713236552 422441391 401385249 28452243 562381963 1604694 743361935 800332290 612000030 961380514 43590710 887992754 327885632 566256331 111771719 436387620 326557570 809177607 82080234 536859024 530186016 261725491 963771127 672992550 95968658 308043873 70129583 80837961 902062199 707862638 682683483 883544000 797422378 465644460 630799284 633433504 31609756 945850629 571689788 78496604 469491357 134409921 162189897 876324777 815699205 314287100 791704988 297409617 76260245 38093788 298201076 908188548 479999993 319219522 696788034 798584787 675952717 127841105 106686019 399573209 689988154 554030741 707128510 662043712 923056446 149791002 481301626 532456758 975230558 98398315 453027775 199223647 825236456 395196202 50913887 386628286 434348580 353401347 405775301 307516030 354484956 26279013 498547159 599645605 88915789 925471341 306146914 981875864 145902517 718932218 424680806 496456705 178204715 706815618 647276589 171329743 876161611 511948970 246891130 71605519 561406404 857537262 790455039 309049189 832723074 180333727 92522161 279198368 812436510 172369042 52713188 579156407 687592880 411498985 883387704 225823909 438502720 349706433 533876955 896581738 547404651 887426803 237192689 356211702 893454717 145612141 161946609 7112699 584473781 956030662 479331350 119335432 60992292 355394873 223214850 598259090 911277327 69277398 928318330 346281510 572797022 558356793 175007276 559674282 102538568 364002061 496582198 230735853 982566415 206022753 751774517 37968052 203789158 686252705 493971973 311489276 564705418 860661052 997136762 922122070 770820562 488131281 382510211 325796104 351689975 292676890 448206514 914372466 297253138 363215151 210681620 698398437 52852093 807646528 88419839 317441092 540497705 350568283 656596077 476927541 755715194 650075695 775528833 964108444 805521787 711826148 445239357 156942369 502571024 452245583 255103766 684789295 146354946 681507755 176350565 478921036 972709838 86535110 589234492 401099648 594526315 772909760 506197341 328347338 205031879 910286509 263778894 843295004 500045189 330474950 516724516 246690797 927343453 150076139 732665818 274831169 938229290 262963465 852078587 135170522 218938878 517786450 375554067 601501290 336080297 112695689 988311382 597041261 394771742 413528989 255664589 8574410 752472088 598236236 790209895 79652596 542684186 949001387 400560585 289092187 767623760 166926356 111667824 512882652 8441392 785214335 226707482 34148995 787863327 408853338 873259895 523152965 409331899 36208277 50035717 852421553 754498853 471182680 609646991 398681750 724131980 381226910 696563755 934788513 840679401 547527701 425492022 893536380 960412085 223426984 429267339 235855902 513142171 126718241 301161834 2385082 274765333 487772181 937838077 214206425 340149096 225713650 973697382 630866977 684153167 774817872 766082430 72437041 813868764 177642567 160702682 728640264 26390018 844362348 1687796 23290249 681528435 584233215 69703977 881215741 268385262 905588718 558133114 278898925 699923178 274268205 851851330 777776590 837278318 869493331 269040525 198702150 177173220 549246062 768393630 322600341 402964744 583732721 688980769 7462423 451177114 374476491 336199581 80441027 551797215 960387565 875470412 536760275 409739804 60536581 84929416 868706608 57900370 803959995 451556680 828893341 426756070 203589426 8983492 442423619 943880969 404124120 130350102 957592120 623432992 970257131 529690665 137132426 260254561 666750765 900251781 514607635 596930392 786221358 342557043 321657375 369177629 121281036 706064612 981650893 899908351 958043566 777941580 490361846 335297730 991251535 534373385 489926307 31961975 970539759 768262755 427883932 634800706 358369812 170460636 631616441 22146361 591011144 154460397 806884064 911032603 204186322 763023175 269943205 738333032 886862805 353196628 433931826 91162544 91836110 355539137 755853173 44828330 472522829 675964206 734281017 394944059 794560668 624575808 169141363 170951896 856958445 852453156 84542946 988352010 277945700 237417070 904811810 54742316 578112070 61261999 904817711 892550435 986124632 855016381 655368286 954735135 296472541 765878107 776987572 531731475 392807371 935680146 42672671 889296193 377263600 584028149 335079260 397514399 143927695 247341523 794497876 152201993 842725358 620988623 258904091 361822673 710649801 283747847 524679033 198519075 107491157 951617677 500961450 462400480 288068390 315162480 166952692 872374089 752140449 811919978 718693479 326859377 436995271 204287600 196486376 808665849 290715058 695645929 620196047 889347622 362223977 520443014 226877579 563090732 79410218 462440091 250355914 361538474 306226201 552756789 330978088 633519628 308254679 969602143 294276506 233501647 936346440 241123448 500067994 847161594 102484159 206011503 344787056 150420041 867434585 821449872 683564262 540500412 846043183 789468462 601271036 75481255 938480988 755196692 702868873 771352778 838636031 802241848 442223336 736068229 287238410 934147967 844877439 344756888 111501912 151870816 137314133 288723842 262334807 386831789 1950337 130675151 371313208 683222007 315909679 438945841 210590595 960355395 746839740 375164319 948277074 497986339 381833638 727402617 286008483 274175066 959495980 461990906 326314760 168143894 972669256 749168543 887178915 867431126 545528893 506884647 326782036 210543170 720524998 480594659 686848224 616240474 486824292 336548807 266407228 375766013 230723648 211695085 397118861 105089370 41611527 833953198 596770008 556009557 779566661 184082599 709868949 40586274 733198383 277194697 471688867 225915993 917793697 379287319 105695360 371327181 314332237 343647371 322822949 413556218 312428791 144695080 684057218 622959356 687386610 850695799 385149294 252142725 137369274 126115536 419336136 591150052 457976565 940602633 459967744 518932145 703198029 681213003 24059587 74095840 840644338 407192166 379114115 621175059 563018090 322533650 935417893 360573393 238535203 293651426 149632956 952073821 80379785 688347369 720554948 977039499 172710409 650308164 519674006 322273658 64370128 648476945 186175555 138479043 770060715 395946610 242352654 744188401 480513785 730586611 867074285 248241907 647351841 862258097 65458964 993652932 214969360 430129732 748004779 42184072 470851511 512107876 909741940 386922602 247936988 55722892 947064662 137055953 568907327 541607570 501022928 10516757 528556406 51097956 337084657 422247582 845246120 991600604 792159278 119495710 736575320 483131379 890792841 549427388 667642753 483042840 748509904 139895255 659353982 472597337 229848761 315683228 906775013 737516793 359438087 572079255 410279720 34785601 337115090 790722226 842150239 835493626 842473699 408973084 562312007 427521352 31213022 291317560 627569247 877742607 194254696 172714726 603560348 488031900 38422109 973123628 579686233 743054935 903995279 308361728 203412383 143257621 367225222 674222490 90174876 406595883 857311154 257367095 995367074 769269402 785967966 445851684 934007917 9754241 668441143 843108302 54021831 601472549 443931687 259939475 408542693 289932351 700188926 630482349 556810244 655246919 625732434 458305711 218825311 488637888 976083801 301235242 587032755 938285198 674792281 622838057 721560524 589555031 96014417 388809579 463927666 642714471 381533745 960105820 111359220 333795826 125608107 945909115 17996922 265347433 203568199 75982926 251771477 817364956 137474830 956448741 420197275 772061459 226225826 305054082 218609145 183438473 909264631 442184793 383938293 59817114 908830929 610451954 587044682 774014565 524097891 12271852 100179903 425411020 28184434 857055310 827193345 153878838 668673875 86843310 765480196 716867513 33162961 839273413 901078844 949664472 211292004 995698175 699502774 122747126 58192603 778983967 873695877 633562694 125479789 805035456 570885919 623070388 280977352 250729137 559252086 387287147 947345868 665993929 71959711 38580842 87507135 439394545 899366453 293320574 39523700 386200284 914586108 530706143 487439604 670465791 239687164 17341002 801264216 225441016 100060367 762033376 531759652 929961541 706965077 982640638 184170161 152392994 956550297 656354006 443231690 310600077 900614290 914515680 392596563 330398932 255542687 634379096 74996308 282086082 664063433 538759705 313044680 1189508 526019748 410818574 656082431 344416932 343341191 76581957 434787310 52138930 824224303 939084652 32641595 18790579 7756174 957373362 230264634 41588768 52485810 720289814 742049457 988327343 696518787 173194581 219108052 258241090 592554616 641659104 91938404 965006637 630670317 545240485 419223522 848255841 271768392 651563866 170233575 716050583 672104177 852210084 964545893 328920138 832721968 375191642 239107149 586070553 988388048 393705289 970572305 644840317 229069407 270069721 431459361 84864956 149838106 415626905 521428379 538762558 553433652 446567724 90326504 110754847 472745295 6184128 135314058 377087460 597122662 406811750 463073247 985341110 50170001 435484112 806334345 80103682 526502732 932829105 449975941 667262966 947327397 564806006 781601982 992118175 286468951 813573527 783887491 798761802 349560363 972204261 15547316 178771370 79748395 93734672 673392612 90493508 23193508 182601007 513973865 428186106 685078739 72362130 250022939 449693883 717371692 136980859 557245481 769570080 324712466 998725856 623133563 451517423 467707145 943481489 155138323 348490783 348224625 266021022 177067417 148642046 420243184 871330599 962420556 142264488 236483248 864533296 691580167 402708234 997809412 550034290 421581528 930985347 733276455 237588119 469942262 173584073 270269168 404896757 808409842 931628534 761836531 599291980 449759318 372238899 211244336 850747007 774674897 266214504 69924750 711566275 526464029 478008412 29024704 547674370 773782923 187706310 943940767 246158420 108577538 450967923 681630184 669396708 937371718 294275983 304631421 553677305 652555591 739014488 954336895 610257321 795904874 995269239 758299766 30124383 416851123 337971270 962206733 305532801 758808416 88533222 897005175 874548745 422375292 647601383 208374398 607009992 430720796 429564287 901120602 545050176 85944271 156756091 30908224 684700357 647569974 836578576 83532308 263102178 890374027 170751538 887571877 600763333 247849314 939332276 503324641 322468637 588582225 902623671 672597724 740918449 281218650 663272260 427528069 306842696 148503965 833054046 888055118 773270434 272922457 244990885 610521094 338128583 923758853 605614015 285121081 638243755 962041556 516428252 759051644 615353197 929069614 442671272 385183202 651363144 799308084 603665245 737529963 438371867 257043345 233995103 161570669 264361937 60860145 43103936 434264353 748086114 370437794 440448410 378774545 344927280 781757469 97931538 665499342 199694194 371960322 450303365 314203815 467646543 14024531 47126685 893368180 999305825 286039666 445989311 229608357 347466641 13756411 550200320 222442 778315739 195907345 585741496 275942247 946721099 666978736 156904181 695455856 969312793 106658792 824184782 848381072 301249338 292969814 38950081 471073764 573932279 157556674 997540357 153098710 103808394 480815509 615018718 790225630 132333236 586642764 531567299 720613233 680086366 91821221 994509972 539708086 49490686 662799845 646084900 401487890 768330979 323272923 15656928 505837775 545079765 914827473 368574608 574857502 918759046 167634252 364252182 19853790 344793010 872701815 311902095 294890800 22179964 988891806 114486691 712127248 573953302 143300525 339961417 169651472 855249163 737125029 350473737 506987728 558635536 601042348 119574415 759925693 390756588 219639660 368317143 838390576 456687876 489961996 37130130 602561071 143943621 407550514 836503430 614553613 296379677 726144770 678824183 421341418 964696534 731633341 846988859 543638189 524094102 921679994 623109545 840350170 663460181 351997747 693654484 254417253 492360960 205571359 839086745 973592215 253550512 717944845 922383776 217746624 449320323 985137007 776419861 10740954 69650682 775680101 386709963 800634233 328287797 997878799 760890485 408950735 573601744 573596634 656733213 369864855 331268369 844739587 158351349 358845960 179968517 894032135 886516586 46328364 185463438 920939583 741810688 245073122 969596811 84435560 597650373 830491816 942188522 291136601 480035882 756255318 126281193 625785730 418922563 765509530 372620095 598019612 138691839 144505140 960315634 722040364 151401262 568851213 676992327 389952972 936264694 565875572 614560571 744093804 678453588 186542603 635852275 219864088 287180797 384654139 178100662 262735901 344642191 304565688 947143844 785562288 878086204 232504827 101158128 274481214 214565211 989660866 288531298 848721673 390841821 279009448 726490543 23359138 956436457 693732337 945302590 340812750 926718920 481213000 520218001 251156167 504617168 433082814 137100559 869185406 563904099 835769412 527775925 450334065 401746995 759761835 105251685 946436416 233144888 850864669 455275925 146877683 521505035 450298508 544253362 702999223 369461836 690205221 878410756 100231400 570068591 930837461 508286463 867185755 486613487 266904531 922710024 823257321 957138111 725399628 332991481 744011630 48509571 977715819 313021263 547565953 870417858 212671998 184146311 357341223 203440534 458033615 761517276 544799865 760884982 124349366 246642215 973711638 720659501 695288243 348081546 878191248 537198498 15659731 540568972 85759566 608479029 694913877 676109369 706700872 193605249 43520072 279648457 533426767 2608540 658534764 42506676 124081426 870947828 259215189 453606616 749897916 727426775 807223257 990142212 20118613 775387477 371094429 448471262 407280206 46507446 786304848 542176332 114068416 755135461 811488693 80729371 973532171 412897517 159301977 480041620 128666307 241198330 195466587 802721565 849341317 923615717 992706100 254134954 194973073 92878881 325972511 766680660 441669009 939293309 592554829 446146766 180051153 226979995 821260840 739969930 879645347 60517045 245855475 520229056 248632854 667566672 623970153 554149473 367991186 162311441 576929781 913760198 573082676 571558437 666869305 552563941 407171647 597429357 498827114 796764147 138042692 835547324 953616832 964649999 413536162 936683042 424970356 124770299 689163975 784341328 588745204 313257641 322340425 272536172 461583447 166888597 276167940 747790905 202785623 46937557 303315993 643092313 779536113 492417556 325619781 58130486 227720858 667829500 633133544 702505161 59582320 567052993 325240199 792906004 434079185 33791520 374844256 511698775 946151623 995240803 545801872 28735678 614642893 437270026 824524226 200187139 355746134 81227979 871590393 927414098 100303027 903228605 197737737 904266730 255214600 109028752 154919793 479080963 52950165 230202738 725853655 913718200 584047082 28766456 891367797 60644105 781956609 614890682 436801246 325686416 525810156 8914057 764422947 822052787 277424389 227404268 409090003 689531932 385325357 924512522 462594559 86377409 906996349 438665328 440803219 558225958 812071434 734103742 358383228 637544767 261324830 746787474 403637361 492616953 474217465 568367511 979308426 583420137 158589029 318231009 142110007 907584924 826543356 341166814 191797015 513147613 249968611 942067267 441941435 172359800 895194355 913674906 233190497 791704736 367700794 506451728 865681098 144526733 569110545 720508753 772016519 556522798 998751411 979282124 399256420 748136422 154769686 484668828 523917233 161448562 860647890 620595426 887775267 684367869 720497002 345347298 764866469 274884523 155837271 604767966 977610976 314031928 7385195 628881166 303560472 127477510 483677976 662690873 815358965 438209229 427816483 168326981 894706885 612817155 750536602 272765221 4800485 905394215 99049269 321737394 391445347 264132256 213042992 820216671 965762201 192960647 36335817 98660768 764731695 103830363 265017058 384492827 84503952 656990719 618854882 174169299 432443897 496648640 118158584 192691923 876300193 222700234 772717531 633649510 292069933 304306559 747499697 202453239 175581804 512284326 541844676 313320649 571271568 277323074 188422025 764123944 637959060 558838007 611707104 408916513 834747078 68866263 611277948 344736104 874418265 462531100 844042511 494185470 135393720 211012051 456080399 719682274 11472331 939888469 893915422 407833254 932723885 594136113 516909015 748137777 137455038 632966207 41531586 674866587 99262224 464606056 635421616 127247601 319531164 444854161 175592367 702857169 351670886 647312803 698287114 986690263 129859459 972823262 470885682 630430034 456712321 590209421 903574806 223400568 537344451 650190762 921966499 94063792 307580146 915078294 596789937 456452050 30723419 903503184 274768601 611214247 510689984 250902056 178156939 946036901 884701554 569159625 750200023 409612087 37714872 832399940 906703293 956334018 231532578 598066987 758200583 752660498 273327088 272750620 161047443 886039044 352231095 492502919 851993719 986221833 588753900 477945692 598213867 186644308 430349232 305645273 281990213 140426247 538499343 656830194 524966044 615626292 180157538 570153280 584896982 17652725 339696960 753967584 52422481 60155305 5429539 707798079 562921136 141706162 51751965 725087975 122638092 389478143 447325033 997052194 11389215 232215325 902773764 802705549 806286795 43376013 785290714 107305961 978793979 330472661 215555009 559944606 756547734 309585862 306630158 40760529 632966002 200921608 840501332 783208130 922521500 618796677 91391254 967450792 126622512 683001199 811097035 893066355 594720971 844671568 944928831 796386829 831019703 333949064 488112963 503834276 741339082 421009185 159306154 700415979 937663192 691487355 25908796 493421021 910297073 897957444 180232154 368980618 79807542 210510979 608866307 985747720 474337183 791733140 837330158 377621107 273345239 229817627 909109431 31759671 126526316 367764301 887732518 325799365 936273534 991897892 13959421 779728256 258233085 398166950 123457877 671409166 949758367 928896146 824174492 118997785 994411106 837914942 404613412 677713000 312858817 180586621 645831812 740054356 124281597 636887178 854100876 36977984 259702480 108660935 69173867 603261795 117135844 935533133 779011376 153489087 258417414 36532425 170953647 749522181 997376966 677149376 798287712 382266469 234969526 236874764 311669213 812802548 272163085 46725574 796171732 456349549 307049064 338378545 705960638 515066453 190604407 484549104 334564910 495125327 937855652 387421603 994017464 256577640 827610533 823817586 47304206 384460861 515814487 776615226 222736865 6529063 163031776 874302801 804726923 640646494 109511800 264331609 761779204 626023714 819686072 287335582 676850659 93797711 773988757 959775771 582695220 872639388 686551152 522534810 808823349 168432336 307846832 814013369 243663716 116753476 939228719 857353732 2878998 286440754 510529077 505716776 266812771 503191209 249743624 158881960 769588537 33106432 914501793 917800520 33372521 32318200 475725981 819741340 764464718 184982576 940056069 222542715 874785599 65428859 263804157 988636440 595530082 4934029 468393914 540754888 483367728 156380441 702451530 165551245 957244100 80942829