4999 5000
214402105 858548502 1000379516 39960189 86585781 1015746500 712850058 465178709 650402397 694356034 749430896 933842057 972964429 566758551 727852389 228333834 439307255 139462587 778752307 941807868 786505888 1028882974 962622651 1009615159 756000993 707649057 820961902 407911622 543741223 343532699 135603925 469786987 1015821875 961945942 895797514 114570265 910943643 815992720 809524029 801537401 619396679 407115386 907795248 879849062 727737589 123491772 398418619 810734704 697475254 160547310 243443785 1007296093 899449711 575508768 428953433 882389155 487219801 402290516 589760766 178293231 773332609 121844479 768869471 430520226 150420808 1045916044 163098424 123214414 956879076 539415512 298272343 716700221 371208413 262388407 822392352 997387243 767853201 587416430 801655561 152470663 879530416 519736375 150647327 978509430 1052965057 973248704 123095423 339242448 48372124 664112812 715669725 159032545 563701230 728744464 353339905 296708265 933754808 886018551 3971397 143480157 922712528 28644575 984806936 355357411 134471774 170071353 755342207 424507738 852160864 861756909 656255118 679953808 274504998 187356884 896721139 127671689 66234071 185790781 1045429612 866985215 1010343146 597714025 655445068 830333405 1015849390 262126094 23503354 615690434 775848899 794766039 9476465 789809540 969942687 737069794 916563137 399086507 674577162 576783937 431975821 983599858 202590114 386592122 291440011 1061516233 855802199 818008583 193652487 411508694 516748272 1008579287 438125920 194478703 112032388 918190283 402828681 1061803297 546441218 577930041 377124490 324209709 844873642 547718253 307560957 1066048261 723213713 359902755 825576593 992643283 72675105 318680590 114314890 739071219 725474199 212564564 573353023 502279028 838777987 308276751 585315994 28535195 149980748 331625934 375307164 882307680 1071612073 730008594 488384214 259969775 256511785 847824338 401240561 1043380008 698304940 457387767 489252135 512962080 343991527 350435041 906831816 670056093 167963364 916155616 601465014 439536542 569033600 853462203 757475049 891832528 49319147 312793901 857440748 935345946 469681195 950375011 246692446 659235091 628145562 748363391 905820786 515731334 710143331 780266008 693485168 636169717 430440457 299399863 682464561 281880339 530563808 551427420 818458790 649789768 115235986 131523319 8062546 296854321 565826971 138800368 636239820 361621534 997814478 875628959 332675902 256779410 295130062 828514516 1052662760 1012202182 352321429 77754449 38218398 161808167 860854513 620632139 241026629 723725523 672628993 386168813 478323802 987212320 370752956 268753364 755540332 539745557 680014443 559018132 206922141 1059704814 1011525674 729785137 538837285 801138077 288859756 430221735 1017943247 1023270468 56204148 614070627 35420793 743648187 204264668 507019720 26802584 215291408 199084049 77445291 715240370 242757634 445459157 493319895 4678883 559127430 562879420 418751626 376239193 484482626 1017125552 1034630645 386323671 792364565 591237485 455931840 257701174 341826956 432811013 94350212 88441055 359526510 719765853 418182224 342765650 266805298 681020334 66982692 328395170 82741379 899576069 469791609 29487351 814379971 380181444 933332919 1000106251 685809541 194700063 307393981 949281709 91967761 818316191 931402589 271630913 243612132 674408354 904704732 122054206 873212974 181878745 448872311 624865710 222240594 568142793 888809945 290772914 531629161 669069899 546481318 936705275 781314751 305154572 432386292 928917586 301560917 571126286 408091340 371262225 371104349 1038244389 851019181 1059154344 580567489 312155002 159164681 124963866 698916765 1019887883 979360966 998039165 526773696 972578857 464147902 876059005 957509423 568197369 1063514688 879659737 877544610 665360116 1050048141 234812900 643666181 590661991 210671964 253117445 325447160 575835123 303784022 930497848 229486671 33818382 281824410 900841611 484408467 264097920 238278458 745329826 759507839 849605607 119946685 1067395123 118292100 483347252 721034907 701557386 226862149 76097324 516416964 425534471 107023644 630081512 145295641 363943579 686985107 172696917 586847473 747302479 896490732 488671156 396003478 658211261 338576794 27324442 589923013 132539029 1021889989 902713586 4865585 247430681 637178314 996087415 450878977 122523041 1000405689 150765370 189860429 497686296 523944661 58606754 432463013 1002421628 780782103 1060213607 157981835 780886370 317766315 152294421 732548084 324735344 414580082 940917648 997295050 219237090 239074942 106355594 7512173 22972934 727171481 845974286 979353133 503950015 6899391 681393913 338429394 640162054 767704735 874461820 525322517 123982180 584093470 945667995 385969956 926331257 627517396 842205105 729559329 405641336 553133708 19827690 356230819 656955305 1037683656 953097671 809443892 815198950 8535868 969363357 524738002 230404382 818652238 322546966 924088175 703364309 154238620 737985455 833371504 265229474 772826742 869858105 697649969 1050479535 753372512 482819672 488043903 123804221 60396177 473133830 964429597 842546718 799582071 876331793 777080128 730934073 91882544 82818201 144995347 963382281 261467154 630297236 373666612 949752350 904167973 97822025 285723189 570873498 754068899 387889880 301944092 400689845 757845631 1036550065 214024419 989296698 840958427 173713176 312969209 132141576 29439632 986801063 504078014 1011569810 1000493482 64663500 629778443 70661728 808985322 571893319 926960040 791799947 1747266 861285037 470833364 765536069 54732636 400400872 47896257 368695886 944506900 463698612 868564245 838944128 1001657081 663602724 192223850 336628036 119140560 985145371 1045659343 877916955 947781648 732800979 600422469 369499670 562362727 833341530 159735618 884433758 515073076 904089872 246657842 965188269 917560075 750050858 121980657 946514643 25567285 921997618 657259858 895806002 400523821 187242884 899569051 835473218 172593188 650742994 139429895 25882894 544480893 125800353 112882242 677042100 544217938 745000395 894948336 1057561833 502313709 525288187 149150503 548691059 294372432 99996468 27132145 537785518 938976686 994947914 243643851 77043464 961460463 817504614 949870120 266840197 407654448 391245191 371891951 182710843 697098816 287035900 99744248 453288406 315592485 709991403 847002259 529930773 305624213 446702541 492057089 385094476 226873981 241473007 843432953 198020064 694222717 938380019 580862757 174295246 680537450 683733069 141663650 499721765 322764234 852345031 298736004 354613127 640804444 297536765 873062735 283588779 169633166 472110049 653959295 404704734 315393797 1020111672 674852865 900043902 108214297 871807003 106943160 493290365 753134677 546076535 877298169 430119908 651366907 292411022 609765902 2763086 219764351 514694004 732444343 798937704 401554183 181345682 761106341 347502968 238057713 738774566 232531197 930540755 1016706637 495030465 772500443 276391781 889883230 949248968 781314764 640246061 365220382 369842420 991622739 839036862 413848759 392551890 496156005 232060608 713209867 940790852 426223085 687925356 171164973 649394941 248150345 95966740 805797093 643769865 636248267 1044451480 1021836336 936888131 37892665 305273074 832811197 181782237 1036127309 1001627819 774495601 927214555 740639541 213965412 952823524 1048450200 639933716 342235726 226172898 345112384 482238079 201508530 890236396 830366293 879666945 210180202 612326836 712381738 678895000 196488038 606343076 320637035 907668790 560258856 1056482391 650661523 265982273 347735880 970649887 968914035 415298067 829320177 315196541 847161778 663998843 621582946 136772268 183449928 303957818 607225198 670343703 430952962 7081350 399308284 655978462 592420609 135060874 308136839 10241109 865185851 256842725 221777055 484867972 1051243256 948311335 767608679 16967080 175864406 356944471 313410069 98522033 534828997 564546927 692681590 394970051 65225612 125644254 179108711 1014440373 956192067 698758405 554038108 616001428 140479574 926790331 349351645 20986401 321349769 115448265 35935236 589978959 732385902 972172398 903771136 585963718 916673520 668104924 854879125 262534243 344989900 287679930 1068372890 642839733 316108563 454200992 988004730 286072705 621911977 310522014 960534451 777834559 642463433 928900789 713107034 543349915 574727294 265451100 112515989 606341366 648371499 59632637 58410016 818498786 475447813 1057015669 289938376 517597097 682318228 513636503 547368435 394413254 380098614 571976618 794428950 198127722 138705051 665249255 501149757 871422969 799712330 792883707 208193927 376943243 276229146 635706507 4530343 395836779 150360250 952778923 286434917 275110043 594074410 816915558 503475738 773420878 792757567 354035001 186056248 424360045 576844323 394736792 107229376 624397075 39941842 113058919 357753801 117121809 365392543 167887746 702151168 349568362 491616173 610093622 1069886242 224900311 354435959 1071257286 32580740 653633093 1042057032 12892647 932018572 648308050 789741763 552325956 962192437 1069154516 772072028 316587515 787043726 987862866 291900381 758156573 333502012 627456905 693932771 498423858 87504628 141830376 822090590 616814515 376770817 677070868 127565844 410210702 787846852 197985125 837274398 803132838 791000111 186444647 592805482 375573072 499384138 662645595 256027704 115165399 488700078 709676467 37937053 787401209 677354508 205377689 56153346 439919208 414498983 615352936 1027211942 631295818 849856981 551181873 797929752 982291129 995108739 52576312 674358206 304406596 362423982 709298805 74273105 9607531 662835690 548184339 977251423 138648103 123085279 865625844 697924551 891655520 821575111 309330475 899367745 1072251253 52038641 905900161 634993619 960517304 75584065 263089137 261741660 1025495535 826549934 13442859 118764046 771531988 269217731 432679445 414353644 940609174 257111327 561444421 173106256 479584854 715571188 608590728 612157287 84414891 400886667 193827935 62213555 509970718 1014990271 1019511421 833426312 1013931182 716742526 12862282 109604495 82265165 652586315 856167523 303822406 584149090 883759038 955090967 221240446 28606021 742874114 15927787 314447324 282637510 398449751 167457559 556978777 243822758 405995662 847834887 598427074 458184988 319825551 268496859 53985337 356299857 660038358 233468647 1676978 991957989 719032561 355456308 319118198 399298920 797062148 995850238 375383715 894851809 276932422 970650931 931212970 408080203 128130689 759014394 804516048 52128531 176223894 477457706 112372142 17384603 801625590 135557071 426565041 968480954 477568298 26277288 767570331 206235450 958342988 176240555 176182015 849125208 790813324 1004532352 418394313 747740232 771164332 893864706 235242420 860762542 946020228 339018433 464070354 880314406 968829311 860454019 703807495 360221117 590716444 830705854 410073230 1052352118 285508206 25735711 123700595 786905286 934959516 14541319 686768151 372257304 427222370 388592905 444665520 964982601 53360270 494217069 99179718 500532525 300158340 225214895 179200951 995702025 1072695994 949816577 793150260 952457494 976924477 129357765 442329538 781297925 1031744810 29870612 336399673 842628725 998869045 461818426 254112584 695755135 142149158 243773751 979618287 629957931 268365655 948047679 431738884 108450807 312287032 42975291 663784879 641248343 719938763 275468358 1039686894 202894640 449426215 934391857 133874194 668545628 548872697 1059273216 986780735 352690473 352108031 635471210 388494832 640165082 251046284 850234461 844897649 940309285 307531015 187637624 129953123 218075315 72832875 321694351 298900795 806628771 688967368 332351786 730214851 542863879 681996481 719497990 964986264 69771877 479109900 34850963 459579819 609502263 617821173 238184308 619652544 796199531 88976091 376368898 526385394 86348260 183265457 60656842 312850988 155381240 954996863 930326794 379553969 1059718384 1042247647 734505784 744471702 754760843 841498496 433327739 527038275 115111548 448517030 695420463 787723254 573398247 954246312 677573222 1059364927 819363559 506451824 159540322 307709060 75447563 169053695 739406619 173505663 433227220 252250086 720805823 832683963 733798969 1071616718 871696941 212285979 246174243 620219121 653538682 856241236 332462321 964930463 1027447917 819711086 878483958 818507706 951883266 803503686 80045302 56508986 457083370 685472782 805278380 74170026 632517896 480892620 985977159 1055736233 527089142 363591383 248414441 451840362 626612607 820995166 236601382 181380661 22265634 796155872 774162571 8403683 156347797 258788021 456104725 717458789 111984448 763060099 595393717 980346686 627035838 771177162 714064594 799557125 726149983 774320985 611348423 791206884 929373608 1032159958 417668961 528179227 152583122 520011323 783958883 238825342 258248263 305077843 1056583682 492518642 3114024 614963265 808777832 945345012 931182538 187287033 431594293 294100755 515932980 48832197 786136825 659299441 469492899 986480577 841858748 291355206 153006854 78218335 818398839 369451357 859316866 244068068 92323736 123552660 565876975 602923241 607407490 680688736 632902233 922821596 754817546 455278919 824759680 836845948 125547003 337764965 908114008 266447968 101626259 426760936 236598410 1053145201 286867715 117584275 691047409 134423403 440328435 471886143 90324254 33746272 396756732 279069013 768378836 157090101 121080364 842204757 32686477 35564835 970841990 160445010 83294707 554036024 650389120 130538868 887025512 1019312595 110757251 997916277 701617023 657671211 919557741 236714788 1029234560 246389449 618013458 154142949 966736104 658291721 23261623 596532527 280143335 466693277 1001120150 379530764 465703392 127393802 78223198 1000145565 576709100 925643049 441874864 819352467 700291416 836479655 451820962 115866551 200396322 182886277 540001088 906229860 389279104 985600921 580567558 455899655 891048025 4748300 615662951 1031160998 434544585 169320410 641366345 457728086 1001392545 666255445 528008838 1067194819 297354469 48034209 74891117 524014252 463595085 548911929 272489535 1040458340 816678085 723802217 404391858 472139346 386018797 32690387 651983730 727507570 585542297 337993962 538012827 205525458 503616338 19837562 726468672 326387478 916927699 37053726 660914151 384761076 922436749 458319560 632088075 54081209 72410404 348888124 759077529 950948034 643365615 1013012885 104105843 817504515 375836796 780053183 216722672 723314564 380603145 663022587 222297689 589663967 294350604 486879839 634588782 217627844 11695277 520291411 860326879 449491573 478194758 20242965 58871251 169966922 322138858 205659702 283652197 957806382 136967899 923043354 94503202 60069663 455412754 667474556 114998156 681087410 931713211 1032558568 134059418 930171277 731521463 557649727 637164598 83824620 130080536 520048183 176136126 687191325 96796840 124114904 390148227 51964163 940800611 414625024 422767437 142633879 16281848 808035551 63591892 416550242 300138060 52958588 876645192 462356484 849790455 546229294 1020262603 624916144 280238533 971658788 938764786 616699566 375516726 884676830 598500680 411613144 170352382 62110386 79157451 198604061 903676806 133618504 299472492 469699841 369054569 979016734 655761555 95064603 283826935 480704772 15976089 974252949 907984822 852881569 1069158732 1010705840 92083421 72514796 850657135 105747006 1049165783 624647092 728568375 917420326 933670086 127903513 418720207 90314979 1029608189 348274192 723202517 20657925 966396292 240516323 1035050459 354287790 585378712 935380399 197998055 356645654 866782504 123361508 721695475 342836232 695943001 531463624 246328173 21062243 206087428 280263413 321343416 191162010 1034295091 555638486 285865642 282581813 269015463 529143854 947223052 321652045 638050133 1003150994 877224733 885290260 429711075 673377001 359196431 1041557066 727856944 42532851 100086664 719646921 970367946 98845375 77302562 1066207482 10010998 55501620 666808812 641224798 531227308 592745609 684304871 337851910 715961368 791926220 929644425 920479515 2601241 572197471 348939838 696651607 683796550 40723062 920839394 840001930 1048809444 50205595 866046536 109289494 471460465 743629099 875848118 439647603 336624413 233043158 811269990 856386732 806816332 928679714 831077639 113494495 943716885 970119144 507186746 539624129 37546694 823850710 221009174 207488793 144977757 351394795 547012261 269486400 170693136 306860030 696741732 616730279 821061830 747054392 317980614 1040896081 27949468 650067861 354732209 382692180 318189410 888794472 820019200 109666652 211197467 896536532 850371840 511895848 782948224 835654483 1042005235 253300492 552963965 678705202 552755088 352036205 169676978 497986323 780145537 778700104 787022068 889285994 584514275 410525356 427947466 308186624 235392970 340416827 146004208 57520499 124268730 878101676 657104087 818277044 684571951 833034572 179814691 389047176 298877462 152438905 998942508 149542153 856405585 546364709 58177150 920637474 559597367 878013529 87282009 32626197 823964946 204789168 462821681 338837752 426852256 953258967 14189358 35945524 528179858 417422612 1037450413 872287493 161391120 644502460 558620606 384297725 448898867 201688763 1058633637 372942977 361540745 35504656 931157337 482536266 128629397 875573070 107131912 503133413 487011404 772458013 445066640 660306739 990917529 286166198 886374151 964497642 603403738 292497515 261397812 695754258 569219168 997244444 229742868 168913033 979920115 11150019 838489174 486550656 693956172 222583785 509380064 204391676 612646042 624554031 455741000 720987222 647547389 160925638 643243099 1064115387 43388686 633134327 179839385 327841964 1056661333 77167772 1061426870 243458943 956831185 233920165 240488475 368730588 268374388 194518676 82223716 927308353 409239972 917896193 701830880 414068095 390005435 218270487 1025568788 850222907 89557639 772386069 1059700279 288231021 443917515 6760654 1073005495 483360228 547946429 520756009 912648627 740289729 259868806 242497441 528811135 484605687 793008069 972478662 633071652 894039505 72363532 955769019 269798621 222083180 37011553 472770999 964527002 1066576953 118002879 48318084 268827265 592829821 514109074 942494466 471765352 218200016 232934207 406754468 266026589 398659233 635301529 1033120498 506495518 918238640 523648877 910069766 439823521 238807443 1028371447 18950415 510062989 352864306 964660842 321890001 1004260543 1033247051 913811820 615626275 831731398 659400430 995726488 109052016 732703080 399009282 923599099 1061551158 178811931 1007840958 192806295 817794442 850059404 837371185 550929379 83555986 582526747 419262907 13030472 597268490 335131484 741337489 968729254 789512639 553072792 584337213 170824397 165663511 886838859 435245852 332268805 602041223 45452452 92167135 382808710 260008731 78889223 698703626 892410368 519144178 57086606 469860728 1038629909 159815103 621002372 216127444 3287002 417114186 77485289 411369249 651024217 505717229 292453617 542967091 456875026 794909975 906791300 743350580 821910390 749176780 129359295 334412833 416766826 224285730 1032167794 801458506 470834890 897480902 800900512 311193302 531648995 315752821 519788803 175078972 801228536 37154692 59092101 709639371 311493310 1020996185 612386760 452131874 602691808 226476015 926100894 879035065 946100347 230159701 105345170 521618519 143280291 724018992 554178397 1026452121 607384797 885455413 312660338 465710449 766921123 807230384 560364403 740129701 489308387 914805247 369423289 83555148 195731072 443489559 181452496 734571092 110329039 345351935 50330616 635881215 717334811 961234000 166308261 300378209 131584034 900875451 440875520 147709668 192346774 352342915 225703781 122664132 881023389 230369278 313309411 521471636 241394513 385648153 777086654 804793271 876592960 95358673 19058416 692334311 474120941 835674298 394578340 318183089 718814798 598476924 12365241 520191479 233756748 153534801 774968646 42204269 540457798 854656392 447476240 387079965 341987726 433123077 966291989 66269411 677761514 735864767 776188933 794727153 548920340 565979713 186469315 935191884 194012475 468423210 418780904 887897933 204076160 133676204 641884481 24655905 771764090 230619408 508975436 199327562 1193650 78776625 682218687 802800924 941675047 823374333 269870337 394621761 502066635 154737655 840317871 616117557 1048307204 46695351 906485528 574476490 659760173 670808680 208285377 1024249509 700156691 886896202 907982818 93483711 637514616 1015575342 329832935 954926309 514586771 376300284 1013791472 304605496 332223629 328052272 502467666 596248750 641043718 1002079320 589635347 935725456 45526926 316259480 596461682 994138106 358899244 639731239 446240349 760446558 81128411 559671503 651744249 428232193 895633672 740398449 289201693 416700284 342179861 253822590 475547607 451949372 729416153 559476863 463523558 930388482 1002406430 1029243534 313401406 120900964 555066401 1048966875 477719687 91574346 1029650198 106099496 446516382 959147890 734020257 159824205 748156435 641669613 1004479326 628828085 789069737 113904032 891582298 1029343711 49247705 207109060 570022551 526530782 485556048 690436454 587985805 840928217 479351148 560410599 176738211 699734156 729429187 611965309 1063325626 85246917 615700892 775075248 679961763 323199464 65453172 806851038 540007331 9971563 480500346 44097976 789609206 737880411 429438483 511174594 262221385 69742037 64432983 498609623 962396991 753601677 303207570 87084451 872429037 744709963 1071660740 362809639 852036958 541147753 754396705 620278585 934774800 990405975 74527378 1067313153 1053743221 156035863 738806834 296097149 827437427 1056250561 995909586 404280317 554164964 209412095 992623478 439324328 192497174 1009326994 747924182 714537973 623901260 391922636 408804317 816604723 754479420 331535636 640406317 968803330 119589775 144511589 1002811545 307306712 548996452 738170319 609518505 660034941 450163405 403550453 1067773978 796299407 1036454992 406756749 962749020 474394366 879135591 1050410467 140317714 328328337 256661248 16690518 902193302 814953567 269598718 508911833 745662834 221886807 1016270263 199104372 269748967 325336761 976181876 711580353 478453866 371501210 822493172 60510063 217913634 855551076 926569449 254219714 190405740 992565588 70251641 1341969 659914327 617279738 734880959 435942726 366003240 71143357 565885256 239631714 940439767 223225172 77730966 561423862 720277904 477707598 829502367 408260779 507093555 137303947 513067599 759573947 869605844 974229696 1061007362 226151542 655064892 271899383 782162955 507018174 1002866022 106792461 590033457 169228939 903155715 658855986 702160684 373061736 405114871 97810028 694388012 1067869684 738877401 1046928661 763557970 543167842 276129911 731224 976374581 482962170 289150288 499166392 653388639 416472469 106338584 666460041 33590733 893290276 991822391 211324789 1000483699 350324010 495820618 45411576 425348533 702785854 897758112 961897189 825141999 184351114 603749311 301252319 753439470 280461646 710640093 561883616 357673844 984740190 967098983 965669046 628554936 483987615 163324030 968334464 635817444 347045006 950643316 683334453 267309462 109459898 836120147 365606942 954507871 583242821 491626071 30254168 89886535 857591911 385664367 278646611 610940999 803056363 770919360 37703509 317225677 488483248 732039970 875731447 649080379 806075432 589116321 715476134 568209513 1009069020 140066813 565560612 235979295 679206119 258816554 649464325 531116955 754081399 332648401 963281715 554098961 394087247 128366285 893944426 634453798 425982536 719610287 45652924 103593844 478052043 179012667 273927694 570594569 544733528 142501864 338033561 742211816 537737218 696160356 351089258 1040748166 1045243633 766717965 995706083 840095822 1004048607 792882297 726381112 130853918 874688411 162919152 622386930 245876680 581897353 154754285 784735599 425289106 810955040 567895200 88802912 957798582 142550890 784689518 366092618 14219747 912673416 965690480 1056398598 278520762 173500203 157936880 436688961 680951633 116501532 980053231 205748733 76308659 375777974 482911650 538696206 1056731998 129410918 471688176 645233053 1013446340 335116850 782517493 535120808 513034956 731135791 209382019 770968960 1070042190 192943881 786464668 207318858 906592665 445167487 393547000 306613375 509990641 243862500 528326021 999535724 807873289 431105439 253670114 974291634 404548494 532905132 1017088484 247842759 467042716 860815385 866791185 723501427 82267718 452720266 612950823 440836948 337835794 515813045 459919254 844328795 1021280891 488767463 1067158274 227417677 674645101 679418493 449867202 196352067 4201165 742631531 677033572 456293674 56326639 439270841 745569831 174669123 526666013 529537281 325614974 552173988 352063254 579580915 419143828 12084405 583397005 123053009 931589059 260766388 950301350 1031096819 524660763 671623729 855550845 352506948 899190753 319542419 503126687 468291010 474010382 148885138 13266830 52854530 10521548 981674171 819074113 201809578 855542524 585451503 755141026 1030607350 96576691 539479523 17634318 554466612 884131000 350146977 816003033 145253447 339563271 290482182 716735943 458726184 145680465 78904387 80033684 717506144 91673210 913504348 1040161901 275278735 342255898 124370348 178476405 315658728 619721213 992341343 657220161 316388019 594171299 153583862 865664348 16480714 407659456 908079814 380192963 443635228 258926525 892581497 689949290 781376045 122506549 288899468 687913142 738651284 675615865 502588368 886183681 906348667 64345868 828649449 249373209 26955299 467704872 619819986 678137025 987964254 837352759 515555670 889818158 843883539 508762715 584025752 96842891 299410109 799530727 745731725 745547126 442136812 298816995 257327485 651888257 682977218 1029066380 551689605 303813554 52545655 782799057 694951704 633797123 778538198 626418136 494920057 926270434 186781630 726669431 521649986 79861170 989705634 606732731 115464929 151681608 234478858 609834340 897496854 371851120 933666575 276101735 750722934 956457574 208101347 74849131 820502763 611716188 112209734 49810252 837702193 615112443 340326674 746158491 1018834011 440586458 730400176 1050146588 879047500 1034541576 681396897 458574407 326872638 709439624 851479286 408196040 893071423 835572944 696436696 370950911 651374767 929394249 436470017 525523584 10875843 318765010 1010320705 268502164 126305029 1016085566 941822714 81000374 368866769 1061855953 857442468 307669783 226347481 887442374 621503818 70933274 263523234 148438220 900487434 613342680 1069420294 60743044 566994329 185124766 191264688 502531077 680005310 876371819 1013862819 471290200 9575122 551674738 298252723 822615549 359506758 1024564638 550786570 701052516 212743453 260556808 1051516580 547268468 322650477 820101507 827848147 944724744 848141794 182293009 688853180 526550125 770692411 530464619 25047000 459529445 666814412 417722749 184788853 471740455 245963770 525985512 468629554 383826141 317783746 969030014 700577670 700173604 598127667 877097673 711952442 113367823 871462895 263549060 1033839338 658912549 138849709 951654689 501739144 119549663 196075962 119726145 437463257 669485355 755439988 86121279 375168758 473378539 70939597 1049339302 364082636 451625334 1065785806 403985846 183911069 442594582 415170322 781402339 842462077 867876233 310669894 1044533334 838436821 236505728 1032650160 301737322 74684643 299947043 98441125 981356079 684569144 603469707 135406353 229132779 476150329 688415558 781369331 767253908 469346975 280630231 383609822 412792920 756373751 687562803 1052832378 1057744917 790826787 960042565 966602240 603299297 885404630 631531371 765859778 60965508 621888284 443507958 421537952 50060024 617273040 1057901742 530680212 651214064 128614180 829924684 525603879 319755086 161049373 157526782 238199546 302625451 267673875 596380647 524857918 598949331 852002613 888042653 804671548 350263878 236387332 638086313 1026285006 512308409 453983955 907608842 548118244 218568083 290941006 644172466 374053632 794084720 272872176 762259207 154258874 240091553 270324618 842950755 689383229 737657002 458990019 261765268 126246088 179111619 267194515 525195101 1025247534 1014270551 678360775 224700148 382213462 976365704 225421184 862816386 185213115 49162665 783473332 1002014886 926269934 51467715 611018155 211409906 615462671 61266193 410960771 1000549228 372108888 563902596 935685548 149664015 486117010 218142271 726140013 575382599 909002653 273024540 428099422 782104184 804811500 528429605 799464940 553541496 383124487 799084316 852488152 336280080 718883080 365158643 424676791 757379200 484703006 778063701 736979315 128825592 334176013 210881051 790355657 675963423 976598444 827702744 339987402 941649808 312261734 181082190 855554394 135841368 365591994 997432566 173659060 471673209 394015162 695372156 168866532 1046136426 868249231 365759040 601191243 444535188 70805748 1001062103 612900382 553349847 492176566 932482695 360538599 843104771 329200955 917900495 632986371 302256991 149532152 773598685 456666146 578573350 27255545 435587862 203400907 664811269 33216861 81196945 537707477 309063838 860374999 384803996 424487919 337265673 287737647 760649270 639701017 963305293 516379327 960718739 972657192 232556523 606886134 659447708 784072006 116561747 862657496 246633836 771509872 930170733 904536443 680551635 574819574 178179858 27456652 253981399 810218238 126078608 912192712 84836910 943613442 472484905 586971012 76928965 519814989 819789973 849917990 383577917 525558914 57488251 572922025 858537833 591769621 174680060 1023848988 640470737 625486288 543430953 586102052 19503154 427790160 926008968 349608566 290537211 520367237 321425555 172335966 519115729 958366773 241280312 244787770 884762892 277727353 603356250 641221375 788838200 1018962751 54748238 1005005748 318771605 353062599 723967583 368381170 772205208 168558118 222350155 327486058 1020307559 113415622 959735748 835429215 448366945 434451427 266672368 424633127 956258452 656083215 1052379369 858349999 503345733 540967087 47878973 105124852 746461291 110836092 879886703 480046218 853317428 875482628 434902901 813845529 39893375 753495334 53964856 567591387 242355552 938230426 755214871 860331039 333019295 13348710 738452324 262129865 134356281 13455978 539723493 385058256 272240094 807985365 804415572 871162303 15749745 1061703341 193933536 956599349 620084364 403130187 943528874 97089124 213781497 653522396 595067464 874038165 631169850 747478498 1044330822 224659875 420383745 377914289 542227616 133095804 870779832 553788658 863153225 202131363 363071483 1071038755 648386727 23383216 664959769 265040405 695312149 607131086 476133527 266015853 790550111 578399549 918700461 577847332 972491594 22913742 424208839 380276999 780651785 172751977 492391174 966295352 786319817 4454026 846990012 796559275 1036712742 488215743 94006771 352806057 706749108 380699180 809450982 681743952 32675447 742507016 802684038 1000717073 232283499 999534621 619964663 731428913 338271228 507695436 444847120 595145289 608227471 251327494 354174175 619959750 700080120 381329620 707882275 430501738 129266177 34855632 526085584 745133256 1007623658 510177322 294841230 712645836 179136227 1059953316 611545914 751904817 817006740 187346966 964308580 156596745 533042070 297247467 793208783 203481144 21977591 671060642 685432821 952069113 28912569 239021134 483979648 326023768 598729555 486906647 751207889 845089974 459358767 980666550 72046973 384971081 834542891 393997820 7344331 251378585 800676120 891482956 518036536 503385348 293975870 834642204 891940083 779791675 31125974 507224185 805042529 185758403 489695374 458279808 442929562 535034740 1023450377 1053576677 756974570 62682365 185089884 13440368 632852817 157037919 478513810 822317691 636236292 414524269 360231209 871549046 450013673 271249234 333715859 137342563 740748575 768842507 587999926 329342810 864474228 11981545 917956716 952081157 1001464300 571348496 778854403 869668389 130536769 914730747 548889790 4266764 579719261 930872310 778312786 95451681 900221922 71239586 499211114 224643679 685644707 995258740 1038012964 1064204758 156910377 464004662 298715282 670379561 954620463 770205829 65350458 74380558 623952165 900245842 553232279 417580241 117974449 716451937 463673493 221236433 698210089 977671373 394068760 306091521 969272090 273483138 1013146230 256897897 489959877 682123713 296977656 389300899 297925276 677978527 563034205 630062174 346466505 1058279046 605537879 605164766 297736104 266259379 850510092 935865466 449302344 586198710 54763415 373821468 647989486 514090997 729131652 587008453 411632530 147159850 737294423 342098182 258386016 265324512 61159942 558623624 1023311672 473391610 184391547 907283845 87454510 697989677 388717587 837913165 626583307 671979137 627061537 740803778 592484810 626481875 236041323 21860317 82565916 1043276118 3473580 680308518 253267941 394175245 75705873 283027263 220825277 530706514 146146492 106028634 537992303 396802387 852134724 524487871 363114621 613213839 1010721587 832896327 131852698 679838046 357725574 272178659 68143662 607513703 273149744 265642006 976983254 535981095 346295704 346024311 876413154 486801264 443366167 659625008 353582805 249759719 762051451 309641089 538922216 477938310 946415750 128413758 140811144 695111704 410189423 215433548 130580947 659033536 940996704 830841897 1045594655 785087858 849640694 201683297 426499699 556531320 1064229573 1052428569 52428043 290395630 621417682 90030984 425401560 890111814 881655574 171307385 758012414 510786757 214903554 56536267 168395349 1022722052 632005621 402962672 83966441 650691185 591297479 229061489 336195450 705279435 824518466 1029067881 758784252 638252202 633416356 284524294 772632600 747633396 762615327 142123531 178030249 722349672 1038307929 120055889 82234176 468629271 288603372 685422913 738911649 1070213094 692983014 524061019 596218691 514684687 454899530 386595506 847694804 290768541 567061389 626216302 453490099 309427442 973832218 1018634313 959670900 400829764 88733391 715718930 714279775 872534044 888766846 481217837 1028859377 1053805526 1036979821 765321745 662693977 121982244 318842070 987733448 105391613 210595723 696799591 28258163 624864243 1061303780 56484547 72923075 227927432 179524316 46069248 930822529 493015229 639582580 90755879 927488520 652034756 771239298 131930551 79819205 396295303 86125615 278773026 184347838 669126434 1043547255 594465102 744520456 298127460 213010348 1016473366 400855375 277258066 1046084083 337459398 643119442 667465892 1012239044 688744098 1066316388 852351814 344153454 347276128 130015724 1002142936 179511698 635252905 346624998 450416174 837172132 68914077 719194976 500158417 227605869 453028172 50520830 921351804 987278987 224453437 386841974 878190496 567633135 814904298 931776021 1063687648 785427805 263021378 684687672 600302998 327615472 919356198 139291859 516866380 275127444 105593837 968913134 917550660 97352586 235464929 477798435 432369905 223239656 816153791 144623650 96817531 451768854 247686715 341922349 923586623 643850322 977685625 558461852 534262348 474882861 831880085 829369946 663195112 395456524 584624412 79569253 836509449 578219943 926562448 1043540306 775482332 1073383053 640042984 287101127 786643265 1024290206 277580814 911970560 138596173 164649616 605715807 698573387 941624775 450394219 109368367 783785099 350703787 308932621 146756930 514828217 82125995 834519206 574615124 1026882654 1032440745 306014269 876520082 364999706 178590013 650435626 351749919 551676448 497839925 81908121 585404304 829795256 619872784 907269645 537258608 703445180 720457090 286046171 354037180 965497883 1031819508 451985067 1021645672 564552793 488336385 815117307 929727961 48407565 874484474 935541659 87112809 846864994 369939299 410188850 176203750 393712534 113518707 1041274807 446902035 267940222 164143000 549090297 187022117 510323712 964676848 377508632 253105223 516893079 644911057 748895241 440733207 66639827 1048913730 148353814 210043942 483167190 1011357312 310624860 619292284 562164440 505895291 603902539 1024038418 148918948 632383830 64115241 205345111 629332505 517443818 637186192 853471404 186073514 791548227 891626475 227160807 1000061919 757700130 603112189 274651603 480294353 1063385721 104066395 708564654 881452978 63921394 841778156 805553834 801879362 1057883240 701755760 266059629 774692443 328963181 202375926 208235410 403046246 18256323 234590309 1373989 998400484 729822946 1008923892 675892266 836639974 712808568 63100849 951164695 212370837 546347492 67847166 914213717 184741803 442741178 660509199 463306691 383729144 905903683 76554094 33667891 172147422 302885370 136730488 383817964 1015279829 85794832 630688733 368078118 395041512 484249832 277847331 212316561 890570038 626935452 1042903843 629326286 65865073 945080694 775013771 993847284 892466019 341103736 1013593178 873740556 831826276 1008114133 969093223 621396373 379081957 498292597 228701147 1025442306 1003607785 31832949 521816754 949566263 2585734 55285924 104196927 473795344 521262952 228911879 86875813 949344473 232578638 621882454 162396510 892015063 551828876 894826622 907240375 600454590 953642887 689308189 850342482 465679160 938931516 152753928 117575331 488707173 1062594234 596440264 989933427 1006336853 874042275 993471769 5300577 329576080 213316526 1053284970 596238172 32699790 641214248 135095392 91618090 712967487 561530735 590976082 475010532 31669381 140724085 505395662 1023862903 553349301 993567811 527736595 746200100 539363866 633939316 101731733 951792385 981708913 1018654134 271295101 441368695 959891310 45636428 178402086 493482434 648231734 366098574 137396641 322168436 162471139 77479015 548864305 185063666 688066307 730323670 947317456 330340085 373948952 436921710 257089960 78432778 24068378 1073118167 403728283 258674706 333565425 581684298 395747772 412017603 332500475 442278937 204434643 422204709 259081868 391073828 482722269 134484502 271903081 790220133 271018633 181681863 370291020 837077349 205653436 797187645 448958051 128676549 493444110 762251985 486564561 360323510 93258827 782515888 868650795 716185729 327768051 555936859 697618173 910048256 38680507 270247720 531293506 65438755 540549130 87301055 961190127 25089132 1044548988 834738334 251199849 204340339 659173730 537585302 700228363 95109219 525268544 747270476 106781601 830679419 716231758 120340408 547692271 441558670 494204408 1015954601 111182635 1057389699 847162462 121655104 870227326 136349398 718746580 688079728 883863175 83150869 887539810 202113668 291741400 820431459 465078853 742398873 26299255 11390969 1044034157 142023712 659432030 932336544 242980606 465221726 309497596 78600504 418250703 512181227 198817458 674336308 329468653 269122102 681444695 546847260 898752793 123967231 627018164 536051466 366017094 216317660 159228425 153545261 316256796 995243957 307984518 891704393 29879416 690057544 647778258 3772981 630721001 431611301 291938183 523826524 778726452 917871027 94601396 1020206141 12536529 287368617 691858011 515445482 79353708 716762518 677297648 319177612 1029812837 120414682 280470496 626407134 668708689 90234795 884488199 471639213 582117751 10889617 382862905 1037980767 487598163 973352937 481973946 510774633 235050006 158493030 178703046 876599255 867809828 387611531 110086410 897797320 449208725 479703859 594524712 1032402671 760983476 775474441 880973111 972047124 177151107 205327888 679951425 535363729 630699829 1008118813 754821316 695693781 756005555 698910295 426272817 447638756 976319000 277458366 579594352 251022292 135982389 759250337 363697241 239529298 856294669 914949159 467058749 711689499 1067593817 512588487 85026395 608255108 707110918 472583888 464073579 418816755 1035557810 1009990114 1064166167 927788643 866465331 983984754 149843069 1020627939 445788688 603536458 884866735 993427480 97238534 1045496070 380652850 627480503 75460996 986060952 354135170 619603980 553390383 782375366 739835533 925376373 670262111 346081959 952266547 310486503 934859936 372238633 208863437 330894697 394325042 481248142 134965411 857723540 379818122 716218602 1059732340 30960921 869931983 1027078567 594700785 790016059 209698909 888832001 935824706 358841168 332479813 128022667 194020224 265632325 305095371 956654248 1039555642 391689751 744089319 477262098 153195761 669660506 850692548 501666390 360719771 769125558 948243012 324094294 352345379 990068581 859007610 366253510 642813416 69128118 562463791 587508912 2460218 636444557 988573022 103203056 611479776 848003297 649112759 158505912 464341396 110925373 994262560 793953549 940503428 647865152 91580207 866286664 550590419 605744412 398089137 351207575 628132375 183692058 560411175 632924537 418091225 378963733 234072132 632508229 889363481 793325051 741914480 587137956 91783111 794800207 498235719 594844178 458195018 813757097 230480923 366608481 135294716 551841333 819472238 187328310 553785004 546701616 199610489 936393354 175077403 649269102 57188008 1021995562 182703744 782856918 851812379 965214775 644781061 762985444 193293862 602641319 31481415 251150886 1016054226 717778115 235514585 990381248 561076314 511975847 989889474 585194217 966141871 578282693 861578234 374109291 663675637 640397154 527492081 551758375 944459524 647772695 815560201 794009230 845178599 930563409 880440087 1016868393 759287904 341619153 807974629 122564626 814227554 975071533 59247795 248186489 455896982 134190669 343583665 411664160 315178711 687255023 35947399 1028555744 987540405 82528036 539809997 1047763745 872805622 972506065 972730772 589576293 591810320 497436975 502829531 496819390 21006512 104204363 819202074 946571092 830144311 467097222 146409915 196212192 563897143 837457430 278634396 979547443 816696571 675606147 862642830 931266992 509255932 342545707 257673177 325580749 36717676 852813247 824524214 284923031 182362543 539790019 390010835 49907243 91651293 445576722 1025788883 825084989 749377602 180873560 781254091 95856789 1124574 362303126 583163078 38133645 593566438 888250530 532303682 1029556373 95692353 423109540 628748209 663957167 281326347 310472090 558258424 416088307 540085781 30719700 686113523 629429003 12086627 309111417 1038085872 1006808504 930825388 989138689 415196208 161918796 289270238 113991352 1011940457 673086510 967051672 658454593 283230278 313163609 444033966 215142161 126063589 593328861 48203688 142189552 88617816 408709213 380135747 886672764 377749285 555624847 92234991 663392421 705435846 866912447 171088975 710314290 343592746 702548300 838161084 1014604346 459856690 648546345 731484610 467705516 145976372 54635614 517250466 376205768 95978620 75376517 192854478 590194595 1050158534 402703949 818953585 61414823 225824197 427675898 1017477092 756288273 766788255 536624099 45770041 966187378 926560110 320120818 1005499060 562777390 565219521 137507624 226792269 1018985983 264368409 668014870 408871984 195567475 576320877 448865125 272802109 146741610 333855142 1063447119 454502793 27455641 462978340 652764452 942035930 946274058 413278007 446122694 794481455 215055514 91745190 688243246 142764854 765024121 856667948 995943140 176944339 296311981 203574262 848790922 46740128 962408592 543794726 214099026 338523495 935466829 937590867 305990532 244125866 64523623 772485126 183966201 232824604 298987570 354636351 1001673122 562108198 877852248 560842734 726202370 996781922 95402070 476971643 802916016 662147875 422676732 539762750 69577686 178939627 877780464 443472135 615619252 711105780 268142635 402733720 891038750 1000642984 567180411 401552678 760532729 978659368 760769535 650606556 249284803 142327497 492547247 31006039 570705416 360780690 621605329 41429035 993147629 225542335 693163141 288903004 136123305 272218434 838872122 556767974 621688071 820596029 589575990 859230262 975162598 1022459529 1043895058 556215983 545157816 191194417 728499515 824081446 262707207 339370999 182293363 817520998 313575659 260533455 232746062 408589997 91765909 482776415 406101942 912416813 435434951 840104838 693348199 578116235 627782490 325679570 228900723 951719779 901214391 300526599 398495423 488180163 780252766 320160671 565452676 108839595 780696162 537832516 373041103 303136148 1020874987 1021050968 34152962 511999206 1041607859 128208238 754758993 793163392 833646473 535865550 996863557 399200308 925780689 367858677 391726908 784723016 459665410 564539667 566198503 158090742 767562022 575358859 734513867 1052188140 494383454 627972214 940391361 849442509 517621083 910263072 64920183 694591919 411378662 886798730 410744300 583375515 413845082 896681190 609521143 1027486992 307026212 664803870 474942400 559093888 578821194 94404174 620792389 885558481 497783777 193985349 66088663 367302365 617154709 917349384 416846235 514876659 44193829 211577167 518305290 808782676 286528996 714980870 905139057 96440503 642644793 483888077 869477745 270420677 168798240 1032976248 1032240256 417401501 854373287 477427088 679601766 765106514 193596530 768388816 602539713 320799848 1071524151 29799593 701974402 12925530 309463363 61965758 949209454 597980951 966821107 20931177 333061278 701988992 81161787 969077044 236554495 364622572 164757795 896611169 431040210 422436261 434414661 614615395 573753133 953085800 1060206929 118392674 765602936 927003368 32292233 454220219 95785713 141089612 899480133 350943614 689211688 212607148 240878960 502722798 77109380 338930840 1041453576 469233668 881737149 707368594 432050338 5304556 233976160 670740623 112369636 524790919 800391246 278160249 801787146 256073447 469333052 866638768 45769826 269343702 424758325 417727876 893817295 974222160 469976339 860182973 310874442 899393028 927461898 473594388 270872412 974957015 378004765 385752503 731486629 358923873 1050650535 466275784 259227480 988303725 387777236 723317215 9404861 452686717 998217765 686959747 325055662 35003461 343493103 755637 690417434 1163051 959312860 220950886 892939141 392769486 410219369 307562491 171849862 880432763 705757287 839890640 795801928 751023289 671176058 849584819 1037366793 103233982 263170205 156984932 93191326 103343864 725250971 767696668 990384365 153896069 581962903 887572739 742731121 565814715 357797510 882568119 1041748922 1069202850 987271600 783193804 828665066 532284277 212153394 70757959 811694649 36038436 923857535 818677538 601363826 713840084 312791002 230970316 274973044 652152413 626904797 494559398 1001425586 514999755 736705014 512401542 431847348 712645599 719764453 655558967 35342739 852418443 136857663 133480439 757894273 396927865 737301486 940676600 963049534 530850437 708402607 126735584 948969636 792622142 870729362 454024009 84047388 135598441 269679229 788531522 518428199 271296638 491382953 583597260 293301206 556057128 449465380 202776158 542023762 528823753 969098318 303463777 1015110485 435482101 915881308 280657076 33936303 813464818 974727384 66309929 1021423554 63406398 47154718 989283334 913028614 744741385 372390624 326820742 176967046 973089719 971652004 1022843733 83775073 984462431 890504257 65420056 109978185 169930831 427679845 621052130 844870920 686624389 350618642 680588736 588723446 466335031 171963420 92985902 675488644 315921996 854507181 217375391 192198069 415486945 134710209 487785466 496141471 171324613 865324458 481071127 202771950 350988542 164379021 1044980294 1044972642 1057267266 173862883 192109513 982085708 910500990 698543354 938930260 327491604 659743314 569317745 1025639060 494758070 485742995 214086335 1023824038 730117697 659717064 68289453 766849179 348154967 188288685 193096919 209902842 27661999 961962163 28032303 423989566 20998550 225987966 425220730 429291092 644387434 366023270 449001937 604954399 755816477 573829879 752527393 864802036 661294008 458567024 645817004 40563742 861128918 571293512 666894214 768415834 929695269 915765668 992192024 550787420 677606888 667444706 1054807968 132470600 373667447 174291474 370804655 199612218 27972285 944119160 573457578 360624064 956043961 397573387 65515594 408520026 1035475966 713732088 616826908 644077312 833380916 630500384 137592322 185260700 205121428 263686806 618078383 780052876 395562352 691837986 96670767 15908130 905884840 454020545 868063837 769309476 789704246 771579170 645819243 388829772 83196835 167075114 1039064670 413263560 295985040 1028164209 57336206 317968059 741064238 199978948 855622442 1058987706 367676870 112286369 212781491 161547856 802166578 714284989 766024829 901495931 933332578 132755329 831618097 145783853 221399768 833682057 465488717 1023643852 1068042284 885302820 142141090 1035711154 582997641 388337878 641256916 698413998 738202414 523511513 921377758 511507329 403112174 586417816 422432652 207426657 398702768 525038899 428893183 282003322 95906288 390079230 198424877 438552936 590572348 993804290 741166174 313358014 496868023 407560314 142721200 335487106 464326298 257503574 833173396 573663406 313136558 343342268 883816782 790261425 598706131 907378306 470478201 630524908 15394428 742852790 955114369 1019142198 450481457 805468182 880257831 322186840 361607692 442366104 687471872 307693713 99219004 198384099 53949174 428428564 920766085 461222868 732352710 829321861 918375358 240818938 934272129 120431743 743779154 378086682 585893643 799977489 877942720 445316524 275227807 853327932 108441882 75680348 333477193 518220407 583792009 427171723 50675050 594578220 116687304 411878603 247017015 888533560 727966117 575654246 609197626 937713519 144552067 669673687 382603728 871419669 611961306 577322831 271356841 256972390 660621749 301780530 177528140 301912079 965500211 87412888 295882640 821237938 675996423 675798989 195312420 560634726 322591737 474474448 182024456 874802741 562801507 376237016 649286417 949960348 1061267380 122755786 487963753 677269007 577895152 170865604 999774733 438681202 411161389 472201878 280976205 1027354273 460022552 460422211 625451599 480880361 788050542 246801285 1029454989 712562061 101105284 875896134 567978834 318085954 801434304 420842791 831749185 401500083 217235741 949883389 981938638 871622142 220463786
595040847 455769027 93813044 872253452 787319002 732086205 44959965 645296632 741206285 789082540 864951666 1452474 663188366 212122710 911232225 809054640 799728307 288618964 168687373 525026767 619484937 941849620 572772939 470502430 276892624 1020470614 24135655 281679158 62921596 869617839 496181404 11201736 1063457846 741116553 170885407 216168983 583375961 412096800 740931221 32960633 589555446 10999046 887608088 755077083 182335569 978047392 630266423 955118906 11876962 717870504 441564531 330775338 386703700 270410665 496298178 464382547 589930505 305730182 55090959 347159023 477342868 473789939 203318968 628465741 62133438 1035851513 281495055 482259793 307651202 335576183 892866522 1050925298 833032337 993837980 602406868 432883643 974524110 131942510 286107433 615929675 980719314 129850950 98871549 585867476 121000042 191551569 870893286 306999199 296732180 929407505 270056813 541622663 123251078 492808154 909406353 656676730 956983335 494702421 335407173 859002363 171970452 261242880 477764845 270300578 676790812 879246252 53416932 504939419 164592452 788055806 1063603193 791900707 898196548 95379951 392624621 747125006 302545032 732532813 868226295 59196995 1018313264 301494839 981447489 456195646 688797329 14429348 846542440 290917517 134552241 956899804 779339775 1071629396 925046735 484866557 9381389 167858378 936679385 566885240 895336330 830748089 782877171 155071378 389521638 872685570 714264311 574582500 964178050 808257046 874786288 310018523 196786997 318642302 617773213 663806265 891146441 218628692 104151028 810715793 931229820 263092680 960886941 503626959 449348991 308584604 631189363 765198510 538391417 535966889 817851911 419496256 1024684805 732958807 1027925788 273527913 522583600 784956200 842122027 990729060 918064381 226118190 170444001 25043773 175661537 72437905 716127644 500108629 311600711 493887498 57496050 895682530 469276428 768153962 896175658 973983340 865894660 442617108 39078592 324299345 431099252 630172542 62316774 263129922 1022385814 71042485 708914942 499625924 1036975128 992107990 84274465 230268336 969412509 68093845 280416667 441658034 513339706 991991994 250185068 978605262 92210170 336079263 626419912 967715542 377184859 390653364 85272472 449119477 865065678 662105083 434281975 1068404008 738212923 242810764 22777014 460494784 932475515 315099153 171908569 726354913 970126045 347071051 1001306391 937696262 222754977 864813196 611133534 513445499 381456768 990665531 840993869 582964705 545454626 410005843 277881016 114506157 1034472102 399251684 283463975 768265898 893514526 692314001 417996119 72056690 899778576 776878864 441306552 837608697 262102774 250923437 299759597 309948162 970062527 387015367 248304463 925686952 466929740 462501713 32365931 804521175 562277107 666092115 351620735 481324752 373119231 843614567 163307009 108149416 136415279 452177212 561633048 12474825 861104691 795429398 202046752 315201392 892762418 951035980 523026475 683503917 129045574 274775240 364757371 217169766 74214398 1038547339 385886217 691219925 806469339 465497638 97961217 268403718 227403220 79116354 403081283 231161305 961458386 154223641 897074403 36402182 210047796 744447227 527680938 20944020 140746829 696651210 535081363 1019931488 157145057 20828543 10010703 897809053 40518316 246223779 176078530 877896526 4316890 617644245 216589187 194518477 882760848 867444554 751399776 543015496 159033954 901179209 1005958615 1000644927 1012388314 617198507 409319838 597617671 24388600 934191714 326297885 1022340426 789788076 658230510 555216623 871190916 817409118 999751913 254929508 769654663 40557158 561627260 79787010 37765369 871508884 124654311 153514495 1006336721 874045866 51487998 325336264 581809629 602611933 1045608871 560042877 199767871 838323287 749890141 388292723 879519979 1032762040 142784431 639028657 560828971 33688209 405400001 1011067252 164782107 166117095 995967178 999824043 124927533 710020022 6747541 958670203 274136742 102623851 23071233 72941500 939283232 421744233 158853504 910767482 948933894 192852357 36362652 149560693 70376987 214888586 680180333 911482273 506720499 930346934 175806244 536854439 1012527479 1003470650 200214147 1040749922 807005541 327653310 875518819 376171875 400209103 1019299547 51586349 1011406701 406258328 1030026143 239468641 388036858 490435834 777839373 646264594 840348085 597939714 248841371 81703272 321949693 169948177 528305842 1072936477 445977960 714459741 96758577 154630912 701385534 995375471 924627945 841811317 319203065 945983395 742129442 967695091 273432268 347709867 475446294 555745668 47074841 864170764 6709105 163631177 974981626 693661343 509943767 433786867 57525689 92942097 479101533 705653579 13887319 592910179 480392975 982298540 143076361 53574507 522175849 811031939 203537590 737941586 780732638 444795094 131994234 340663572 312671572 1064798650 970599206 330171139 196336549 841841883 559189438 467088964 365135392 795808760 99589882 972262991 870106374 51983972 116213190 534943347 55300878 895218054 846487490 896738897 383695329 1073101146 617252290 833047133 438730398 192674030 798629967 1005780064 1018437207 881980134 154061860 360426488 626875027 422474232 62197426 173610774 762828234 769313137 209509021 718697086 605814764 452011438 859235388 212689483 425972442 568306851 959890973 340607593 833347307 174354008 682751358 102055705 13772648 399451495 872318677 530005361 762826513 105138048 483934794 953619417 473863318 267904485 597166136 764088975 587898655 980475374 1048380847 240835620 71473860 734517638 417708276 438242813 839820565 132652971 445826559 1059403986 429492627 365835506 921213693 610904370 911134261 751356929 70018252 987594749 756879333 699958804 449074050 379689705 800370433 743474041 1014705894 273304830 667438042 475415572 62601972 773678874 709563192 920606683 449997917 357666925 850746068 596991834 992996613 55766782 641535452 301128752 883191940 251306021 522119538 512020880 1017403558 836272398 1070893357 2700482 92514795 426493756 241091479 1028795808 498814983 6678788 394057390 692168473 388182627 267081230 435217507 692891569 909580442 147914712 968834846 35269119 693427965 887042610 997099064 753061166 133888783 537902019 122065535 884077948 436916234 432989826 882029238 463684798 654857048 1043972158 484325394 136712922 223904027 123745047 926405310 976989771 562208934 646213122 997178968 146205857 359684353 626662729 223919730 645597950 665589097 256307977 805726994 801201818 446937549 581107634 17780018 1062262080 870786898 167205515 1003211584 197445071 57053393 490773035 76965279 214536378 850796372 724344065 1007338277 677318793 474670748 173711820 440896923 672520790 716941726 849129508 305012288 911199824 159489 506941680 1017084486 595753019 616195489 857642733 197140307 863256557 1063262479 876377901 104243201 847145426 328496655 984183190 174788703 315352938 156704537 921733471 432554606 295237574 1011650777 978423190 737825444 611588111 318346927 133902749 170853485 780092415 503680815 776992168 844590757 1034716774 1064927393 673341249 40204319 268523942 436305283 100204997 730670113 550721591 136993026 525096676 763703013 1040989476 463645573 197453604 432437786 627487884 612181794 612319838 516573537 699399201 7126055 222906432 458051281 537252781 839224722 98713801 965576564 353975688 46489 54314192 311158727 174984995 477518372 280753790 424302653 999838081 337744205 964004303 235766205 729739704 94410215 963747094 966486559 966443380 548588532 921362806 813457587 1060521845 762844461 59478889 507165370 883875852 464876926 632472380 413327339 515026337 437192583 699362705 990029552 58972464 894222621 990077916 158040550 674439880 1066895303 94569702 468646625 367477259 1069225281 523519310 299925605 655759025 677686268 944605187 219677166 482912516 392371100 364562123 892165225 1004141157 485004665 297142975 45782713 842409413 180867359 623785164 312208947 68964397 196444366 956438067 19903265 22931768 42604026 1061476618 227964227 43826068 830395851 343455930 82968650 781110660 695057823 685017727 900147291 121213280 18200451 830477803 714925714 1060595219 341122750 567590243 779732348 384919452 191730758 748615328 384376220 31788942 709010249 224105263 400007655 333587857 664352165 427514097 515062856 910720990 207149168 429910684 900479517 625644487 449466481 719061048 787794104 892229165 1037696677 670527395 402735582 529099783 5477564 447218958 885508171 411380450 203954585 886647678 50410541 740125019 833109461 300279116 90656677 593272742 919011388 1071355045 385311561 832821259 777626190 280663050 103682724 702738276 391670976 867507921 944572596 1004283297 68895736 376310178 345404523 962985540 161385621 238832379 932042031 598044901 918511589 157733805 775559002 5532079 326897773 141014877 962822331 922524129 674758244 522888452 416607507 909908046 217332792 1045245806 513366680 553767389 9929480 73426367 171984501 63785482 136902440 388283369 739858760 301083491 370228385 80626488 276226979 718612491 962386862 759378630 854436493 657271355 351794496 861618183 965968894 776131772 519161722 908085055 943801190 321966958 666632757 302892038 1003550246 975469508 694905726 709990859 492761108 94092614 519230483 973843534 495527932 195584526 594205674 764299301 129000474 321658699 424445610 60578616 490124961 421361090 431202352 917273925 146852408 499212871 731738379 774228060 427064951 972152392 52970241 933396836 104485998 1012445251 148256136 137269396 956050206 246680650 684384845 92785147 568806398 588350598 705352112 391972345 313083768 689129906 230539077 9537988 565354857 187317148 913124949 7913444 360041892 870140327 390319708 1008189622 396819568 453059403 726642569 795257581 813446917 453032083 884983616 646925324 166611987 236259998 69551259 1059985646 989236284 864832543 129217765 831551038 450057877 486822366 578811934 569725183 474019113 598627125 197231994 969901830 817908085 629996179 907214817 151166843 869517549 179652092 1051531888 790942555 507529589 311277446 615468279 213771769 21700073 688903646 140007546 1015434616 167576214 67468481 843652016 346762066 207673791 139230596 583350150 805967061 381794329 923930509 686949277 1064512417 217006415 588845271 35082952 585598507 192468095 770905713 14485391 182151229 317786298 222645504 1016068270 561269619 992770440 403056953 140256663 1003141056 780231522 465496168 848444140 321350631 755437622 969531628 199386886 105305602 400102375 211034807 916520561 580312062 72603850 350021587 1040314477 897020957 391445546 787764440 895290222 628723059 679279301 268274039 527208861 329402474 762162509 187531507 495656278 78020415 755733736 520798882 653677992 304979586 985561008 179200625 135099095 605212057 967626035 721572189 697340637 832628541 671185652 537198074 535092709 181780987 841539817 973325552 38697679 698435765 236008955 786411897 171234223 187032351 510342281 390860260 979479117 284601923 501815013 873317398 239107238 710509821 310305749 993725955 824031594 92723327 144837395 763229753 1030308988 149412046 378327502 860825686 66341750 341339459 662179623 37556620 456256034 174488844 249641141 170283301 913841921 563185576 600129281 712734969 87920584 1032588654 602225162 796859897 442211806 276416519 520349122 394672295 458115808 70234863 707030672 540562843 930213149 729179128 449678796 466425345 658912282 994522055 172553798 240123926 866974991 202258005 551456959 316514222 86538088 585696111 689703022 149255856 991861061 48779063 722478972 157728152 186082299 105697952 260703113 607548404 670759057 1070236662 190675493 624378088 827685955 600285012 312311127 564208555 714296578 966524716 333459482 222098439 977536498 349226179 998200027 396702429 828003306 375541938 1054081020 294038174 442997240 905841510 796571732 434134995 283305435 323288480 378683309 323146135 543306887 252131574 402311492 554764823 736036516 747212880 496399437 750780185 485836047 985768044 176756844 857096818 455210328 93792347 913990205 426541709 184794690 254030338 818986957 183393003 362626118 284461722 200809759 500659358 932226577 88443696 815558824 12023502 409190657 944222501 954963923 799983412 700327340 559646383 332792701 833624737 245912665 72801110 810431610 499176824 181279109 448646264 814221326 674708527 968704607 84483526 624612469 939324371 237248844 65167812 282973533 63656577 420831844 962916941 854321254 930119661 423768051 845068557 455154089 554362335 306325241 932202501 79396910 642445489 734731178 652919307 968682099 28516307 418819567 349311815 1042635500 131720775 125873635 895252919 54187134 883219237 386289751 227630507 583202563 9222679 407253839 749369930 575007689 1037874142 341979779 760436236 1045340691 1039208140 471665630 1055525693 1034476439 1048155976 522015746 918511744 212011262 515301453 187251394 693350730 542013031 482005995 862625703 194750051 565954532 447419333 1068267115 473742953 557860347 738077073 597425025 349120076 296876582 716998555 503888011 589062611 195631955 348281154 2382051 710919189 415255141 821732217 1019301395 210221057 114532018 1017460040 1066779740 997480663 54624899 546531401 209250099 305584813 1042997143 778449195 648246719 911426283 363895712 634650674 1072736093 16740558 154723525 31715765 807362588 811824617 883412510 237850270 873248065 551042719 329727035 68934894 888914372 237636266 216080797 808190006 399428305 483898776 88181563 523020831 340472904 726650697 993524990 327097059 341394749 724829298 703766085 39219666 457260153 43603741 883242595 418745807 888059127 893658919 432306460 167067088 758078056 367856320 776282923 578666849 250736048 1065252590 551610047 663296288 730306918 374552587 89204730 992323394 702846552 293157442 663947632 162570254 501096453 200319510 656689326 1058785885 661305633 501953755 440789680 69832737 434389012 1041011003 960051306 61824730 725996411 715863987 293768000 936597538 728499878 453894931 19523982 1062097442 56092184 950972673 972387105 984295450 1013566474 544873078 212901307 830954206 262407400 739064896 1013399955 1070629204 1022215123 49835902 430470611 185108727 709715741 872198696 633584921 1065469526 187436240 374267780 1040941558 362861973 261486376 852768946 253027186 522013419 460767508 895761697 267735430 473871139 98525881 638145303 92600736 421618716 541066735 708788269 228492067 317758792 95201986 238252496 845061092 623704113 840604658 369464770 90428590 1055205615 564212595 386400919 51170750 536710835 934899438 419360825 1035842376 510301248 780063806 1063190628 286886385 863199340 233711092 982554410 491244371 284153507 724035540 19792752 170906236 1049323364 799781717 289568623 314316911 1057140930 681499685 965464372 404308129 1030024933 503637155 716813089 1022752125 38943879 839271011 279866474 146871521 826123127 137097901 868037016 317631647 229440793 882958078 569124106 909231869 141894372 863146373 540258159 197232437 352382690 668023208 599566412 781555190 109677620 592216189 321113724 111730145 895260556 890842449 263557292 473372684 739807152 21764644 112403931 855582850 485430782 538736683 177075680 763415234 518160098 86205517 875123171 943623740 856076898 781994919 203160802 1023222487 298048659 480550920 1005356078 503477613 1175073 276552821 123070444 961977421 750513355 331536806 226661269 872682424 362714084 129856134 307373686 223857252 887702739 1016133815 261295152 975175165 912017300 277084429 239592761 132867999 881515317 390057998 132366169 139311197 1041798746 152079993 260906542 68937149 587077561 975416763 56349609 917128762 163743391 432510075 93890703 286457281 214066025 967731983 1040241913 91175476 526985228 489308165 587253972 438026218 997570701 275905692 184108129 83314220 372876169 131836232 92029110 245441466 500642479 119636529 1015851067 1035750212 1048791873 278813620 501276462 170727409 801414807 479188704 203463712 408545756 162802332 408217083 405114997 1013584530 574392910 766386427 37511400 92869013 844830274 302049805 56716805 287482076 56513822 496034321 512093357 639996241 606518302 717565212 969559701 406976337 644333456 1030227701 1069775560 858367792 602256216 837101464 146200096 768704947 196574060 881391542 198941649 632262803 931499096 12752179 412943839 570225408 147569595 677619623 399885730 519182876 236314825 585073886 353651785 554521980 809714887 613164376 265806676 273395627 667181970 1038084297 349345048 460167847 970783768 45361818 522741055 590769249 1038119133 965027430 28203334 766061377 712407160 313470078 405623038 558705312 718741012 665953893 10366731 141195084 1007555055 40790869 476959080 474616840 305678814 745039032 431577568 410682889 96760263 100991664 76564118 369668474 145894437 634093712 540334719 784664057 601170568 1067841888 140203491 679639832 1007871506 337529949 443055839 676617437 530653179 664949111 649394662 768731202 457740814 29482449 701133371 374519733 396715818 879630404 228823672 674365337 1046696899 725196252 854609163 638229188 662767198 43742809 38728884 704440063 244312088 656988336 93431048 149385609 267529503 1021034376 150764273 1034777492 773698871 240143805 75799852 477241030 517487670 67273440 219288777 232602041 544922248 596852661 230684078 307661947 389076397 386046644 152590101 222829839 842416310 1005880457 576265225 408861675 421162188 988691604 783518701 516415608 553494953 647402857 243809013 7656854 164877853 586615121 246104747 1029125653 60866698 347807431 295881323 681785660 1002133352 410033404 15097831 605048645 839690690 29724755 102703013 588582367 374323127 583835366 208285052 908979371 760287994 456666367 160759066 504713664 1043287890 798904736 257845889 654994983 127648538 682990332 616112773 202205792 1025021890 983016187 654891856 572547803 205236813 872412090 862149854 193442943 703249361 898317320 399530369 856299815 664728058 821679082 210310750 254776352 279127944 812355864 893051886 763506348 257166540 631597950 708994687 97453186 442538030 21754301 166670000 358850636 705283754 304450983 298066424 38840359 895626319 744298694 1068774176 111696423 932107455 415056086 996534980 599742672 1023833010 200490054 124796886 493569950 953247090 634277563 983384091 1027913598 566951776 947887500 19466412 501637970 400502894 400249927 637636214 1043053681 290353570 815143211 604387003 477382437 266864282 663179692 1061765007 434063148 508530179 15185651 642644059 630176823 356147744 261339739 457853533 803843694 682477897 742930933 627446054 634604266 1027831401 887358724 167461659 871682105 90593663 329855106 232122869 301550302 647151646 242924441 1047751489 365699534 647480814 505250859 54763745 249295604 550933800 226069322 921190793 693714862 58816286 550996417 141924674 427190605 350041265 86234249 615551466 245857689 8472280 120197461 659688370 786617163 748017440 316357383 339969439 434140818 387289126 981988920 417371658 878405006 990789151 102938036 355939104 995040472 1037942608 176303867 759614306 523957240 611665046 144514754 574729766 660490733 278356448 348970352 868959252 486244777 102297264 101499809 154769322 1050168978 941700766 758767270 584363449 993579266 510163413 341013763 320220645 900104903 309968276 96164592 1072290601 262960036 888269998 460592856 736975953 1029035471 448776202 375674333 128996478 540072561 40085284 1032958035 183847846 713973289 288426122 90619456 368011025 180413833 411890271 1055849442 444920285 509340055 590160604 253132329 227358075 762737742 173740234 770504504 538092079 770215194 322026505 769886953 9488276 244118880 333303309 185529158 607460630 176076019 551389787 40072465 404724342 73266848 37883664 821535804 446865481 696890531 820995418 994474098 1015099513 493139247 467165694 1013559692 171046595 747820778 893736400 1029671965 1025220920 138095983 135106110 877086183 886638780 155545035 350070214 195162723 947235210 1000090368 930161786 831692605 1068460974 829153925 332918915 790579413 70630281 509761731 196152988 124690112 451572304 988792218 997274259 520788037 354520717 797397210 1067196363 723376352 702626973 131948235 34167228 683041986 656453424 774286501 253797489 469935439 722094029 777862424 857593097 395623838 624496459 24810694 525169208 194981629 536608345 549144260 390964419 490229099 294721015 551375132 642807815 93750300 896288762 358697294 475523698 961833465 762326924 1003083978 326651400 397092381 724736426 786041208 1025112287 565814360 557571492 567927345 926139812 968825264 1011123616 600855363 697459732 710727899 612026136 717779697 722565508 903182023 112872279 655231472 786436442 760135442 634603520 510652395 968842641 269514898 868771719 259930111 524404537 851638734 856457654 483044672 118279924 783388035 533079082 2793267 974503290 420128544 554494675 99876434 937894934 35481418 36284535 272517259 333098279 1016721497 869949232 572868033 442350752 752093913 361400553 855905353 1043259528 537008650 110833637 163120494 228495738 729440353 1067341624 535153134 802210598 334894085 865547084 220950139 704169167 1020347218 960213597 980297787 748614091 524847449 1010029821 487911752 685388295 163287646 911824529 977794352 764889728 653029464 821536211 842091894 215121354 222084981 235744590 322768400 148470925 368220820 428469221 895099367 160310787 1014357961 579755340 490272602 430119035 93275356 481276556 663420091 735908314 782908362 154360452 1011150032 676536340 622044995 676387427 165505875 28156343 87842603 846362159 143421811 308811361 569607449 426977601 93063761 34520901 330148058 300052166 911826819 847253418 264256751 608033344 334599573 892202347 128080650 104366083 1041692803 140099960 271407254 1006022072 646543424 475650131 282864428 21852893 72283442 550769301 990649631 990148931 250404020 436299111 155013617 806727055 28022163 1038920457 105913051 183318458 651574417 431178574 482876233 581485458 720941285 1052935197 772488539 207100214 941682872 941455858 832599653 876414365 421512617 127203419 477125488 1057723151 617038155 722369148 268895671 858329515 824904098 700502924 298960683 703459295 249787818 695545685 174010096 149119731 205945296 197518008 211934686 50683775 11527286 325028903 623618816 570581488 532376179 289506344 829626392 393774856 344392593 436018649 1057953305 373027930 619943693 49526630 855153068 864981202 484702235 664476309 952860587 275189035 24851039 918170939 973357481 179125367 207660661 128512451 490928744 914013338 788297322 932370350 227064418 526118607 498614848 246733838 158903361 294469666 591443054 765295115 983042407 725598709 1002724958 40692574 344907366 903123579 942892270 102185176 1013292936 119510336 696253680 27269852 935857481 715651998 333363113 459221473 608430296 316874057 705011541 742186737 914847898 310157509 275588001 485778476 27581607 495973355 680515120 189904198 105788235 317330535 606697239 930353156 169512326 223094845 544788833 957134019 918565773 1017603647 159246220 1017018098 22559046 123686552 87781386 146611603 429843152 864662341 653566401 189830078 556849401 405737623 712069259 785443101 718089669 378058163 926505398 931734129 26587374 457325841 735469701 685169164 944575583 666490112 823483053 845656149 10084535 591353888 356805850 628952135 172112332 877934055 796071720 841591794 711979814 569158429 179646889 747767033 183399552 1018055263 425605349 439219474 560623178 271668384 809790038 117785225 783539754 473883043 167784680 586345661 100393846 370333827 304898431 652496034 471163835 832256044 950290289 35063101 515276602 850931679 214335751 257770539 330683749 108726193 548678656 307843610 5020006 610818316 881779214 1019212622 408352409 934614829 700089687 999790622 898712845 277440420 1042210038 209313140 383487495 490654424 258113911 449895761 662134911 731976832 640719199 622415686 239531425 841954347 158754209 706935036 84911437 559402424 429923882 508423854 934947480 1018995167 870293078 684499881 730773576 1014122151 493314424 686115539 779672924 910012397 917131095 53282593 239450497 248973284 916445355 919464991 400851358 858347407 771744676 985812587 514282570 428769096 310708323 588702779 192994896 185925437 304815487 237680083 877055794 884772846 779162754 435052047 988781987 12028592 529966697 556047072 886414347 933863981 1071566888 10661318 435412231 703130337 1053630243 613321819 1009182695 549172126 476597686 497213640 107920686 396176906 746106798 1047026253 70036245 1031366428 566783693 8146366 811889161 1038913442 560174922 835593729 217725224 310908094 500790351 702456977 32920264 470616164 980991098 117502461 79810800 61856222 915738204 865631849 124250588 609607240 549633277 861712908 802499710 1003890964 303557718 949448113 387581175 607892615 829193685 23223095 279417122 352475707 1050332380 1021971985 965788938 743873435 633289539 950956998 264986479 5880426 444075474 364876913 292433478 945627452 992352455 100705090 603104053 774118394 1009466454 291921660 57980955 388292707 455848228 590791285 972071813 902227590 441328843 525075737 512154938 312774985 58369625 1062234983 481784497 1036592869 865854161 939550578 61254549 401807719 769503656 644516194 492404296 600940336 921596233 87080945 234312797 524721014 943633298 700770542 990453532 614880962 725629525 162279869 985316354 334858096 212354008 129845205 186198335 70101554 397158229 157374784 290720310 1014442637 155500923 332555551 553417728 896457562 728543467 828267556 189086185 576798534 677339835 513970453 910463474 42934611 635170550 1070725456 1009854797 980090196 677528858 502086977 312774884 886487157 1047799961 738859246 970598867 208218545 869760345 344919148 871324137 1017836122 215049269 242637927 69373995 458499733 157919097 982049438 907417937 429016539 816609129 144977508 755844167 222397305 602175163 620197152 992794285 36921104 970987288 759354062 12374359 325586198 573621664 773413500 325387470 206909267 275244899 673216206 762508749 304012645 794404328 491625082 621941189 350092605 475859882 640368845 731034457 148597664 713715861 252919332 346420963 668202150 771405454 1030905972 631135981 976493630 252466664 487055298 749881529 677197481 630962672 354655915 540586170 333500666 474639714 99203806 99305240 952232348 465180402 227470749 572806192 381057228 1036993988 362298432 790785298 577161499 149949940 673249458 474183681 1051467758 860189967 219255282 357138678 1037252093 771272343 795391122 295231005 718897111 947333251 175389500 729097303 447596124 1001318333 521498408 1061579702 91393858 760165538 821991591 316007428 666654097 990615430 200597404 76495165 735056423 1037542701 286227453 46090256 451286069 891984723 200685142 181740130 375892415 171691301 270809158 816014282 422647840 457564102 505883905 765187606 13624451 247813835 282931660 940893637 516156523 783839423 313955972 579135116 297750061 199185311 452423191 46507985 652550513 687606111 854814473 559110450 51150773 773049444 55682033 814300927 335240393 598451208 692841466 199800508 162344788 906842393 334187362 1062308768 395110733 8522330 692947966 373824281 1035518083 546736384 870428084 858900805 440420118 291071286 396895999 781501818 40227835 244990618 259290479 1046159040 601635708 2870462 841645606 621815889 772429750 757236647 48732 690007584 54976793 924080210 935414748 337443151 840734444 492411178 872818053 972399799 914798534 139275923 276616139 138264932 53725718 478881634 388159795 493570839 314750107 372315490 898265818 672492738 17180397 740309457 974465262 238359823 742478323 993690081 423145267 476469978 510292074 967103288 985372031 1025847730 1047043940 839133297 251086911 940731996 156632775 113376664 739598576 959322959 331305418 1028099249 861095590 538746169 316733308 289593906 1044389513 392341369 770429756 266375556 335285331 866582691 390106434 991015302 645546708 452237056 766825236 885557514 398451822 871720203 634150930 842629975 119747481 490153461 989877739 924501157 646779744 745069089 687498533 417633956 397989858 899423145 752174489 168895733 292710098 444875479 241204981 761072047 215558135 565631661 827982136 822520283 983451052 367715678 783650106 839803385 4439393 758739154 903212321 662012537 1029619737 945683238 902888685 360815682 416703210 435529513 246285037 150510895 371400576 96518369 178772039 442678413 848274587 132059652 527032692 961165214 175732364 336922239 928110273 1065049625 110026683 487071986 45046992 205811367 286273828 863944498 285535509 666223464 319902422 765636293 843386457 769805932 968238195 373231978 538402107 35481147 58043827 604082575 789734570 171827790 358162144 951674585 134202988 836470675 406528347 680995488 689714074 898745580 503904278 158301295 794113313 909918128 251686936 167179912 663372866 339259433 519217404 285504094 667792147 313036309 176356722 617684250 815981821 44895525 476394428 439999511 373282620 917236097 983653938 200966502 835484002 1032422466 1003455423 435376202 446846420 636506102 73066594 811913661 663554635 159943967 734014894 389216489 940216404 541087413 701350731 153229232 93050320 461700768 199534451 320512805 1018209653 159791678 842561397 996493328 512679755 7839459 353161269 820891502 703234353 298675796 301563561 41997038 209518421 92091211 19267678 504250741 472804543 490712566 311350257 401027995 408679367 533631096 859806103 972984364 856858266 740756327 982975381 455770281 575860665 348629580 528946888 1046623684 961432186 49217574 902970143 972979175 162016133 568435686 860625948 653926317 213332312 304250100 1025300823 406069863 348320964 616030122 1023182587 430587545 105165166 510294484 1047985735 935246971 422100559 50597686 338132494 242488953 571266612 680625670 83696439 548466099 595603518 312558445 24772926 930795133 658892898 360962058 552567473 154944735 529545195 25853039 650377651 687882518 273055219 373972386 262994045 1035226130 4134894 1037646238 653478360 23563255 847579680 269470671 598884772 143333532 664008737 499648921 236379477 288530446 647556448 69152466 748631152 441703182 246674845 129145411 962378002 50647439 808912238 937622060 523356266 834662201 770093755 437405885 1058245434 60811241 641187138 484776093 1028171353 60943406 613574419 327266663 380255028 702950861 445619477 953220135 1038268489 585970750 557641599 985382882 11467178 517636397 39246432 225422860 891107712 682853626 160292376 110804751 785371270 94364474 499345373 11361995 1010321034 472352564 575310391 102328592 735818479 595036260 539657603 76772901 428961069 446488315 928686196 139589445 62983503 130410589 402968717 1061954333 682015860 1065630626 63189673 75379279 730781008 873156117 384258931 857959410 35116200 208725944 430786542 33161744 695376345 65791934 428381679 646102567 597849937 286611728 173894814 4160936 1018925844 355030729 801123576 200572539 405083960 323240122 238666320 518552441 98054762 799424486 612616905 706975984 530540647 921705222 751407069 95428898 777433732 761617159 636079834 64622791 388919335 640368519 615731552 208728966 283486027 579404636 757650916 200832 554734848 958951693 331204656 589620934 559123944 89376599 647481824 296286686 212184763 507080105 516852455 971402817 344939716 371751080 430764552 536212960 1047238242 30506668 434967901 686853275 145167240 126368833 285082324 775161032 402699837 914524328 809457836 413033394 751389468 639048275 37924348 63868439 539171285 486513516 202132269 694731945 692340139 9899598 911291004 340816013 716340724 203096586 1052375161 468434912 126287517 267032292 824175754 660771373 11296931 952619732 684626280 954250488 438254234 521455109 432334240 13725750 137302314 504856409 569506836 958587603 616306573 859230435 578249848 142978859 746176530 624747628 552133590 766277521 70032542 865345519 814546186 847981259 99290917 227170844 597379398 664248467 375278133 294575833 75276431 655033880 33595756 343098300 386830910 538942075 576694781 816417938 568176001 709966674 190425903 495493084 1063885271 547275049 6282973 243731277 929398679 80194556 833913335 444504141 536068202 714022846 28128511 719958136 116064204 720941269 300919950 858165792 588413839 529203356 414560717 800347335 224670808 630106591 1040839420 762559910 38561312 693009763 17310702 417883177 719900852 961842779 622915210 360162928 776491062 565284596 659796812 480865743 179160474 255130826 997431746 627426127 919392041 984653168 291893520 322483244 185258241 473549549 576774253 764413524 851430803 644190265 103638947 519716078 628461092 160273860 275165075 1013542097 673749837 1057709552 901327535 342876424 377849211 477843858 958629245 109285205 875363695 788241524 557279003 574348459 99630271 510482902 894861749 244429235 856931923 414290152 49738513 958488392 780977897 82674002 719189252 224842490 675528082 1053245357 912612858 872520591 106026035 430383623 884470129 435436925 641892357 737672290 538050686 1071699825 643088917 577023285 184736328 290232012 918011844 454883818 363531400 65010721 852306760 152058719 721286159 1050898360 40467497 523360869 100638016 155330061 51476421 62168132 1057453202 55202898 960301517 189808437 553469711 594162921 160918725 1014785766 110924503 1051974635 976921224 447961338 1068705694 400186275 1005993154 967936390 1046353705 913488148 998798708 414545813 206534101 104149103 987993972 96393637 134834961 1043974558 845952746 147888680 706777567 272415932 976730580 388965380 310126935 534455962 994914434 245399315 496309539 30641468 686259739 950811811 28716548 55096409 28397847 366851063 876372556 956121567 420047810 822152900 383100514 378942061 675232960 979674549 750990657 232463831 668256131 723037416 404267257 905268133 817749206 808366191 519680813 984618900 631251798 503079120 954047891 330868244 605253619 727134085 600701559 64940232 1038184052 886520701 27499832 542339849 977639920 135761305 1028469450 535371364 523175254 921969968 940126770 844562199 41710566 852186251 1051172109 527607960 591413686 800943465 114036745 779502094 184359982 267140476 875242346 356313813 921340555 381475562 634067847 797175551 154093152 605372622 189131082 1042992078 36004880 933084084 33913524 779224122 26790742 1006675488 981916502 691979633 268894141 438990088 630760665 710171474 803191080 344527958 698105720 530281714 918899787 709694311 532935296 274479384 785081136 44605838 424953047 209889984 1068959156 537975441 753216882 601644443 541192711 461038379 194909149 626522764 257148207 664753545 511385783 642159661 357135238 473497037 730357299 295488329 221286711 155444878 52701336 1060062047 906554053 306034006 893447873 318039845 201649540 292050722 245318303 608664835 700932126 50625765 504740274 757140372 832989968 949446662 30055828 23137832 1055519018 338069214 1014426734 235272516 520894482 192667963 312781184 544214817 318267585 861918431 804388254 899941417 407646213 316645889 340535214 294056829 983049981 1049216971 154484011 505357170 748579745 1001271514 520043172 316086799 697336119 731852738 839902269 599327121 509038815 1056000904 941422125 951311591 449315336 817519653 359638335 752159798 183411448 164853514 975368018 361701718 944054600 739650454 123976665 301237331 318378597 631181217 1018186843 570157037 53333009 202152949 756677875 96144920 36818144 532633808 1015239889 615275645 1003058364 924408420 618751672 1022017783 929697121 834538839 58360190 443770391 159195873 869618499 774385807 375764896 211495969 692481846 278170730 507688716 584057690 284934707 293428002 53387269 1054518937 270653359 1072693471 288218349 896137280 224870933 143573083 778586967 375347075 339461955 852216677 40292491 235874539 1203467 640361313 626310662 243250903 798913971 931449286 390039032 10981878 1481845 1044463774 1062682564 1035057614 276062719 832264970 858520707 272209207 212867316 232742332 99707778 1032633057 17293930 28110714 532500159 384502218 892865130 590600610 482754416 315036105 264451187 762812576 883311228 772000774 19552247 93142138 697838847 355902335 925994204 131799365 1069144266 367578501 404727804 492455853 1011460321 399700541 100476838 416675185 753524220 505488672 701755419 472450532 920468231 280046971 116414482 92570221 776567202 223551215 371230004 615045896 896863905 17383922 687184032 942175939 604683917 155601997 352398185 849843266 911508001 489712028 655858451 136182331 75545294 1054839760 512730649 51640315 31307576 882752432 813783146 568571359 69011382 170312020 319211495 1006360028 311567062 434617513 276570343 790193143 1030937046 507581936 583041716 344856269 1024826668 180710975 376679435 1048371213 422875392 762763262 909637535 1025101049 405434796 403464043 1039214743 736900841 909428803 288154391 369526539 118277064 615673607 229817446 379636875 140949141 291857905 837433363 317251737 217452514 900790061 449896106 743138602 34242137 769207196 794135820 766972713 444833586 407310160 966483182 786196211 202706622 1019430419 137715035 1064115420 344213728 1002008545 392796973 442400168 115792270 91610473 40925592 556104467 551968084 426251408 1018321568 519740490 670912977 224568558 319559581 337230448 246986297 483904591 889932222 150834458 569834449 1927987 103834243 698681043 1042892406 195676494 925602882 684720536 210926870 391588360 656542371 725728093 143043125 765505791 216658723 989700743 212708458 48469632 675894677 42660463 675264224 882879506 993770652 271622118 1011360213 280309995 187444787 557421995 551750430 615020153 708342821 892518647 310363809 350082267 141571221 690646514 656318169 1004400485 219568760 451900475 194209110 294668575 937250326 341160803 146887482 444705094 170655116 1047584626 283163069 522145737 945337677 483859809 347701930 720894413 586107036 283209631 552009952 335328810 401213972 619278989 51744979 163678701 469177376 529230081 927238408 750511316 1001873795 518396102 486865564 763520468 620410321 1004140314 884490685 873394070 134632948 893920559 617899567 251399414 13602985 592886955 119524296 717727107 138319616 850062376 1039348469 286327298 762094815 665641909 293210419 802791659 384203136 700944723 351308182 683989738 199794670 380022137 333819206 676812638 94603148 494475152 125463549 87576798 142175374 573506167 329337995 661793199 87920766 683307264 207570258 934236239 41271992 139428465 51047626 377320430 228210926 648384261 462256638 462129392 877967270 993236073 698422541 485203308 96471735 443904575 370407338 1045462448 464244175 153482910 201547164 139405498 735479024 394508943 773866814 127898816 556926190 76533393 334397440 878363561 1025682419 692827927 251794149 557557650 12478971 737949957 943875843 853563211 504109400 996636214 86460934 520557271 826681135 303421945 620543662 869439471 35163129 26334608 639540556 654657151 216077316 94858416 591135817 759469351 334460911 530911747 949393566 425186748 952452401 966480809 20944477 57166277 492181139 295425970 475869479 943785726 222862513 754690214 979748020 814754776 791967357 328258045 845272398 270820343 1038244284 317934759 523001942 758037683 160369543 163429254 78806206 528697752 19441867 986478575 1026673549 399939814 59686602 679341613 779925598 1057060881 953299864 938592765 120916449 490375233 863501982 474706707 68207192 157262547 431304986 166615444 1024806939 539823575 380784285 834704025 987500053 58851473 331937164 74138803 332371013 564164600 969168800 1033430113 292378686 74111802 975340134 926171292 495164840 682029109 542373824 78470987 930297533 490446847 721000034 372484559 829363404 712149855 757584469 603580793 901523641 20442962 933510519 561222671 334533498 844585351 170319865 949479499 372647580 767634660 211345632 220125787 512177340 164034047 274136709 130207842 200323599 307924901 426661653 696233717 668017882 542316374 803143953 651441567 454682106 950481350 953873359 184593246 730640734 867147614 403030007 591878948 16746120 745021626 414521351 841769047 848877840 934193961 523282640 716587857 470880545 595684656 569590262 867001825 989027322 1044521734 719834740 853262280 333204590 636762905 548150550 541977404 532368228 528304776 399538429 563216745 17848408 904122791 739643935 754501355 19831256 563204223 565294532 886319189 360398343 932326219 243783434 448267949 749513502 550690555 191981410 716952557 67895270 425887157 762838800 515309444 78865471 934456143 118937007 696529619 684730781 1003942359 830212779 171924913 685849477 650380811 499662277 663163623 821518356 428991457 776730514 851195060 502581369 1018784512 399237629 322957643 47149430 794149701 180179136 431427408 902616034 1046745407 612899311 994576990 633791786 604338867 684080749 349962116 929523660 247003930 42197621 911993284 711723994 815958046 226366995 905162386 115564413 382207520 660991400 190020187 309202800 139496628 152824425 854224123 226424705 767916835 670282464 422221382 949650195 5364968 519314282 231293568 563666334 16981557 538246839 1056708325 954299181 940085355 763323982 1018953250 783270111 1005829797 449774342 67265753 407926120 16192046 374535566 302761505 492953997 808011526 977921766 1066829828 756365483 113291361 639987939 606316543 997007664 1029098791 533354159 20264838 108991776 925314165 1020104007 898541694 598807185 961454619 330798075 947349952 352099376 705514268 893525233 485938077 640387514 402907698 764970403 488105044 303835268 158688327 228138844 757484701 805022708 327648509 1007896511 384912418 680291845 964817702 252268864 487087617 861929415 336457037 753843113 637416780 471534044 7710251 904477847 799476104 263585020 401078579 890279930 173617969 834114162 783478535 430917784 472684597 964435101 461935104 947943563 742189172 393226096 112988842 351390142 904145479 575826162 25377861 845409908 67278582 208863678 624179525 761729473 339232576 552996228 982067155 486608911 36089814 151978887 685604427 1004994458 984804832 424044318 762167228 431982836 927097719 649283635 446267498 342232962 16655402 608211910 522402383 421898750 1007694202 132953194 359461270 771517171 988088157 939852487 448506142 47839556 426506430 6981143 779593470 182450341 542333947 265323690 426379515 497140255 810420070 1023140962 486418707 543616145 894508485 335731510 713085430 929375530 567454419 730787763 576832391 1057478640 839552956 35244407 460457823 220833852 926138276 590434741 841323851 978925883 717868065 347317172 533809097 857097839 164315580 202526031 434905231 286362668 939054197 730849142 961568004 1014005787 722787388 125849259 695720645 352868795 505586040 864789383 532761633 597715675 212466051 401242931 447429789 322095137 905065260 245815279 689399153 841728389 675664692 148750734 965235209 1000876759 338763986 1006548471 828658821 683177013 667025968 386525606 204622394 161354390 835332331 1070782505 47919150 655210562 219811478 406660260 988448672 728522072 331858232 192989774 1036946046 336730183 443088841 593861873 940912620 713573972 861185721 629610862 11567300 97223706 971467882 949126711 674479121 327775749 633040304 293987282 269765523 694247639 636488280 686927197 166234174 505745956 73798047 943319300 1051414202 723032277 285163190 1053919373 502752228 355618216 350192965 260151757 357116236 509193134 229518820 631359280 255893941 1051228364 819118755 39626804 987710872 631881274 917982084 300900846 449357730 60559623 772365052 417896325 478243121 447720084 385215094 694790834 934346459 407228692 107841232 543476806 358663399 909250579 291720411 719248548 1060922322 603635948 701919 321821763 382764235 941056848 152744981 373140525 349001271 691127750 353083179 12967554 272850990 258375206 156692676 345265910 233187580 763474461 465162485 902298446 390801825 38055852 762442441 538031079 438932049 564188584 780157118 603192368 261840629 368659516 149313861 738444075 727366568 157617506 334060358 170400752 319109435 921386350 256803482 215596585 492491186 600167300 647992464 476272279 427572421 547361308 1013292137 539043724 506270815 316231557 1030617051 734230895 554879266 96407135 1006973841 881449787 368338657 64349728 322811817 243741440 368748836 940489616 304661557 836836961 250765224 387041612 790281659 135111444 981934813 276133959 48875957 18198373 495573094 134449220 204389138 819260083 254445469 385386590 981683891 876008946 138247692 356687745 29636590 511360039 980894708 717268206 894467343 779219695 800055498 679774394 726016978 197061368 824176565 705858639 667561450 202772614 916620306 1050692330 272590205 8354800 502685168 441782811 646740389 177369632 704245396 260803145 207153905 968504599 166571254 269463339 240142306 812917862 683063874 912136272 928954735 294530486 68736600 384274840 737271681 896142658 201073740 424510392 221937016 658169431 162086631 430189754 610989732 709098459 252484900 296790138 368483020 119320771 770885300 170641707 483738283 552515739 927651963 335429584 230571118 313757698 40261904 159651011 577505335 343512363 1010359617 399274034 215737501 681474141 1050115213 265630365 311077673 286456948 796497320 1070685529 800685275 211421022 674783994 342117136 44711587 470352542 617570080 31701054 1054991849 260475853 991689065 899161013 677745925 466318612 438082139 251318043 385779655 929142196 288618540 553060199 24629233 1072130686 526662473 992746855 282878392 659162715 177435347 992519741 1002106951 688640709 1053317404 632216541 694360635 125706315 896329774 133322129 489219624 285640465 613105221 551063669 698289938 761042766 907170384 305842171 735912181 851958221 118519924 438378089 247129406 56860781 787920521 336074070 370253648 844932769 249096347 35542576 838834432 825360880 682374506 511855289 438435609 83124853 1049121514 881198469 819498457 59122528 971348676 32406141 780569970 417114996 450948819 539985760 349183625 339647879 796257704 900942909 702273210 1032116485 314898183 789697530 999370003 844745325 877527143 5737680 719009428 192580562 657897846 776081612 1055273654 167138652 964821138 528596559 6285281 208485829 324609873 905420943 481873908 206719708 507774715 804792341 291738817 590008837 879682827 294204221 521460878 399288503 400959409 362931897 84010645 866231548 836393554 661444110 69433220 535064053 433783303 595917845 712218110 182492244 622674458 557351803 640653081 355871455 1035325580 63430466 555055838 118896372 31144594 329495357 597956812 226660608 724039955 531664024 6265941 1066441990 1037456683 646212174 118215007 732365598 269484 128357809 1072611524 750694387 955295384 1020349158 789585107 128066884 943531943 456143206 528219597 271489636 623728327 480289918 914157161 378727610 367387031 821283791 249677904 479158338 783167724 388596687 473653409 313995274 154172748 1052186182 370869358 498003638 599176053 818004690 727074110 594392828 409905367 23172964 1027773833 544975913 480780310 148904129 586724671 87345818 135536009 620346113 882011713 453314628 604375998 35367443 510435558 833307948 45297652 749068856 1013260408 343444463 510848670 707369091 1025302452 126853692 16637927 447476575 221605197 220555605 850408489 568431369 177455210 851447442 835119220 410184210 1067308323 645467102 832654093 87680479 645634312 339441720 570478573 511797032 878192539 184756274 1044952382 323488380 748672721 706715254 616429537 478003387 1010799508 376556604 902305771 373536667 485068356 934027733 993045795 556700196 5158705 1033105188 392383365 193163572 56888099 759075871 1017919426 41569276 698331091 911638866 746286014 192714880 540696687 274073692 1050831633 90653723 158149145 533331057 814999431 835124216 263583848 596681430 1017492896 102516123 17953254 706442088 961450256 85485398 843162769 246229269 6861120 534716628 705135195 1050288737 510569931 524759954 342371753 109679075 163459842 353876832 1038685655 666140358 567707240 357193445 382985139 891589960 915987255 927670296 1047639549 955795262 394819289 523760840 374287854 563985550 722085232 253792021 494586798 924128179 229047887 4648436 331651803 405926461 960886910 73272751 620703497 1071179086 880004922 785215587 473886781 306221599 161330802 99317376 521779057 842118777 106094412 1010927437 820525844 508033340 42224798 835520865 1040501638 372181723 801503093 1027255083 789307296 132552157 814498705 1026259819 68874538 83820382 930038759 829378998 940747107 1071314828 778587934 474679030 735468925 284154411 638739474 733314535 428399390 67362577 216686164 714406812 265389280 762288811 781220520 973295608 890781394 123686518 990194566 311250485 315042549 386795910 367836570 225449313 680211903 436967683 768298052 903588059 127038108 997771431 457770520 573724891 902580328 289960770 141541727 356973287 422342134 561931062 535388308 664793695 719730316 796033787 71534311 951322866 850407013 286121372 254713022 674174758 167970605 202010424 414917679 388758740 660133001 993346946 110910856 829909418 829266060 1001189441 594000840 1054012839 444604483 572703184 1037314338 1009682851 59813930 941186975 268180353 1022367684 664862900 19243697 781842686 338404362 251005640 137250844 4901996 99228868 173417534 883683724 1020152269 6619928 910781542 669644225 877011674 491250559 106530945 574882060 510995327 720412230 408137798 812254678 838913629 1034911759 260409951 547159320 61919558 151366222 939546857 1072625380 766372292 15158220 836105720 528808667 1052975506 49948968 609853456 567654581 832473890 131495249 962795181 266995900 739198485 474315277 545916604 916274257 105272262 578982005 443107104 198917734 437730240 461138294 199025966 467895298 439812163 940746321 423756080 1049054400 830366403 844546332 163281638 342373200 707033193 785204544 845737473 205229556 486903440 631953401 699432614 805904132 685760328 337121497 41383409 979899755 831591895 896475717 258387567 868539688 660316979 75190774 774394019 396017614 371384970 79315321 447274882 28923141 1017843130 328959663 173413623 595706631 735838681 29496398 257986144 19255075 771773358 876671583 66799887 921386557 906081334 232638142 1033498314 107513163 380478753 542158236 137556555 734448090 32800082 629367296 696155072 989868679 270941538 13743682 741745996 86116231 255243293 139058319 861374340 93004575 435942147 367755112 358651379 388772397 929829577 552020515 1066519447 835175581 31541206 518160744 556607330 791850484 374752966 758303669 515307706 412399049 195623146 35604955 221608953 1000675399 836239558 639754111 896583406 133191341 423988882 891718554 523437402 873584590 569640121 667660537 613025139 720984209 315223133 614510269 218272868 19311730 952941009 426166491 820882124 837668351 241656094 475193502 614328635 615694171 715405951 357170465 732325048 975977151