1808 481
613996434 696560152 585985748 440872078 526633833 925544038 436676073 436278708 933885545 997431230 537905651 765007794 368165796 394207932 860757462 292541049 152821551 213481817 560959463 111915084 14438671 565714278 918130702 859355440 60325791 825614813 670636602 347780544 882593582 742532679 264117651 640756505 474292963 356538850 713853135 89648869 580076844 526464950 234899341 63460981 499232401 987480257 616895638 84402881 419007989 222435783 650162190 858165879 611945516 408786830 58442984 732153495 783417708 890191569 178057226 125786603 635549296 276980502 171754583 614211955 710953506 105056032 309790189 53094764 215924323 564792068 268783929 156918768 449290543 178146768 372532905 835590793 711146743 502442085 654540848 926574723 639442508 195281683 202650247 306065589 893540703 254163940 747263842 97727148 302600290 984009807 284449328 93127850 11139983 418867646 860268159 101952686 639426430 815349563 44916073 58216253 806583042 653037753 615651217 313856919 10128373 557118439 242006121 719564716 57371663 638863691 872011363 957699758 899185969 243012737 117538301 980508331 697781437 204772136 994482477 84607206 471252010 568362057 724911606 454116927 102552087 366532558 907223333 143455840 709027431 855286021 513013881 683706983 539274527 387160478 708864684 621324411 445941061 503921500 703234153 789661666 530398877 475580337 917616280 210387122 660584193 53828669 525787830 122800749 418958631 955421618 438895561 335115896 711202022 604224051 347021920 433993295 621739826 306967182 882856376 516532207 372469008 530998452 124847345 886423650 307986519 408511881 401228158 72564854 512402426 907912255 146639219 142669795 51651971 876026439 621949178 883796109 348856583 264038100 266903473 997310690 966090083 217966211 469526654 426097815 795738280 844468647 869207428 608773036 123756452 939672267 899255942 106432366 371033149 143066614 310108252 380225267 118744976 837358524 192935299 299188374 10021764 577229630 947283219 260595274 317345253 52459400 334258486 818891712 380703217 253769814 395987877 339012914 9851494 503659500 257367574 163511873 22462025 614101616 478119747 138944971 98989797 879947434 28152115 379225904 811114966 925727088 112798943 153432060 310857416 150589921 199748738 496901469 882943474 921700014 915459710 996479674 50254495 179500075 925645457 536352704 817286156 282248473 39035648 626584218 84016867 540001193 857252099 844210737 538121275 188977800 258553211 971185636 631660034 108678375 611945460 201349210 440625465 820513525 485555335 621744185 670513119 229123658 664094074 851648329 229857477 343552057 509920298 90687841 642832657 290752361 954172733 116989136 607825688 315125090 366575111 352904037 95601750 148215383 214485710 976398276 333139443 971300133 699460538 891196662 152582465 941620464 388130882 703202378 915110676 283629678 221964215 589395555 893501301 582507063 867794388 368992416 216906985 358620265 921723875 779423962 29834754 680439953 914957451 389063690 834445333 799474885 469959767 918753667 195138798 254443416 827233285 347042670 123517894 276216370 852558939 472886348 865070616 545873227 525403307 585605762 21076749 613027312 199851696 341711123 78808090 933954219 465485626 735283372 379963306 517915131 589479457 727880803 38865773 506626358 614252098 511920765 108242916 625581026 730721011 730125187 50338129 704138055 886817053 555849285 227811040 115878913 368264643 384118793 748408755 529837354 885582799 644736548 417997304 651253428 912375396 818930688 659822448 605767454 215436925 513756931 217409203 563551136 997533286 741646327 406818299 542825623 894234970 595547723 429247028 206888904 550844330 208518160 923000931 217620498 469433362 657136600 464868863 100081947 474743191 242364055 543082036 337122467 668968741 816753224 797111615 999090248 962062802 842282653 597216459 9138937 572414749 238844256 215878618 811320133 96455709 304895594 671643482 705257241 245973430 312987997 411140530 469385855 349043731 349549130 185768986 285793741 395429676 989538307 789497811 171466589 892290365 799804945 43218144 40533236 313511240 720142330 216492834 737321801 647575068 146616798 253896614 776419717 964582868 24505362 233891363 39320587 755769638 147595456 722625629 541334208 965437432 272945920 994067195 389472774 457136929 334835928 139807991 500708296 440681632 310165826 337829726 882839507 129563051 339195401 507129320 305280300 151515126 248112885 657513276 44938322 491669757 881309806 238813549 544668892 490485529 966614470 42893510 21961707 363247756 609952969 911035142 258235047 324563022 509630258 183197044 104022093 910507636 476937206 218663964 992261120 58089199 651200658 968981093 893565323 689098379 873116049 38584436 832694138 123088089 356762847 22754274 44556620 915500650 284508472 786113750 671847345 32892483 120464021 581887974 832815294 155256938 42559175 950701292 931277598 398623589 612580299 282918442 491531923 348852487 693204576 262069695 702661733 613498573 822780860 195771004 186744809 723976825 335063350 208396954 969064549 297283142 911912601 633386639 898558780 942258337 961858275 648913173 709208520 459002725 756173854 964287575 112594862 331199328 526746988 176099570 596969601 213065228 515405228 592197689 762683251 854385262 753976671 884101107 169775049 948383544 272261250 41162374 878466670 595994554 941202892 434806974 364448730 962187188 985740970 250283094 902531579 41104397 497678209 666761531 164584086 465186604 25563201 242982075 222687718 601723516 451414616 57682126 578789806 467243686 930651549 494872412 44006603 568430212 593543978 729038906 588380751 752577827 792899196 699656560 948154730 530630128 383210579 243825422 739362332 845448766 675266580 603937856 272851212 258329577 364011954 149476686 684170954 537851508 193316440 243752021 481251297 94175545 333011171 633583741 864809495 867416981 664163824 648642037 132094374 318346007 866872524 562060234 312657920 297975983 108091419 568834122 15573012 850462183 21649163 610354293 898850694 198202471 684576752 981479853 885379502 782025227 538001332 916761028 517244424 769295797 235721985 792397078 759382131 464456907 76202703 780311579 526733741 575028104 249018806 283743037 460753539 369248919 949941175 819521286 747791509 462370060 500534976 422030664 984752478 632477886 892239155 901624350 724837774 957289163 300340910 302128535 301817062 47705337 585258538 623110333 983280771 125486165 370681845 521127511 260749134 164726404 737329997 199588978 860099838 43350229 786597611 657705826 82043748 95510904 897039947 626748753 716322486 665961923 667817036 315837861 90837260 211445255 608960175 670901152 931318015 669558977 434049570 408860186 242832809 495571036 43009070 599509883 659688206 87176648 19593697 897469438 934847357 699285220 540695034 953365155 550194347 689579962 716940895 449710646 83652498 959896586 539219536 755659084 882112036 974834523 813928878 842428377 475078222 432194560 562279702 652976983 990281407 804438640 206708933 796219183 147387474 385459097 501828193 445110834 640105216 223576437 406810354 311330362 666210733 36342606 305962385 550222313 981494949 858967071 808377939 889372158 810536219 956312340 147997880 627979937 650647046 441462615 191247144 662783031 243898678 902350654 982444093 892854819 703676455 99189342 374505954 737621381 295006051 75709599 588653600 544834307 589594344 75650054 2254037 788587803 17699663 242991696 410029477 865294548 572310608 9101267 3574981 284298254 222578258 648091169 727254880 64376216 958179173 974356583 776582464 420876003 600139379 383248102 108064651 122411150 529729004 513816969 573931337 590351284 584067505 270069428 980859967 246762186 188594438 65700946 840521785 967019976 793284480 353771526 87191087 490609441 126347582 245529381 288589937 545516600 552721680 559308116 59740117 390458171 212099615 33152167 557759773 372331654 663093311 253615065 601976252 646978222 597454004 249945805 464121645 437330388 87348095 294957712 704243185 939211999 551216178 705904739 222191084 48065274 472197690 335721127 730432944 308479673 877356308 562592911 395242906 179466709 621479092 763811030 184601056 457337912 245125382 460269965 901187262 894850321 546005302 811155933 84856842 813959748 293177327 775427624 432130411 262284034 599626156 121514843 182084001 747609076 526895742 962974480 516309705 944514628 502874071 586610820 395178382 867022188 152376472 538482261 860511350 806272182 917699183 773820055 966409406 159325016 632338176 638488312 417610080 942786415 831787705 928261311 262092403 268671517 924041673 101512724 434006720 373427092 409987138 659366284 888580122 833344044 183500331 413999876 516056898 204818800 483853715 461918889 930862028 115114662 635292205 218905926 508792663 565592041 11178234 886721830 302043704 730274933 664083781 89841242 848816910 157387851 104033109 572532385 968053233 415498013 337504755 91371355 387116162 651494230 819118573 797728521 258855381 572747109 596608944 966603743 949834785 924935072 101056104 915367316 625690226 391340295 994247177 633292484 635630244 523877265 279242720 611037602 795565786 779920184 901338728 650891768 912711208 905309562 620159719 677465793 133876143 58208213 182414331 306421522 656220826 388331848 785532633 233579580 918983832 552933986 462671449 434394533 193423302 288538553 188321875 665113586 595583740 314735192 102918915 102065601 696686176 748451907 827876376 333153144 832857212 307137459 518697879 315611942 578304745 679369954 118047418 114928749 977888679 73808720 272962510 104644112 884445815 927750813 632402960 416944870 832570567 349331461 952766014 484762038 973606945 704410791 455613813 970078196 402392031 418777638 456788328 253506004 942697661 764247383 571764965 876096330 996004509 581573303 798867004 888632766 240874025 63729848 27825746 423123274 272170314 572467879 799778500 562519825 474155254 431724545 197533363 999208841 268684987 978368102 551050072 106172120 853236964 318967310 596690373 748066721 822464670 100904320 759583662 51379614 304967714 305369063 23313463 396030134 734626473 979636564 520881817 918765402 523372667 609480985 979386711 718369796 192184302 237290341 408534167 313153307 168062900 4300574 65805820 80847479 523789217 813299898 324500888 825393399 665923969 290588781 818772629 78564392 360979425 357839024 984006943 782789178 387975851 903353220 799080224 92418421 154509405 346970840 902629267 56363473 468121646 426591059 248264431 424241748 730934705 420927673 892732575 273832433 111716942 956914902 496153140 527463185 299294441 26515508 498491736 772722491 303123173 64767821 781682511 237373050 681822098 785837026 339627128 22926266 817327836 515714431 399379224 901755226 729194644 134688298 651721694 82423424 848441561 157288660 993243916 200568096 759868264 218168005 779920745 178366409 968462028 641695246 412031307 419468384 515301930 44173040 30327839 300459123 698985040 384955974 905180390 914135177 356739158 822852705 497726824 4811306 973982532 231076490 205841990 828378645 975087511 635161336 974105616 33425319 946838472 830020776 933820685 103688567 880574143 114936108 735345969 535696727 3301455 760703028 237538949 9109638 994592148 200492173 911214120 347187314 995328177 16953396 792882742 454480149 743414250 732917046 734237213 34803907 994093885 767248070 644153395 461776838 539970313 96495081 298308733 964363543 649729092 124029647 48130411 578632760 297739373 347752141 886743328 267735886 627248641 964627617 444875419 282409943 785191847 432844888 19069599 841672286 80521848 643944284 589555271 634216756 988503175 333839973 491558489 251795580 143949089 936478516 82328922 580332943 130781500 510697260 158687787 379874797 65332309 551918735 133926804 834254871 490824085 481590418 667418968 64461711 399978869 868339415 984892242 420479644 460882316 950278316 764483340 565370531 639940215 125223834 202478100 318032649 32524467 938617405 409894714 439343669 417491756 885491277 727882458 674308885 290005435 414278393 757956711 788035153 907771120 848395464 768181507 52672891 400010933 282323196 758526025 684797194 779632624 962347390 702919313 612906270 709600450 444203314 910008620 409710208 203563962 532205464 630183118 766069472 807636824 952902433 169200148 170730832 159702798 287782811 789241993 387113216 218004295 260199035 796455329 221644769 693075638 313266076 806307982 598067458 374244164 713635943 492321935 27369353 136236123 336883483 86922394 590144061 885116945 580526675 13513288 403377989 824034709 511122417 4243815 732983818 737990569 158935596 195008536 689910898 904112039 80452112 874402383 170314410 957738295 603593069 8748430 612012717 959609488 687374718 282601899 437101152 950847635 51375042 631045885 528643162 182935942 245538503 499156183 986640590 762336711 14827079 718984354 459713071 742360680 123645605 374944540 939082222 432320353 565068746 940577036 874462512 497091419 813839336 237120772 275216431 549026980 423099609 20664834 872083495 163205206 22970417 391175345 162540030 185845136 16472761 561377952 218484983 295429365 498984271 564780541 76523803 217881931 840991106 649639885 415943582 264633598 296225651 690948487 879412553 150401984 744560521 823142599 80126004 413988982 843012001 554268960 324814763 435300755 705491221 147307110 923017920 503605312 21499562 867329586 440001279 952807105 753895858 816988349 929338105 364073475 827995369 673461589 285992288 670040820 351346680 486236315 701385022 268948385 645816099 910334803 183928230 332226941 947554670 906476692 196513334 29957062 949697846 827684874 665985474 973884374 941019414 234800387 227785954 893113884 947596507 204586901 16606704 448171193 956205037 373538516 271173947 204156735 894026522 177701912 231386741 808343834 885831 314166385 66739044 343942220 960615864 263079585 856036596 865217650 484188 171450868 344863974 671699205 503208440 181936795 693920408 778248122 201116213 80503933 65731951 377220609 224941262 11669091 790331199 662805675 600093200 837998200 68367278 390727379 774774048 790026513 932501730 519672539 739855631 72801184 222967149 306009845 273797653 643022352 625050589 823157457 910916472 380917263 137763564 98483635 970979505 263295658 660297763 943207251 134251476 167658833 448748929 954062427 155143246 660058731 268632953 210459111 557220690 848249634 124962475 779471149 1094575 587205984 634995924 319374557 868430262 577138260 997680278 13067777 385359432 334733904 396448893 232261567 504245264 908691518 108816359 745976344 28401532 725942781 718087920 105224354 33241126 815299765 947937789 53365133 136771558 304658163 266558514 588038158 298191974 559127109 941424997 169783889 236961889 700249767 106748686 54414695 807720853 491931529 74776172 810356119 530558697 197822882 379741659 15242114 726391383 74584528 513956406 115188022 686800293 965308305 225383393 21797426 105759283 719925873 103290981 864875043 134945813 437129470 921636251 644917281 773271202 674389828 211066477 827973064 192537880 872565348 429025512 551047909 406216598 42753580 597050722 374272360 177243206 712187923 116172965 609609702 877128794 807519269 120318840 646822034 714176203 18687673 365428524 278039783 419634765 322010940 667067806 369430734 355003680 948223783 168160103 298627400 985760472 435976774 684485627 418173671 315883282 295269315 637147044 167903535 412355667 80603978 363099617 753462998 721316405 537226580 55285532 15321062 218339951 867144409 667162353 198601656 747326323 720841321 765382702 23117672 662903678 190699099 88932586 876091721 117257211 990325561 141950517 259958732 605175909 967478834 180933591 19233011 752865294 782822837 977227668 673807997 20169874 699418023 828514191 818125814 991363443 925958078 808743914 361196767 996247024 777993468 951526793 474475120 691828682 302683223 480120773 586487311 64477797 343286861 568972215 954862776 400638781 32655548 570176183 756962939 155345633 147924676 787495741 166264793 873164855 97634891 454266412 418941543 713867736 467938040 876016281 631989411 224335512 687890881 265733458 588185508 224875795 392498579 198497559 447447602 39467644 533766795 156661651 813777158 495240817 668763399 884089170 86637829 193448973 884271553 146516678 289959286 29705605 767367300 106861757 778881528 892320642 166974383 124634328 108767943 490317497 718106827 641136410 898785569 526102634 143190343 289835085 423316906 673748078 368831793 834061692 794358096 75357678 257129150 297272739 81649674 835746111 434039784 244457949 307946683 331762551 502844433 995739296 916287707 462545782 813651271 921461501 782647260 255475426 779155381 787825212 357488103 556972518 708953402 894728475 142319533 55934113 37198714 776461019 758390335 584174920 248756 917218261 812796710 870905508 208707233 147237571 25442624 208052532 692415224 869131439 381300903 658163205 954229323 663836309 662798167 731895299 627386469 153179942 42620318 615559695 155465598 783465244 465125822 282287541 55477963 113600401 250645827 400117841 9867131 323768171 835179319 867070181 956845445 186938367 825694800 319335719 754676178 657046253 246867531 16493633 742978643 771394516 224210366 201292757 79534275 923752756 717597374 304238083 990817423 4108754 957178947 425344396 518517552 304718257 193520205 834013313 958589435 534364578 519706011 427732565 367142779 852467654 632406433 89734031 88727146 636222343 854083057 980918057 809813857 460016326 319662097 632214699 10948837 24718352 798249660 589347729 79769837 421004031 336923688 293021996 401832701 339181854 63926919 759451907 887633920 667102451 597917430 113447702 982401247 503291519 190364938 929213268 814467505 601780324 361062783 461692263 612911199 341179198 615194168 43515253 831683466 670462238 582379537 896628751 743079088 95458338 736318833 220435110 453957613 667431618 945475264 595511412 627105054 290167425 625329026 605619176 655403188 431769410 153352794 787943568 247961121 323178798 444223284 638351996 866333450 931727105 298442893 53699732 78065264 953278224 181932184 772266970 38017374 730251896 147243945
