10000 1000000000
747291266 202752632 205158654 600757126 56757287 776328601 764411148 41736280 683394944 502737464 635443706 953732649 986757530 409140667 844143452 786304435 971755012 28791618 937894522 222281695 129411363 597457875 838859020 956673812 364278743 827689451 30790664 968506096 293459854 543508333 124336641 43827754 7689822 600157437 561123254 815945628 851139812 423453088 847342288 200731591 880889535 250543454 939752226 384308285 428062958 518320070 58916830 74890867 544937637 714092231 44748768 406751098 369968068 781154536 990436964 90588211 543687957 104185189 783740186 942217048 706475165 581541502 40524008 96262981 239675237 81736065 133785565 959313567 347923114 906858950 760835019 775400855 912858931 697910573 347646575 469670792 390071367 32295681 44087768 567593649 522740685 972426459 620608516 818688160 476506792 582015084 815547181 34071048 19149890 429621660 292201891 428093889 64011561 168891161 98448806 608714535 33038771 20511290 680702671 423292097 22762557 940424378 490596457 937081496 648546492 546930170 395201884 100628853 965807239 439647483 306128787 145483805 595784370 983235422 401837264 807062383 699846686 515111036 653352373 732347624 928336440 44128939 143838028 242351378 67283825 281132939 435390580 218373318 499436648 6739672 913938068 714560748 103613958 213058965 757610650 142742466 734198281 37805676 621991336 680506585 541395315 794593351 939605166 985231825 53149494 484568846 116046111 744184798 205886277 167767794 59295598 15593933 261431347 195251864 523754466 819496957 721028801 324267827 256015455 778957276 275282091 648126865 970513306 580350547 472850954 49130155 261766630 949195534 56871963 54077602 602690442 307643325 598775017 232382312 219812419 251919340 714265350 693995443 28133381 709144245 762517074 467971908 94668692 13322336 978953545 99534286 1089884 60335284 908311656 998956044 760648084 939033276 809063449 72183759 378912759 641101412 688342214 764017476 692436452 118308100 395809624 946278288 644294298 190083852 417524787 955290837 261234609 100595791 811394181 650095337 369018486 467023948 266467408 690862172 300884737 551313298 922516024 657318909 351389602 136269069 497417919 48601974 772812893 467251845 446977276 298132391 701196230 444960965 442038279 206492328 78916857 76510441 232855831 739525481 662579803 194804510 32230787 269680699 682685842 245938178 459770887 118652762 789095218 576219189 440438083 989070337 508500823 275509597 683659085 951004719 624792694 922441059 551750037 298042338 642169483 66943105 985633847 503247164 32904699 302684233 623270762 855364628 919564707 365313192 893067997 508319127 573491844 870362093 716743178 565717367 16166893 338208615 744196786 415219036 27171058 858140953 362854713 738068141 348271861 366863617 590764248 512929671 924182980 586347271 353915620 555750110 752970548 736898027 14785656 520446701 893941020 470648404 159808582 142795708 535065831 810817986 765524957 392952675 53199944 308900061 591668191 493156370 397777726 204102397 451742942 160219846 635560917 148802673 150972205 935212267 23484117 354368504 496086416 104085930 361259396 886058195 768628745 333531489 389957424 275553519 834747422 315512079 756438941 963399444 286268296 631206876 812532989 536845813 928478885 280297375 471597593 355814969 288865534 953966466 60127935 357687171 984518838 265470615 670686299 873252948 235672851 212888378 679115096 65532439 608748402 889151321 905120998 906460369 482044677 814889603 960931746 701534871 254397696 760948921 514349850 427177025 164149060 823506628 667582288 37086810 201867468 40310925 544633322 719040094 342023859 188495244 390417765 612194458 48541158 80318280 661485637 907668884 572784944 76438817 511223234 265809469 541865093 262806401 257123856 961131122 360860454 445047187 995057792 444335296 335271741 264002074 157493251 835528786 942016136 594671369 621753323 109031244 66332890 367422908 60939282 711330809 710464842 848580269 380552435 499105548 59549991 417865083 908858958 221390730 582895052 544013453 233037557 293426644 101851506 834646145 872452860 841541933 899846600 22742984 101635515 293682776 146505114 681431556 601339412 337593993 993734221 15821455 212046366 176740243 51259424 297835914 670282121 980308436 546915911 223095530 518753821 559272373 183500439 670723263 877811500 676201721 111353966 562678419 967240685 721995253 345753216 260065455 787877134 291866980 969744362 955215629 582291114 146293099 609832558 534732252 10993975 54828944 470302421 450968558 129351014 772685909 642449349 263074524 777757306 578407024 363208668 645159699 127169662 49466711 680171390 511793674 364853670 432132375 644394037 131732338 640761484 144198855 928085533 269228337 615270684 617800942 86671513 140872925 927558649 975555394 851516178 863167073 923335122 331305354 201614349 176170296 342827513 138896367 388683337 727608029 510299715 68178092 844779547 274601970 891126840 76117545 12648607 283907976 640702128 928121367 541882394 788150188 43995072 317065724 445775474 223476412 50499325 44788588 183863075 192609798 344912789 20377404 590660701 833500042 676170471 277943199 491063201 836026739 304670546 580863556 385461019 305196466 407521983 832497152 790685550 92669259 689629309 794774552 615103779 130874779 898663400 370126908 477565367 635615898 239698218 64024569 957950352 629831440 104347178 25645592 738295883 49750509 977087151 447118994 725440469 647130465 942760684 416471209 888869022 476602223 342942497 479485901 264981694 284755732 698285268 862387248 133835907 537545615 680592090 580408377 735978273 722953932 481196244 59963324 785011150 229609170 119559236 885195235 882046927 410607275 486127279 348865664 779815487 506371914 926401406 880793866 237312733 706523104 544336043 528244964 142089116 50506630 169706058 463805259 532498767 889106569 687933814 181064462 396679218 968530416 138269784 210010809 399257424 899044514 293915179 834095022 665621126 38156496 113715942 736283584 556310560 228515179 449775428 623126644 205794163 924831317 502915347 137857575 238487169 70448724 380589960 451455197 478936683 760288289 347214681 97995512 518348883 997661983 145199010 572823845 489717332 968581270 160704823 986352229 344425680 11630861 643498123 390693697 886425624 919508974 795595287 891680496 446076332 328717898 397726372 846237685 92620453 436904956 384467278 673149004 963777982 348975868 599401552 302945893 746363026 314156415 485522752 766979407 198457132 357258862 817634523 726480510 953686019 836459943 460586636 619233087 572480395 394542716 659290742 896058334 437754559 633275977 290091193 362076866 31996595 175686921 831889365 616577400 909247915 207620980 850478815 639624424 705405031 222321021 859239750 356232330 945103136 185390474 864976540 283756073 425797683 28715874 906421433 323890738 906299618 461397071 623658656 155269153 7567700 526762667 566570305 457593318 87310273 838167718 120216584 905026910 444453886 193870871 973244827 704874546 722105971 751815149 447043760 659686264 359696102 378521925 193419350 701434146 68997746 122958879 996233469 861836021 734523206 251582980 964136486 467003322 791786631 395669205 993382436 154606317 752055256 32938255 835647516 654724088 767715058 127435643 934325072 323660037 71688914 350031039 604800967 651003584 33262696 742904475 870138361 547650398 19503869 627062426 542501909 405803019 839012471 923408907 208921075 205816106 473090379 774851226 509514955 16150215 736995032 968185466 900948011 891214007 25711768 243332245 277289673 743978915 128795771 369900835 202325023 160605172 851117428 882890392 161281873 135722256 300405367 559149501 373901134 540655210 966701498 297013560 692510635 936036945 132301331 308712594 756490159 473920344 227939931 122541973 782974313 260770021 646956038 521718632 802876448 125503006 725675728 228172363 866344724 247430703 599940971 538319628 132611967 538447137 561754170 959062916 574598267 161421380 519450077 58687393 725254085 695573883 735545774 20845806 212003318 391067805 921748102 19572824 625794688 375646201 771949073 446495889 973774839 567181977 70826763 381144315 499700729 476531864 466633211 165214247 598192530 176054684 469192802 112441466 433920923 131350088 189075708 923069034 511684534 702819354 895323858 399504749 646332078 945951935 367140371 970305032 500749643 932270190 224788328 822984054 439719630 473866371 539132019 568341350 963770649 518298520 243285973 798311548 858481920 622603482 263028853 852519338 571977622 242146473 960040186 577556542 7370155 143027386 276598599 778459335 452524481 789717053 456615413 172767057 974410096 657698389 836047821 441046931 172719018 312530488 160753141 564558864 125762026 323193687 927287816 270992103 114580747 852811901 76834280 141647806 566480755 711273878 762341287 560049190 692728123 157081880 933100459 128621768 288898404 396635203 531486798 933701712 358689449 774387891 779973028 646851497 501586800 898186622 207996795 512367586 827955351 548006727 167920883 199853790 563508382 748627332 38044166 181574587 84817457 324054838 776133088 966767501 922492139 325058369 530244431 41319204 790031696 344810163 691541748 991475474 845028070 966260070 646050554 223739594 233729970 150418934 359932321 950697241 627959150 915693936 490667150 211477620 261405150 77126118 306832479 467394994 116355089 835725489 21089894 496125238 142322549 684751287 85180435 254434217 906587323 268073206 798304042 395485747 368630968 231836900 364572322 810969083 218910074 354678443 113299374 995579421 53403050 332869680 614423499 821781390 889728382 585976519 444170511 635908626 88920708 295183812 543984818 989116366 841395739 261899013 533525412 652056698 704655944 117305749 887677362 569122263 400719843 343845703 616897208 423621891 59634197 433879348 419076895 700221909 407211247 271060922 618519732 991961307 535370906 935114999 217746260 86495234 249146900 972182483 558687097 819768871 258512647 99170922 606494714 647489090 263103002 46592574 861041450 893190594 781482701 179478766 863299609 424327542 572033518 752208171 274967438 413074178 955230823 818890182 647876351 481012858 644770048 799704865 157836094 1406138 655166646 916386918 835190032 924300241 315810974 278108638 953350129 52505989 287845783 397841382 176466741 790634111 154636839 755021352 599889671 619172927 424203774 148514574 20661798 676303709 171120539 764500742 510427055 572140893 850008625 609358441 48951283 54106837 939250076 76188922 150708476 73066721 912202011 425654962 592513618 773870028 277360685 680134560 177907834 629907023 3816923 908609635 348345166 209553955 940016297 769296479 907530775 23746403 319597954 44723356 893596775 598705185 617339465 75496731 77790533 905033284 187943120 441156694 278135846 507186251 40468998 650196901 819703925 580806278 417616765 876987829 223174346 149097243 368711497 943742849 477928432 608271468 504241746 177765798 162200738 136527213 227206992 895078723 441505642 288119202 41520480 148365124 930040023 874531263 603543868 904398231 217845593 451155915 15414081 432274670 235555555 756284290 587330924 770298091 42117738 899960238 116537967 752369523 594296195 216631236 550794470 386391519 572586553 482025406 333772766 353228585 306566314 236992890 276739011 571268895 580033050 46849446 137512039 131221330 108949271 684158313 644418766 215102340 519426268 103857553 945094550 818512509 112622563 773124167 563912033 463691570 601528780 925979930 50004526 462432707 907269346 561267788 34946882 537238959 190866004 421880871 139415273 514481692 626306859 929888632 319793154 100423768 88704970 562202697 218739770 232976895 813292731 163738378 786598362 265109371 570173773 697523771 979986273 477751450 109763866 835581759 847186863 618902128 541748107 512309766 319163816 425639270 409020793 528926771 705329895 543446722 209730123 557338962 832243110 244379465 647222177 585196393 817155007 224435142 362410820 384654092 692483916 590461724 210013795 444222387 430489817 509893682 667378425 137549861 146840865 888890904 318515357 475567550 97725996 516400290 360009670 471815536 745216455 233620653 830421594 790399827 740530247 477982502 108103289 760684480 951648257 546300018 969268606 992935701 147071905 216638554 686632866 441595925 356103986 182089186 585270577 953545176 194160379 815020067 749648749 745869266 348445680 282927709 340482986 140257854 532059353 609440987 533648147 488771494 183062400 278945747 746905970 872339996 767436450 9851693 669696193 829716807 413407931 38593340 205383010 267704712 231909469 587148438 939842978 248306810 110698398 532969016 687520923 234601077 701135930 277237010 593717819 198669563 911730859 641916612 627333997 476765292 796819017 61971343 960999207 359608021 407465810 756470163 835707100 159475647 464457474 752597316 249001594 499543918 293514157 920181466 378668658 504288518 367635691 164071526 414728634 763219713 322081041 150368505 690142546 201638094 173345982 112322079 911547909 698592876 366218581 376752237 958022775 497208761 734276272 944078236 615453618 667110932 521899603 431616754 838744330 491905192 550861155 512125615 502940913 434106302 65661190 70872631 423615894 941697063 812691445 185859719 754089312 905363923 458983176 336828976 299458055 661016860 227044735 272955109 454690073 215485629 834414413 837901376 603092218 393671604 798872080 71414085 712871185 112130625 386453299 720755517 693686525 166681739 492980476 348632836 910781573 837863229 397756664 529266245 644196314 769632759 865807420 951863543 300937374 87677750 415882702 972675298 893352782 229612587 416248477 139115662 331765170 938815167 663897574 55692655 370149213 660588869 680780057 417989556 302076741 983450903 393969306 670596834 380987563 969505800 946669560 122736601 928485760 50545233 148572199 302583850 266899347 348988332 797318893 797536048 198433401 835093131 223777092 806154997 573997746 875302263 173440065 909081625 849650408 255694059 917282308 338575397 546589337 533430686 241573714 500443524 504493892 709467923 738261401 980659021 486721981 18032052 141858886 546074280 536828994 784283299 135080162 857644511 405642347 957005527 164646232 673906061 306881604 267919526 529714039 471398463 214197300 834383858 749742679 575456671 264027214 429255301 720862750 629314331 145898312 638907569 794957709 859807945 71249206 153015227 122292443 735414204 436501379 454749034 932096443 249877371 667498429 667930437 488372557 793328979 556863258 720609919 252271900 19261428 809616952 624329980 630935837 712929846 94284977 254630529 551794879 547110306 848514098 251330714 472398594 809898812 777965793 109897155 380594413 659659125 771586698 691393815 738422833 550525714 749694988 125171500 810424682 878071078 976323231 627398437 604069597 99171426 731821795 405506924 422730613 502755877 229313944 574537505 882468585 254421794 265088280 62145417 877751998 333082475 146523371 835483370 268901277 240551686 73104416 644535600 269458311 940106293 669639669 312330577 356352061 250159332 319391091 247082166 987431352 360858548 387885312 584849303 831982675 943756624 522056330 810300139 986021847 626295157 572290092 869502931 410764263 291155949 223273346 569106033 796174732 129246535 411140426 485024617 953003156 93516015 234717438 341266774 366666682 708671294 950261784 246949586 446974469 199108794 330093336 698374343 831234319 31483253 603579102 624637720 294014846 178308874 248338361 14703605 416212070 84754943 803549355 402814646 952110320 422823194 385675639 692961416 959506196 10316695 753229553 172333894 174771110 213400095 208890263 520346688 469056048 999676773 221923107 277359281 471192181 785296587 396654696 691366866 968066313 639108575 447979143 852310086 101327924 222197848 315910117 923260764 33783823 674573255 541586165 9072107 32009824 621241734 255764615 573531546 115878002 367056937 287972943 653740931 741820377 190486393 855412268 739228657 974721781 506258875 747182335 54511660 734559906 775167707 89114312 447308064 398399674 527952882 108096939 635134146 533453539 870609836 932176170 631317487 775060626 1446851 27161797 506425837 447885357 206914787 837976361 236587431 729310491 908883042 23256429 928735709 108793535 574202014 915820201 562674400 777901932 506326579 838461799 329701885 144663692 12395938 297640456 325373671 229574642 9876948 17798883 882486491 919517143 368006592 862730880 960453433 497729616 317402255 83388727 173710842 225452422 685737555 516687276 191261476 381631331 625014283 711860214 410169014 524075859 868923330 497764758 385460861 239449121 344342523 459522872 491550668 133681672 106616819 947126689 180029708 461279405 881475752 965857100 579793188 608290940 698724780 36502659 190548261 588440996 435407021 911947227 835637871 185630726 5707032 650471586 337508307 265475171 798156345 441689784 236558888 690458035 79125479 957723057 743092864 168286964 20821354 305347078 785996137 322841622 980626257 703870607 943183394 698122421 277808711 996609489 397419812 895426276 823251985 896389339 679718549 631579693 699332257 678983160 872735613 73268205 248191367 317067178 701764852 657323961 905464413 255319955 354985876 708870643 601212578 237531108 812465810 942635797 138825489 665817633 1310462 811173652 921731665 620873970 464486630 753390580 368238867 569825085 271292189 775088898 692643243 456962295 392340630 155044253 912080969 277985579 739978709 382630851 511771330 440248309 783321595 557559900 96296562 58499132 113576946 925948811 364917579 689201932 618799159 789076399 268633488 840689591 999699775 842088171 314051565 227054091 695704872 170202724 822502773 614237740 200944751 278789740 324649271 947667290 284301752 29997714 663040719 366779785 77431368 469547597 34354441 357522700 730087357 727798859 247922855 394971275 286662820 655314814 600549482 685752353 771985536 158061871 379375558 450132826 71553750 171858146 14604040 248618957 11077055 242393839 400631042 131537466 197315241 651503916 884973760 835481138 602390351 479029960 903714129 212151393 147344676 433824183 37871465 790177964 604621447 26215746 508019352 326098160 86884270 609015061 596778713 459388270 207829928 174462266 225095130 232988207 549131488 496811446 211519952 504271210 18071289 495651422 837621412 198689187 259384219 542582258 466162485 530838076 120867758 450452154 750372904 990630675 406765302 64176851 102145128 673781080 234387602 580672470 475343533 60954121 652263935 837250817 225933667 480859857 678770334 605294169 486051080 657352413 241184704 508919800 939630935 877748095 951076933 772586910 882642776 888039052 380177830 634018820 183041944 963303998 528254584 275623065 406559012 712354227 263415390 417911432 177614640 183584239 570547845 603729264 819196193 264443143 753509352 449341402 595040641 628760572 502328485 816415035 702305881 564348389 850639655 999672463 31956364 648263220 686895456 238905549 4683583 668113775 595063294 727779878 872276312 491831986 924204312 352773141 736935010 94022117 533744562 2957172 434071615 43495052 698756467 362415813 204091729 823089973 73190667 11635833 62656849 308198073 158603035 178836338 165158564 326217135 888303325 156004403 879619895 199101823 463172645 326506070 107675672 401968337 851110072 740081157 522524666 651904855 831567165 19932686 510536376 618414464 776934694 597357400 835684759 453688330 286899410 6710876 971634339 806322915 425006876 458730264 915943280 192898723 821688389 880610438 578090729 241300373 979475623 157002307 510861260 771602672 161960761 726860726 659202199 939913346 127819361 448498629 949883432 115179038 793888302 827073145 987169942 965293591 15671072 22233789 666525549 759838592 70330319 849046772 206706058 693833420 577479018 497662192 774855441 719126478 665687830 24570431 648599497 607106252 558939906 15010449 542741037 951891409 14201674 645360607 561178486 925234037 329588916 282117431 745868538 604884216 842430383 311438416 485393679 262823852 815812500 655240033 97512397 727994440 541230037 817756330 847414873 846197920 615725779 642318277 361437811 136995575 213092963 71936115 114718875 834186139 399412809 688888475 689277430 801053091 385692935 159427181 672529360 364478204 513809152 633038518 594502031 948929733 824128667 794402274 703681820 451031787 636791049 954696700 740460281 440705659 385928693 58362620 673461282 891568675 941548365 783664022 241699207 879031388 836955958 810850417 838306330 621646252 430690794 497108403 604409362 17621228 138901398 25942528 798434818 941666851 269708230 176984536 914010655 53307657 205364585 810150341 774019175 590321176 594383989 625994362 976662710 358251201 494637493 933387177 529079155 694389233 574589404 320410850 20588165 714999261 143925231 22053769 600869437 130280123 807709304 592328469 118763522 975462860 753148155 976973384 191214493 209402505 178828597 624677441 412933 718066519 540190349 345414082 517860213 251470308 676477098 181637475 568103963 756775397 775100539 912727834 283213597 259034406 852695929 896332048 354479686 201122324 925357403 614535135 910022207 150295321 567337585 219643317 571248277 507609626 513913816 725805036 99568962 382528256 131138464 124943336 89197086 536816442 118322666 224385338 90009377 790970148 331808346 655571765 794770580 432493853 900278754 116544536 568421711 555501412 385023417 842479001 944650038 251398635 257033622 533806243 221720640 744502785 333222741 618292134 297461288 216412696 799793264 607639912 239213354 767135103 143641937 571399687 312064194 129663713 708665785 107918340 444120296 912317149 491542154 760001088 541974402 142425341 464793916 639731947 133811722 841428381 916596595 515036737 205804456 710385080 881719143 416899817 309525543 891644335 837285499 122359201 907082658 868202809 973695986 954763108 782481267 260731859 569143599 99488715 276877446 232034126 515375971 533755496 888428129 940498691 952164747 63545536 462991147 259655270 864511952 378161733 977575806 999403098 439947239 400685935 622598192 788426424 145447162 319461571 865592156 582796770 61802655 357739665 39746159 143770819 994754864 210085421 596650136 867884987 877493886 368652169 842986913 607666103 20984933 802091706 790129931 472556872 62812276 272801265 994538923 875090986 921221979 952721983 475943321 310957985 459786983 869487006 98125561 754076280 469029318 139131149 943246330 358239419 924536496 898221197 361761657 251614180 905337536 876610832 759472035 264292749 252988571 17378684 42780469 270611385 673285230 858863158 654824520 134162378 386511815 158174181 711417116 513299753 355631957 404064065 412777773 715731262 341671619 543134592 922915368 656354479 716756936 6038524 512399018 888954018 192861313 140785944 156383212 616951323 942409482 373089844 627780448 964307486 335941336 240886238 987665436 330866143 323431288 489685239 669714029 601329468 617056388 70059287 325351844 640297869 258660107 509954059 240407701 629794525 263811739 108813460 812731438 652559997 846520185 999557891 368367203 962297947 705923875 711915821 752951721 474735782 44745657 678890377 374038543 213805378 969299578 826030709 43218917 827352147 513201684 184202640 1866474 912177231 739872443 20657643 257139878 725984143 289731745 826680417 478273060 905218841 158611792 847311890 37355485 733869250 581261027 877904624 908630716 975742494 940618157 932814141 992369063 835180522 268025089 382470386 954999197 198790735 633353011 591551679 244781416 876302690 969274145 75410594 257502407 850322228 373028030 267427976 199822204 81147192 48399317 531997223 375731435 68120160 1985103 985391063 586235466 404788283 660221848 82640399 966164123 519493830 688980351 820144819 773882786 144209063 620153540 938864685 545182014 671379909 684007674 136849942 964661108 910083629 822941631 53767705 846881929 894429927 433151828 441786858 215494397 471849293 289559304 627033009 309315684 256377295 913906453 581250729 364802856 821551513 995706037 113967996 796925839 203903317 847286561 51103360 655012478 992005623 477766476 805732449 253132138 338843908 714668027 573297291 681117129 164785669 947106721 687961247 983697289 452286938 933874043 661267331 811559194 692539071 184630426 296527373 978461111 842651111 104111422 950764645 367977170 662045819 747315018 834208807 115308737 877569296 468576958 755005941 8607762 432930779 7507486 823006253 383048325 370136023 716488054 464584200 244424467 973300334 942370302 399661888 763638008 297087073 29549874 10381038 881378074 533403385 446489254 419872128 935558299 559908466 74765698 995293529 256964544 83863711 517086887 805036931 768955998 136611446 913776853 576935168 425520192 326895982 895286346 243253965 775410390 183303295 4515973 380334197 601702858 993885314 166730420 876720148 177911429 723209190 897580855 820276412 883905121 846164265 358361612 253607043 993816100 430110597 634811689 954624429 179974169 74678945 60710419 692511413 432122223 182839256 48918552 388605362 807513064 360055066 122017408 812922027 476833422 850961618 838580424 678887699 905918597 880893754 927858695 459800930 804348754 109729946 747581765 478840364 40117814 370286899 253891427 940575384 643051051 22264420 741252291 568775795 911029833 273408555 985298200 86902272 96492388 90392392 723750178 58098636 632612265 510373332 51193077 188928040 547388995 133499652 637134324 359491574 472883244 790394466 218456696 775645165 880870384 134546626 432980852 126600588 963080999 212572351 324248891 73617464 759045447 265095420 360390890 220094659 363717172 364256249 989492499 447282079 893139972 704690340 992783969 410548340 919386685 513698663 63413950 384019299 703360942 323360584 911855937 662860955 244869285 337055437 305666336 327897197 701835550 554198492 864363543 758544545 171041559 593097401 999460272 524744252 437931465 718475066 785267589 390122227 305696423 504423539 481468045 23100519 334364561 310602379 637272088 291392840 844470797 416384546 737848185 966816695 937198931 652114922 681424045 587454888 51819899 973722422 613562486 959526024 971663041 221451018 587359132 693284337 614217721 458895599 914540430 307600388 94646493 78551998 687668928 877165966 830607127 609206895 64955036 223519894 690288130 344413234 798642705 592772513 291865604 910733487 621500673 585535221 687337337 761010825 414394255 54177496 682991080 130075071 956760901 595592445 830418997 77759203 193059983 399680254 809453878 18929542 138915199 619921061 509890188 785238965 150632283 675612448 166863608 708292552 1206660 772853739 5718259 779062905 741702785 614628833 508577545 459575021 915511636 43254839 62185332 363801384 976631346 832495801 413333699 165493389 34165961 645681845 822691105 80271493 851453052 328439251 71213922 646170680 631883847 248375924 711541853 821015750 939891302 379886194 25951037 822621724 215614159 123462634 547418980 624141275 514155355 343433434 423475485 312333033 193918790 492730960 99287499 985529847 861977157 378954311 170786950 955902883 47498461 159773320 505952359 92148593 807842477 457386991 710083643 275432420 493945252 273864675 471795814 590648936 678538615 875842999 686711810 455738207 238277232 623449794 946652982 121349864 215151949 835665643 716093743 32825761 241947646 515736104 438870861 544856879 800238521 536968064 581507317 432294241 990338838 677890920 520416120 374513359 652496531 377314853 966987970 635101269 954035653 130357885 930437303 853961069 104251027 642068340 180251419 469788659 131053067 77831657 622588481 779869733 865053224 955280920 484074120 585969890 867928301 162655762 931035499 794653623 615764879 904882240 25415631 948567132 213250243 578314137 246640334 970499143 403665274 134808439 597655484 230850470 379970152 415147524 622913344 998636713 818304165 57692124 974575981 226929721 763874093 274387124 730624530 296358623 767198778 688650313 746630291 197458021 896795078 383164006 316520770 384977969 863063122 959916817 523686976 915922590 221794478 145878514 391532772 458335000 626438193 262091238 245573555 88620868 960218499 549002147 708410442 236707426 927951076 842265776 732575585 308746677 378204961 257851076 531273927 546242939 39040611 570059020 106156269 236306478 882698975 527038508 868827210 48339244 732923036 800802323 919549106 56647474 633952058 688342079 858937185 723033403 294871683 756578182 989343809 436437521 828689887 33186691 327962665 345851513 566566414 382365035 346735070 383040774 744064723 367549431 78105992 399062934 604948488 869983467 188684379 896843620 940525869 463748925 793528257 281822191 592400424 237614972 727632112 928348933 960733732 134626179 350585874 316653753 918634016 453874725 808552139 529193912 950321014 918280840 43155040 763419726 31664012 575920428 660274963 544054753 766292374 265879246 942122623 808622804 15701847 367433527 1276208 962684765 593989644 748433032 645909297 421674865 688178354 448435715 293780295 529828740 825467273 253461405 669973444 198005840 788151234 517215921 292755447 587768052 576965432 799762259 762989740 197301790 371165407 699584768 116109009 778746202 332861508 511979227 144821299 896432255 477983719 115956646 944866545 156341163 516783113 750550026 822223266 704613012 775249480 751721261 92813088 415581148 712177582 324850560 71788067 54456637 298750908 931989444 169355087 451517722 403055941 238553858 302382 605202727 137677318 391414805 581455779 971938650 696873327 4791232 608965902 323223059 585461088 472339924 508185968 615957956 107693790 432889828 624342776 170019547 866173204 64796855 543209176 176223742 921904757 853849528 228001278 122481114 149067740 175765389 615778514 763878017 583037000 133606221 267810225 816149701 881277240 316221932 809107021 990296369 151809558 416229867 913728445 803073689 942561353 166971436 340979535 415896261 748037372 488218446 806592063 26370855 787076129 934870957 245418830 754101173 395566018 737422623 661169934 449273159 35903952 615783656 752198192 222732995 464729442 617983669 693756275 193168007 806622977 474122192 399133357 656310760 85865095 611301691 700965857 983040130 555472909 881058146 564290862 901585929 785323762 687772900 52236730 714095601 420413330 455775227 765865493 388918917 980045340 162218732 428829477 483065365 918623968 781691001 571007717 230439665 437137600 996479918 595630182 722990527 717556581 535458585 593710539 514389257 988085648 128033657 102520951 163074515 223783816 888623448 50925884 434805660 205788488 657583342 68487259 385638604 385154953 903241118 127713790 575692745 155604700 521257848 21571161 145910452 44954207 169959638 2374983 5034661 275067751 801211186 720953022 546095169 795652931 475405035 640865853 931713025 92612948 654239231 429983008 553183969 445002593 415881033 281657807 67273347 986469786 454047789 602558265 554122867 290990067 767538080 707325562 737783734 522950154 946556214 872523082 578787621 373754323 517039947 63395202 743458798 245476841 932488458 78319775 799751329 243666882 575608903 266031169 334236954 767542578 86594353 536448006 137495607 788606749 963703985 14988848 225958118 38879406 194084398 859740162 606897839 505692009 594111510 535023853 426105258 931865716 800296774 647257377 68260327 581311701 490934226 262152889 23373877 888866365 119703692 151239957 888982708 595734431 134860371 822177517 384807013 245364032 976922443 100156359 339557844 109862746 796949742 96248427 979885894 839372463 708258413 220251850 830495464 424597633 942386240 329161759 341017982 396925382 192061076 690731278 817412918 281995303 350770001 720700541 471139482 934626838 238695593 34526474 480647792 949349928 669216534 737869973 935826405 183143017 227982407 377853004 440309474 628161411 572932959 329675836 106778292 248225281 64218706 180806372 114119273 924345886 532165851 653152113 67148973 559469972 389295324 785350076 231274473 839184824 880680519 491094154 300094104 633247471 895185648 799644147 28283759 62668220 252331349 172268351 721323788 836388731 72408406 97400943 858958811 742340872 655892073 608210825 41248207 190107295 641846132 277622893 60014692 519406088 129923395 232204462 738952791 782079020 846570555 145135748 331407415 575658108 967279621 386125295 371173603 255029089 911042675 978761966 979759369 286454723 72238350 29003176 266841012 693869820 88835471 200813813 451638713 167704014 836276586 296332489 858455040 89584993 463718460 887332813 16166966 145678969 364716205 794773803 594744123 684633917 608481613 132277989 948023024 422425914 815849365 182007984 783444818 13200859 574677574 394679942 215932480 15691382 37639056 556725457 471071892 607313564 699695026 854894058 216557110 658702797 754976794 632999869 637827403 968575727 572159864 641995123 892060055 520303471 361562250 954287076 185559178 466112063 7174381 926130526 738057514 938404023 748485959 149122095 845631937 45606611 80035091 866680770 707504730 572982020 188442829 174315500 723764779 919599374 107842488 245123077 574960839 816875697 42805475 218698033 902230747 822215962 361054568 382614600 449834073 410087096 773879576 401031944 327131094 149766450 575494972 761457342 272602623 543042295 829071595 554064622 992088830 555589426 283928406 850199468 433864543 323561721 410646956 848707016 230675281 424112160 315911154 284317264 648410936 862856799 257096336 605212517 516622552 621657863 668244416 732698808 510021723 641932119 33394927 14604268 763784589 163071478 231937718 217816426 331689955 9113563 771058011 677824594 338518329 966196768 191910039 592670594 821044745 340256692 876226491 635836693 499898252 951032109 697221363 968296373 18802534 821588733 985806856 480627758 761084047 932086891 226869846 866959691 555627822 514668306 439175971 746887438 884761256 30383705 726347592 324735209 831330 699539256 754583142 611232528 154441434 729810465 428439787 122444909 901123195 477281782 572845135 715074160 194104463 307456493 394691910 538164281 997484967 130229464 595885399 329240122 181712153 307302108 724065717 479178930 989892364 93091511 549222119 710834869 48470179 512871615 224373082 724796800 228494443 948504922 760470434 778656947 250590751 861618278 428037657 834383861 671100370 237011448 544719060 504997312 310237013 985351116 120820163 835116919 863042003 900931196 337077662 950043084 38456862 888387538 348812914 683967271 713233862 98320429 525596354 899969831 235781903 775015088 25042872 872237858 54536561 420252942 274911759 528511252 686033486 59577062 530218587 813426112 385127587 548806662 824620372 864556743 639054748 4149060 663989379 15912949 966844492 454443752 661621774 953684158 997236137 554688775 466979646 562017384 347416054 183447013 674577392 528576389 441290939 978917886 220968098 263376580 228095837 433740108 990683676 784149352 184983843 104281909 716015180 471766821 526484681 561451162 480048580 896842070 217112276 428589818 842245179 66993065 77406030 261402701 178106512 535360592 100021942 968055403 364211475 704126887 79367314 158855630 610747099 351294910 473167764 429355147 667222574 602089065 577579443 79424465 611591345 741820653 39160066 782349507 912768772 394791120 544909056 23134059 306010708 781020402 611588010 247080655 318335241 656533210 455547161 196441858 830372390 590673035 338335913 898101331 484490386 727417136 202480059 401396323 530630366 805059401 852295358 950976270 475120701 27552470 620898762 343559760 32360505 830448618 125947850 780568385 941458100 188957779 621501001 268011107 263991999 302929478 135446649 814422792 959724078 942272386 903561344 561367937 385329611 787546250 879594148 579140304 153293219 953663159 696011693 8571731 146157836 121881325 218263330 390623994 164581505 47202593 755944122 581699095 482193003 306586534 677914953 49329048 107107216 93702722 981618839 480929745 179815033 613781424 11855642 231974916 278164032 998917874 131393262 978445960 563639157 490880381 135188480 16006406 284883664 86819980 824698541 225469132 327157412 807233061 878344563 953047338 36779765 621637947 324048321 376280644 972568067 427245068 512218727 617273365 734761611 249327336 343496009 176690294 706050924 152302736 899001412 802357723 864010560 721592852 61029744 114524428 702041316 410389622 204101568 168999196 525374148 524510454 905694151 561066181 10862136 298696260 49836134 762223026 600045000 967851220 91922525 726248577 684781227 520770861 918698147 99658480 923420960 739780192 953557397 307133311 157882046 272668042 945937970 98861694 316296941 421168844 320731728 160800830 186513905 397230338 143834588 251403227 620769508 319143803 406769237 323684539 65460578 590636983 781672905 154716374 858841718 394377693 852540247 915713844 898257313 512564180 168483810 229637668 318534539 909289989 118573969 481391141 260341268 790721765 85366433 63333714 91907935 727037324 643197163 652762628 118322901 177499302 308179640 639095365 619695701 194207909 21381514 217611603 958053081 421892274 669834654 376871245 148138476 900334305 986835229 638557022 372520932 366421824 722959813 459942252 207225029 134348729 645680534 851513884 641209407 549433507 256568250 919860051 666718039 670589758 509794683 415197634 208146694 726047737 599301142 587649532 55247879 40335938 628448997 577263516 721521338 933718423 330416499 357830775 619796014 178522417 143957211 623403383 349673907 400960616 34754746 552760863 787128804 768008788 278112737 593541670 561243891 391880957 845754155 90449732 164446133 115650549 235943908 612734108 579773782 11151209 680677249 614809953 816095412 736088609 862555693 542448597 84005879 847434855 748139316 332724486 252991345 992557598 739362213 52801473 676554702 91112385 86369270 769103238 379965145 664207234 102487954 812175660 940342153 64634716 10415410 602038753 199808845 6005624 194161103 618379742 798708520 48496656 192356189 973816849 144198826 731123675 634089961 478967131 459746886 755355934 793353637 213830165 929830002 446157330 431982975 505828903 361310610 561462292 925329072 569042900 285230777 417588407 180170709 919160199 186494029 499103609 813703196 526397786 30559568 180768608 553454997 688065 706810220 540401202 667229007 103641340 17357046 119148789 992802896 865440273 584549597 541760459 363737537 632422011 134139327 583394565 328705335 101543953 38137832 197083949 850348342 982451088 50639010 150549547 641892348 256267671 365406814 757258788 55920480 667551570 968365163 752532744 834450201 58373960 886684513 151949947 186409074 297311370 893282682 107505002 622793651 518886465 460560437 194100948 831296915 108737280 96923258 858745672 828020987 877579032 962045396 515253826 182752516 584702524 307912352 758573898 434008325 73673208 62916401 283812294 772955540 443746594 364439259 314337373 122020950 391505888 603623993 411664331 208330748 265346216 60318412 126985136 842236558 415738855 367238613 912371231 790194237 229733631 281345639 9255859 887220794 932945509 111266353 29419335 253927272 608447719 202213148 798133251 744751510 376635207 322271287 427420160 262168125 902024671 682400815 318006482 529506983 66702532 137070444 854278714 182856609 520756065 853810671 37544668 123075201 979818124 748490763 801160802 73774032 333665978 817459140 669727113 609518812 598581049 274907422 908947105 949018103 815516617 155274544 277675870 575815737 13203619 540168948 813692667 862010968 599085606 761056060 574285081 288427748 404586400 516519074 54755424 203524784 385962149 809873607 600882027 214354897 654503937 701853675 738489249 705928251 993475539 895392733 922287900 823348789 653582770 304977133 139070797 793749431 40374202 31895565 330529660 161464449 657920348 929347703 604629800 130037422 671775499 536937842 819236249 564199246 684922403 858494124 545606958 4683211 398706858 622142619 787214338 461900106 214673455 225325151 711909120 693703145 189428527 707370339 815698324 295369449 273733544 544182761 541245316 925123090 337796418 691319583 741214976 267212962 499067126 236683189 273788888 804407579 939676972 436487030 59494407 341686283 725034311 571866693 118596117 311003296 621726379 873742903 475369201 299566395 358383773 87906700 248893630 231392363 115967237 772908567 709765286 735199422 839240591 677387123 364907531 29753210 815681333 659396451 27066612 634817655 218915675 451276433 288079283 264920493 364847297 19115707 271278468 194648060 473862787 820136087 900709109 697797844 862254893 349998995 38084658 603334568 897909011 810250742 273727734 966419913 45828949 749325272 356810185 130249400 477055207 991597673 365007128 526250909 3698211 664878809 922118782 968750579 845680954 207427401 336077409 860491277 815187600 251352841 617629298 619961667 482702119 582584484 863249775 590937603 793125997 226060247 805317372 903408689 853845732 217190402 330597000 427913450 320108354 878411197 212703335 688752805 169833299 572047057 715081805 810914661 658424053 943877574 94868329 763108310 707031048 147285239 116301392 481430037 694411067 186089878 853560581 782571837 870496460 144800232 271828149 637467038 905951000 474524864 430375521 873787334 953059181 686228824 489651224 680659493 557631429 970633627 188902708 761999210 807997794 4392448 67887544 528152601 875167305 43689616 174189880 645048133 900419365 811404124 547773584 696183462 898860139 428917702 495177073 715423903 55006213 533250040 392668207 513130264 881103456 338736161 900192288 468843781 297253418 945378339 117271928 410233505 459563880 608973884 77536039 840718143 307123232 751597917 580351801 906089473 480147396 468149398 896231322 943731226 851832452 877351916 370553365 725706457 850535036 380488388 567677772 520223350 156326472 528901520 344828609 705060298 766659239 660997443 293049204 582192118 348400017 210528161 180070528 672723650 672876380 351367130 65944300 197017392 59413490 977449630 122242419 911172720 533436096 988599436 675977401 910621474 335134822 909263906 310072935 486228212 755949440 957829318 287461066 177731639 68122590 348767178 837320893 724863082 930822260 314761354 313139931 285414798 318019887 961781488 613018334 475352358 738859836 792890735 532095817 484710514 829040666 442595821 409693285 783315675 413294072 28222008 567562435 689116656 929378321 389138638 280705076 182574467 282078531 160883377 421946151 806802356 406204658 47004145 670995675 244626536 317300914 816800510 463538527 351378254 301063639 665259800 585906976 903986540 385950089 538257984 589044368 915781591 580180806 642271690 577034193 327776796 50444645 112358208 702750716 428235344 700936006 662927760 931895702 854539965 376638602 25272807 458294025 251970359 599778281 68634276 24129834 410733121 856226633 168237943 473682890 880396416 627721752 324731007 530732598 193195144 539258961 657109912 113585631 876831461 373062124 243267296 246361589 941307661 582690480 593474860 467942016 152816168 445545783 508625916 53456267 230558872 751720834 198716670 787737986 485824848 121532288 36012345 735544996 218939720 100046271 211415150 10844955 206159897 719143172 557817504 802629918 364581151 806197965 43057258 925204027 617614492 979641552 464543808 427395975 5626699 190247917 515035959 667309257 867003017 305868391 670226155 470556741 281702142 814618744 114150977 153761276 206936722 398261312 306311677 656202235 527605950 98623020 748936008 434367948 126983267 163732623 545452181 785024019 90530234 792860894 818787877 895576896 960582105 297012401 114555333 292586265 952807899 968128922 11785055 102496558 926046207 836126748 48056556 477050762 852790978 949872704 881195766 621838125 495843050 986407047 487631946 746019542 399105583 950596506 351440336 100741920 562406596 416138384 165400104 117422538 945873323 214232671 132234291 325255101 387442136 609065914 335252532 537092498 625005393 684517874 778422748 292011303 938784875 747742281 710589665 765854834 327278887 426816799 560764263 30932405 780516986 673915587 990258314 851395211 919541301 903203030 607758445 983480486 223557902 327569572 224356428 630083305 930149126 227753167 336089650 680181810 1362127 729314338 475368468 947541079 618776280 178929635 585167724 662489177 577853646 479114766 935174941 131005165 315838779 903908116 625611788 185267865 399620402 217191336 805119955 778777311 698059036 753338065 171177050 45970199 3097040 985119204 248251312 744926052 516268132 252896310 539389599 129454611 752745792 727215046 867989119 136033615 753341920 465535109 728195067 486297719 892904238 919154898 100545594 955593410 809469747 845464519 294128570 817541040 412379534 17446697 375112590 340705107 933475931 33712331 568471814 519304544 650252546 697063518 927691563 102456805 669975367 175605667 770269034 815995266 751594078 938562979 582851780 567668955 69952043 940916079 248241055 155444410 197557146 932558529 227694581 639500352 440881775 610624194 137874362 832954357 870816645 687378202 724713443 641443428 958425367 376248565 408652386 115556567 776484317 837629257 203879074 526049771 458601142 90872777 651788169 107102418 633832249 214366103 809268351 438047673 848726310 517854929 36252027 197147489 32245020 517599198 666128401 5683603 693623318 265556124 154714651 178139586 172226967 474845585 300839031 854318888 482722707 177849199 162704546 218000698 285827185 413181745 121112042 728773082 285338107 514726409 57402323 931444763 2358700 198884357 798129513 911747554 173042294 516180470 361505834 416682095 976394628 428173508 601344941 419222266 862037887 476914614 185713651 216040406 973963100 711079179 11303632 838444644 765619780 565122012 889624458 375261510 897585783 387730492 329115101 400430195 225655025 604593496 77765178 674234025 345247807 424008947 347127924 353531409 256046606 573322110 706525167 574998773 630546095 440851898 451164398 121114527 404121766 587911232 594407820 938109381 133163214 797380636 642994838 270478226 141485636 445857653 117666534 681191859 446516734 704016713 722222718 838667344 627672294 298687303 752784798 196413940 605797736 89608231 497953255 851874027 260916877 470926568 50184633 256785656 112523307 228702485 150439570 634377660 214534699 488488464 463120089 688505778 311204138 5774383 896103218 648410883 419145753 173609982 30189398 373579089 880054233 242728481 745695180 63674320 949723021 411495392 415899077 210666852 153334216 303147783 552314078 487482496 738267420 739733421 947370636 705341765 722693333 853878613 803905222 632157136 705921167 534199231 587691830 526434334 24446615 90284909 421029114 10767520 397224838 693650592 538635447 685442585 991980503 621694501 352752931 786447689 371074893 600683884 85681421 395359769 533148625 393242138 968539716 559858184 923080150 528562711 811673775 250410381 65365718 183723274 101479543 936852261 447236825 527710502 965991362 337196506 943726315 621375422 797199431 591869464 389945475 671421574 43908787 924988390 390933185 374150341 905204739 76126911 561605245 541958168 37088837 768042346 710385468 75622259 518305890 987217804 687518341 100931331 191802694 117729894 36204884 965945582 722557242 649610076 526971032 839957330 664839346 482375459 76515156 646051461 198942563 903599451 239478419 599902292 543558233 329562397 731728080 758725906 371836515 873684885 75639579 527011591 632898262 194558096 615199978 233220479 983506830 868218393 532875406 252446848 344301447 528252952 720529347 440458616 848611443 524111228 270728528 630514304 578650500 141405776 504259719 519426665 733862066 339360992 610186273 737963466 422018534 66334016 407114145 191330040 557902965 703176400 797135869 834593218 739413960 158561308 627032858 337938618 840817936 889997369 280082406 582633189 778352180 649536745 885323047 245433069 743254950 609945944 868805355 621991664 580724362 319132938 745949541 204044610 133843371 942251261 628856113 62830109 697021495 517606928 412914904 606725722 151735185 18443247 422618662 698495998 647071429 833484189 9446318 785459504 280961118 677165887 964776328 350114872 635150331 697864909 325862665 705166280 652062878 182829090 962958031 772719061 812160902 68025771 198461374 78239025 338956129 258792902 90733431 612734066 345485283 217844333 482202784 873732907 311223744 583822086 442710333 361758948 281853822 877221836 963054007 165749341 934329259 696260726 134434429 53177890 773117257 749999484 194711213 907334110 689376603 958080373 268120910 653003394 513348803 8103477 994658967 55404035 415644277 909678239 684054123 864135720 104615769 178181195 634082095 132938538 956418802 564333995 432845080 417353803 407368723 446858058 383190592 437507957 506145460 697032497 410925324 764150538 289379069 822341883 682442161 196751780 694981228 763660091 213634951 758185858 755894023 311174173 142127214 723980109 279032122 373551421 925484287 322535110 280481715 844107644 256970096 378825608 112606397 244002008 471776908 637658416 313527649 926390589 760978724 286248421 472357277 349440477 882890036 739412150 506523569 423517111 864866930 590791487 254081831 810065813 239830256 385884446 698741325 687071760 373252558 438224602 995589815 414467618 105824896 665139380 384296756 153429471 698329488 506207833 591852948 384699663 578649802 80010317 460566239 804141445 271620436 836956701 712063408 317727565 953589186 848609204 939264040 734121604 19023605 187173502 587242321 944055338 319927548 440905066 412529676 585809517 835215599 522411091 303807789 370160797 775548905 173119901 765021551 248306581 775127831 392173527 116612921 132198838 366517879 315559924 144044967 705077152 167384267 469321083 557597754 524554525 335651213 364727623 976375530 56790099 740332483 288328820 226883666 998930382 181483208 611989566 82996541 536924578 563170715 484067467 933948513 728373368 336427028 534621386 732142877 377408335 152610304 923188850 288063448 452764922 652159800 58454352 499569777 437883277 587474731 301955861 359976354 976669788 560644921 458895996 130272156 544081320 934248721 922741163 962740212 725302996 850474539 214305057 584012963 261909838 669347205 894839672 462337195 795842703 127168768 244861945 984140401 85955230 300085934 261406622 578632846 45622032 109528523 28166620 409108615 469519513 698205439 537269139 657927755 709298456 338531842 556171171 958519284 132107308 19681801 209276843 746765345 645795192 195893047 408157049 317558811 540514676 991137486 150649636 582210223 402647710 6456762 944286849 200471598 613319116 142391300 486019226 709003090 601807721 475502859 72922916 57914942 198177833 563442134 156152505 20431471 371137777 572206757 967122443 301612562 157373800 105521552 694796549 278580899 624530520 269387389 43954090 131034144 449487794 951724748 341912227 665725055 230311817 47306399 441422785 380853301 968514285 881179775 305896516 902697739 701757829 932182712 122242423 355877562 3000919 405346058 784107152 681398886 925273521 706031297 669008954 178384245 839374061 177405366 841930599 724238595 323376505 552801595 169413159 378350149 790807543 869237859 93388568 398368977 325051913 50408726 709461422 229950112 632503835 547344717 450076949 634606839 208110079 498311200 919894357 796317765 777434313 692626373 338237365 857791448 455810961 460065756 87698123 284924338 733850581 913875975 998875771 904424100 677248546 359238568 737212023 359239765 978409724 808371945 604637269 735979858 380232764 693438490 558200500 149422052 24623899 219999625 846968941 596810550 289917950 548326205 455534045 421763497 826163203 586860872 751173061 658752836 230054260 116441819 13006187 823552574 280934021 58380800 890811573 843571997 687218692 609458987 525127464 839407645 460823762 840245849 764120388 357760053 460900440 547470097 739723476 73382906 395840420 777990322 799116630 250602172 114402546 301792411 173955252 938148506 374661139 120901397 794869470 385741950 317117627 114649756 243843938 879298985 322162565 578828587 648404202 492030058 526744922 88701750 19983447 440552285 861879460 46546406 926478270 655299294 949434575 655476042 590446122 895418235 96362259 310095194 678354644 492602262 52963009 165853829 890469353 271409410 687751019 560560770 896907146 478406706 840225499 654656326 518291472 306115138 710017135 995853118 249598811 61447832 614433894 540885333 578845536 65863604 386405568 749499803 642293883 41302511 386963338 720314119 19940667 864201703 2268398 294323811 425402021 970915897 575987061 582804675 125840023 479231577 532893941 783489518 744262338 313314844 711482675 508264865 574474712 94656237 996246147 892151940 916838653 432099911 666181037 999756185 459990805 512442250 606727206 630089347 884255059 949523642 639010387 818008212 812212736 926651048 367517003 359616539 71793897 204269518 343957165 463839515 109714650 960087572 890282665 906380632 754037244 540975023 945925791 550453006 138686743 647659699 878767289 121196555 711600765 934264636 830365559 129640431 948966896 939346182 962403724 689016594 524485947 209619198 749883375 834641851 863500095 68455975 690687260 601319073 142291932 641624587 563739621 628449680 971268707 344265612 59752674 335411532 141820960 497123057 436669613 766320846 651217538 597772758 161206546 679027171 711855993 903429986 671537743 770122232 920504780 628834497 282775846 779051660 884467863 520437158 379216614 224237879 342669909 115282433 512335046 599088830 728584530 116539331 234686811 672694665 994929086 352507374 283392514 27224643 811079506 632701071 358341543 960371705 696783492 337076806 266357398 715715746 778813295 117448378 989110874 136578713 422517475 286814952 190407600 517337681 690028139 639753792 626124588 933109643 830441260 708617170 192221653 644833332 917327330 387822695 932359181 338959547 179115048 534179380 465453925 550092027 338942799 418206739 560371920 189396852 951934959 185438594 267179727 497718577 443079935 814021142 98002383 421615848 355338203 541813293 831380676 887317155 696752523 646826502 187914030 931387323 651638436 470550337 161602453 353703239 323328851 211792711 667925056 321423016 282555170 450250149 156555345 18301481 611474590 559029353 675146213 354723944 780631783 856588135 349097133 576887950 587204813 613699955 998068293 261740431 588070801 585373858 831370235 376947595 312976796 390715836 483523071 245483787 197510554 38072828 697599486 336767485 456271336 609273089 327428428 740807628 276373956 123045361 703721205 758185668 57236122 319821623 129761986 845383321 551502699 380863786 313354729 760921440 771494624 309632428 542883824 151707007 933728588 464477940 639966150 911852178 624776172 892827841 592410373 90872932 650307403 746526255 915433448 660619707 113901121 255754039 586851447 993826884 316696748 66931295 189746296 413034768 802145064 107701649 144765220 363996444 116689949 136578871 81249607 470022036 149035877 871072636 444614735 532764166 966703911 365976216 510070700 687293872 789136156 918508745 780995538 372795891 107600448 169292301 50382396 690105362 726231847 715377315 176596638 295854424 984224433 514471453 831162438 998677202 378923392 830578108 966899644 46315290 420747430 219724644 96709217 746619767 391636335 426592310 426661130 86707833 15550548 364994880 835229240 868547038 961111185 148056663 288285458 853599237 731903414 963813554 2675612 264632956 212927785 656008651 752421551 620618225 575977225 17248616 92951039 320826456 249979929 761348644 785350135 958891729 248519158 225868517 368310295 619740446 465239871 89095447 814673382 779644223 452480053 124512414 909955000 194709069 308540347 230693897 66869152 62618602 870954664 339050913 336777435 549178927 937041310 874149580 600972649 897169056 291525023 936003515 615582837 546280122 967449227 825464566 584413263 926731691 880659464 805865973 417177477 820265526 393717187 599276463 90111567 944956863 473698053 844263711 708146509 351411586 93022538 198045720 570128078 36078383 636535981 263797383 344031824 475815736 420541165 261361551 103795933 974024592 387712393 84432032 830235755 965213588 956419455 103231215 927010842 106911243 766705892 996775287 259831713 355376810 198459994 625267353 399547624 436306976 131732288 513554164 59110646 950747339 650075716 392272172 753527438 122393281 926728220 881106104 64658059 363163589 546883627 863006327 269023487 827609493 873208050 517215818 823539287 281219962 231119958 946986894 229064362 345698676 804308852 977870040 40605640 23905837 459277851 977950923 471490223 574508373 532907762 970679532 705370153 745367050 524967186 769730141 501869559 728141833 140992536 682109370 866994688 46762404 795484344 253091864 460588603 847281943 250637847 984958609 864545314 496648296 924734644 355969258 800032363 959604190 691641106 724825579 153534370 219674149 930816272 906161629 984025424 130101133 864923004 327999065 941830438 671236872 234332921 434147503 831430688 951947908 83331749 603539155 358180087 948315773 858868492 847595742 598078082 648194814 489136275 50730507 758411382 841777829 607639175 448797049 603315215 375920416 140440894 395423781 35071200 344504076 825422659 197743510 213363299 798740830 266838181 697045438 125555314 634683950 731146381 891129500 847895958 219576733 618573053 208613902 826862231 442226563 552943376 588249209 954775814 811774530 750923981 941047732 728289981 390634475 397571320 234291856 122758677 701948777 754651663 529061935 612606231 761046819 724149537 131432979 720591022 386631564 760289278 256394311 154446003 883651745 165436075 28896198 449615651 868083751 554139049 12359044 865048092 649865662 361789930 491818602 946171626 352684489 551355634 961988890 222881009 546593014 596887054 230485552 874600871 263277077 83316610 573543909 580704454 585123308 82579501 515104324 449094865 712000784 869857167 973451969 690260834 825988731 49631092 776793660 512669317 917387695 326001118 323166154 871999819 466103145 116985416 532112615 503536325 486507031 858982567 721702071 69552341 31782623 603296542 602747725 865579419 7695698 691862555 489076274 221491301 4717523 576537091 46469672 252228621 139982253 692429677 613300451 736246297 45072961 930141862 655367240 172278072 364612236 707653402 308190251 636884474 875018228 85717562 254898714 35325511 493719883 333362622 171829421 602488733 23906157 334165779 54252515 930537809 925326167 873316268 483171776 638274028 520873144 424596230 32674939 555192438 267360655 707486482 612319067 748527621 264352153 721015513 158865311 218738200 560411966 824843689 235392588 56700677 861022473 62955211 748362464 153000690 680855337 853625838 930459955 129116175 109245224 651972686 514791802 423174514 814897768 104848610 588340446 988104551 724963323 638477513 923471984 113907621 955120860 668622629 709168903 456477277 371951868 390229498 96652473 545661774 846623479 396486327 379628671 863553915 935043401 758630847 186695459 137535190 757498886 466322533 755998234 738110143 332296975 330172135 129184537 662141597 479382534 875732026 415042386 734808975 411045943 943896789 757923664 50382530 118176411 125176688 814031704 178770791 132298437 22243205 315589692 658178452 703486333 347131316 314985659 79479970 389257881 938116150 97030728 479066939 768956067 345764928 648353296 233733757 94515594 116429161 142526012 56185200 393819475 953806174 913741173 772380068 340564546 641165056 342005212 824146893 820186013 360870124 824534593 234353973 990332439 442920374 190850562 550496318 967356818 618624663 392770976 204068317 295634415 720372709 108084860 585797907 786948009 853374876 453632295 904987969 383489676 41929387 457448271 985447342 455152655 988582129 61051486 859597675 469651431 761080940 308746025 803190215 742155257 673206846 545703305 385544536 679048808 931739923 891608690 599570428 823687668 197967930 891034190 57664679 130922348 202640509 597725029 992598807 850915 445707470 410076758 231152302 666341484 530518221 598540179 443094670 501807695 305552723 57947789 338280724 882448867 607766084 409369870 385342282 588234406 818814659 210949584 846630467 550366292 533860596 470228922 176727888 206364362 248927029 883716041 132659951 318942441 77048237 501187010 904791297 390857936 362631110 40782575 83986472 572484133 290401546 503686370 96468136 714328937 676129713 991283315 587805329 28761436 554796686 51871528 331413835 180879943 640273827 270718477 858899842 802016535 437752384 980120571 949094755 989662751 938189078 210592794 537000987 854302276 824996815 268480924 372464641 876900212 539050872 386984463 697832450 592538964 453924330 603049020 470012445 157771341 133113073 736478691 313370712 473641550 792450841 819040465 471072480 379395738 118519317 499948859 781353112 532250826 222812613 901349985 69355885 589099029 732217506 640622577 581216573 81183829 16546809 688881346 360631720 634801462 39211575 211886995 416342925 91114957 536682525 249928332 510254145 665115989 160686758 591074155 750514729 750111123 520834360 348917387 657930881 410834715 232972233 82558878 55897294 460833446 433073200 985237599 984282077 44720442 765498513 575326055 220800506 501931574 237231976 184733647 444026479 886940970 182810079 201637243 65682564 5905879 184726029 23012590 824206194 988250443 498948274 326077878 103712847 893366480 31689566 262105683 387902900 731622734 459548437 51800290 401468001 1397938 83010995 697471554 537829435 216376910 808256282 284003077 161411863 156422714 827129609 294813374 601055409 56034178 912936359 996111177 209849885 129623750 820357508 747342373 147165686 961947592 925158999 328894278 256113446 2235622 335049717 269873072 757475326 774493916 343462298 499032036 792496861 306950023 331495690 206653564 554578027 134250908 264320196 542151544 422345595 709920839 552238233 896738673 279159680 16819667 392878463 971132754 395756595 120965085 428272548 145617863 435944127 152447087 358026001 794571730 830149061 572137829 639502607 112048779 5347511 949622476 377118142 613669679 828242481 641070775 721597528 363904207 486405155 547732713 47321386 397328362 459826719 283412483 30710754 796621017 230652819 675893246 34863829 136029152 909677721 105216720 473247856 156972902 12282459 748460460 448460750 996579371 702281212 242317641 556636006 262185594 214144475 56780866 186735772 351848960 345995825 932032538 61929575 737021843 303368059 454495629 664835402 927137971 473681929 510632128 679619639 57379823 310761696 725564174 951394550 952176352 87730981 173358855 660827414 293941441 460173975 122711237 108245314 590901677 34419377 94178805 39202788 951462677 555890871 500378519 659305784 200013652 148890910 755188717 689728788 860216257 167395763 771968214 982708831 298568302 471970589 447254406 855975033 518867916 329601306 393831925 936879971 996718618 815621988 368951487 458464880 441444348 877495687 442461995 333613031 314589494 726583785 921134265 825483757 272117763 326492950 4608505 830557706 957580043 106525562 43546301 999858832 228123275 461137178 832253437 428057146 490906531 615800579 140533585 697892940 938310437 762616896 732585288 303314495 480188903 94934593 945910448 85502416 125703760 723916770 729110988 221065382 907015048 267160404 219814130 836309841 252142168 155165021 646086291 49211139 675993923 648311086 777807542 327995401 135722940 440054651 706003962 216750454 36973666 555472413 777661902 485008167 328240480 490317160 758478704 788480921 559796341 395969998 376579272 231887152 312777951 679244455 533835089 912192020 506636410 748258490 338938277 549908177 502968227 28226328 53607460 864567231 330002202 689073086 386157488 681633833 490020910 635881271 444341341 681130920 20792978 91458727 287021407 440891568 176989744 592955122 915222762 844162899 432342893 489426240 964662639 390033223 707181145 680595882 589937747 904815666 457124185 666250205 770227800 881921838 931462475 773370278 498458394 342865152 926937915 308565389 547758427 352479189 707770631 494396683 219469364 76398183 840035966 102644446 9789373 907590 811046774 541773148 642639840 641657241 474555792 218409467 840643903 63966928 590136722 131662633 982167225 435309892 323349642 912175251 750958223 130623454 18091826 999334425 995788041 284491396 208326937 388037069 704168131 760953570 153013746 144528731 502848931 187576853 629441396 527963978 547246901 794116930 907766014 864520153 905445496 469363115 816431044 671439624 421283650 823752546 540854331 784195657 926105591 541064125 718607028 1880279 195857127 819088651 89520455 267095536 179493788 332055275 425427110 576533724 144779327 169846616 58789626 706321619 855427999 414048657 608723588 415620978 608138630 677545659 301803029 783415944 999163022 17267017 515214351 205723988 725326809 816759101 736769493 689248574 212863732 50880628 966814911 756147287 739069693 66795559 747887490 489748440 540224001 397045902 920683679 13109629 134026487 412751323 890279007 630703314 134585822 1683211 438735962 985170777 744149365 947924225 974108181 426684144 929153824 459997903 193132777 979675814 206790879 357076095 360766328 449742546 19544849 427840282 970488661 214774808 779020798 271952955 789399037 594912500 75858154 760837528 678628609 524047599 445095567 660368007 286031442 252627817 138013852 636756136 653128965 495348398 125441930 82855742 165107782 328517221 192223897 666741582 289498539 846605744 294135154 31763248 235342079 764939295 486268991 444941348 745890537 277492515 703549457 732706143 231991582 851151825 389524121 424414305 301537505 323929390 423809294 577762747 613981622 683433230 920216314 234365454 361714734 307274779 153346633 181021868 90391047 106076873 10671182 716485199 268182522 947657046 671564572 361141245 282375874 380628435 173117061 727366767 595567297 531804037 529864638 414276709 607935371 137262425 977714394 97361208 891649629 714695565 828151612 746920498 21735283 564960207 210382432 166810264 300538374 418580287 530292769 698055151 916005297 948565324 336986723 414621916 967269450 365179681 973791429 697774922 989485104 178899156 253928197 373131832 603508729 226316320 139966662 372824931 907114719 563020105 239753599 748682601 464040676 360500013 13322042 877802302 365425223 389290546 155313837 656848970 778423626 783489525 927185824 848304770 139828739 983884111 75593791 865096572 393221804 882422265 140802346 604064603 34285308 896235868 91237913 36919974 5483797 999692849 779323881 991692785 35639131 927582767 30133375 794234760 681487887 144879533 221020011 681754818 977757522 325645433 313916154 357936903 397785418 83834147 76660187 742149821 600487116 706425462 778512105 46022046 419702963 659117750 38017327 840253554 47193801 609573115 366769504 403157595 700965146 212418493 973695333 766951698 215588135 555181874 229425443 861873612 967658914 926754576 178811810 72603143 195384326 579335591 328546714 936887547 346207623 457504657 119420192 763708429 206156415 154923737 990217513 884424599 786832418 292601257 744308449 581530286 249013290 750764833 151577042 613324455 916731810 699506321 564718923 415606761 427821893 739447557 882656333 68610221 823432954 343066613 773444645 518412758 729183339 873579876 195414394 196037958 889003484 963676733 799238432 136624095 477563746 75309130 833301346 485159061 591499524 357069263 182732117 165784537 803157689 924997473 933167776 721515349 193185368 608378821 256869122 175002895 192936237 470781471 128049059 522873105 894776996 349372229 116772091 791954469 581625040 995854307 683474926 389312303 848463308 465974716 896507561 122705226 498494938 587049521 592888231 662636985 967352414 199537981 96790118 212829634 851451277 586063594 686542470 79253512 393638219 331311208 565943227 634911826 40356632 348158007 326633501 389160780 671291117 713893393 430729829 608952699 884259484 465283650 613926870 256641391 83658418 291897584 762284506 675277258 986055049 753499427 938225257 280519865 71663376 824123083 181489712 806709155 254648412 752566164 771018898 596277491 960949308 841224912 280418705 699541984 665227507 685843839 33464812 918895504 613418588 493734596 592915038 956522858 544324620 711345826 726460855 831491311 956642432 871140239 532904451 486138874 771444638 747589845 775616720 52081237 674012474 477058435 641241217 187110001 388660126 952574508 552023572 391282743 463940660 74452285 354620876 956071153 20069184 46699527 159534853 846284599 378724739 75041884 630443582 347245189 165219769 170613196 729311899 610264460 464796664 554713831 255367752 321804799 523843601 188066609 350488156 543778840 327829948 863170996 433962122 349741121 178141914 137160594 858814860 727435739 302795433 875820355 924932384 436300901 747663106 991782245 180719156 54897897 907587493 384301387 318846939 827290699 731275090 401047770 718221371 742222241 803885297 193123553 175355118 581672528 639929677 947808573 804417955 124567247 103394691 515194124 509348143 678005469 154653213 227996222 654512567 353424659 181607798 483789309 235921630 149840060 434862962 246440769 129979349 848088909 674492449 226342615 665443597 248944139 28187449 633815417 408725338 869582287 905583998 90461417 98896756 97853049 409752443 384308650 330567740 265439125 993601090 521146340 72646649 47847229 812584028 700031910 26993696 343610606 463224860 469434138 244876839 405327951 971705641 79725330 932760124 2157086 741310775 787922636 685746123 62942110 972434894 259171081 441633248 195368242 603557902 566675884 82196661 878763734 328191110 468935253 130237649 580300350 181355526 45140989 840392541 999045949 305076518 597577941 561714177 205644478 472840537 826624673 603716959 790059282 922862461 359646786 226106165 549771961 141718816 426468068 310379187 779651783 736461161 135055580 551812652 341062555 674818340 725540736 219033029 901051343 661119428 598054280 258614980 436814047 208923881 977214994 978914433 108086585 872330036 420287982 34453735 534061447 482674413 577032215 134211456 850243357 623597827 786226934 24981222 262047740 113748606 860174427 46395730 189795581 339671953 136030039 237747562 247931982 29922574 967657541 856854779 948220551 981224446 737821677 419792293 674310939 440058966 769228079 166239176 130544500 171690604 840670072 933801294 290243125 282026348 281675615 36767012 694068099 204094546 2236480 591011418 307590088 647809194 28994850 812427391 211771872 559539500 707310883 764361318 989132716 674184791 996841027 880004810 267658254 230789164 531986735 821918070 10276174 735802701 378813897 136406707 352422635 682022861 338892182 676544445 934388077 224360494 700911852 12746529 643900265 444562526 432104531 960778707 225550042 537303379 968234008 490439989 239747786 248190037 569718462 496254416 369029910 139924029 869660870 474553576 531183371 503809417 4995189 911435585 551589148 837965424 861495045 445800141 866976128 2756731 921293125 482414061 422824698 313232236 608228743 780720139 243366071 752368447 42861684 385785560 689717810 87552140 276380157 880244898 970932991 940864695 489608476 130123916 155562987 39909189 655424465 203992625 635307991 779371434 738833403 40041075 994981193 392119969 732421748 205699006 850215355 534288485 486512403 600879858 239015879 266570713 845795816 65685895 45575467 212158329 70947135 803994703 411235750 153261242 196720247 652459009 575588507 310162850 958112836 862866383 229483923 23908243 759532207 72872018 394807907 855331724 683584850 895378210 884503395 199859084 510659622 565998804 492551230 793408361 837919644 845333838 2696335 611306092 12954674 161304625 984175251 914226710 599326321 972329631 911206043 118021628 159358003 617921071 336451023 326383858 952736034 567500030 713199804 722863245 169118050 525267667 550261061 645456494 386226194 17601143 360800494 302798627 435057339 518578841 198241288 704638707 439427145 495389421 999798034 346142269 2033439 897403168 333350011 105079568 660681775 55501412 717068665 509050364 944337127 985331551 270184407 603474949 392869927 634460437 852103059 914779467 942254592 234579380 422552180 96432244 106675583 965498747 824055855 41094885 550515259 663626498 808626742 878278199 203547892 33600081 445826504 897325434 157672844 42629556 330830241 449398644 114364721 564470631 726324119 395790370 726696424 368125987 15999106 148693991 481133215 170113989 885549721 388873485 270784580 374828025 425498033 955942426 691208551 402058077 180757693 314260874 25476230 852211388 314557052 714741511 683085820 755644556 567458531 814907808 508423606 678376271 178918144 953375827 641379573 717996030 849413235 451687714 182793916 854385272 570284844 481114033 401596890 308721008 584532357 158630488 246520459 136537348 533071990 357124403 3520965 730281935 988894272 927348370 507271407 384650224 37260644 920113581 653321036 951203273 731084093 919918542 865070434 475240138 111039351 148872681 171827468 542609232 946556117 921141801 637091534 659934014 772938240 952920357 10099210 626150387 410476355 852872366 372914060 894210463 964464121 354633282 635181726 134696736 744486029 374589989 868320442 103802864 922547487 4741857 189442298 609608430 846317859 747109970 298166809 680009129 341747319 931209287 510828121 228889603 754673234 738157822 534845004 56659146 67265693 327168984 39501116 461773692 120587227 863425939 974521438 526089511 382283164 620284074 632004781 274965514 18717855 361970104 978554635 145746028 223867155 665856997 779139251 885919044 932603427 177206291 608790886 165611915 559432167 606099136 323204244 10342142 219947779 189008853 468025951 508361780 475719658 542812645 298914257 890285812 669767218 680147035 901666307 655130517 437664156 92884488 127430562 257319884 530690123 13374566 799010706 941939802 449934821 336073176 99310458 598249031 329789380 604098692 134846388 508165912 138965408 440679506 605584227 909748105 376981935 570481016 43688378 495524640 644724607 516376902 249674461 805536659 338758754 756582493 227442917 125633486 666617466 73195450 247094932 75982903 532002389 258393122 770884703 30288445 654955665 760546190 205572878 918191674 798763657 757126583 142808693 438305007 90252269 877444929 316142523 615337649 442749416 949464625 422902886 578881536 941760315 257558898 971133717 360620945 203538400 283728582 218376132 546153048 758922524 541420285 714817275 77755515 916645038 661380656 956153445 779016963 400749938 970599662 581125707 915590199 175580118 259063632 574328194 60227466 733887188 91689675 673371996 338624052 292154240 896207127 961879358 242401498 538356454 392792061 431038186 386723561 264711679 49400992 899401994 412971971 223574136 148339984 348262625 73661642 125000257 200078284 412836595 150774607 801626313 308636252 756924610 929063940 847551930 261421003 676335411 398513024 579385998 63456423 503664133 792658709 262622607 534223443 702039451 690552086 477195457 185453765 622431490 887706637 911368463 860054334 275024516 377808592 32924406 254232437 659932667 619530852 45859535 491315409 40025276 918657645 487211706 375506068 109622422 288905429 768361438 76535012 653222277 414751538 795430901 468864538 108556107 575660767 712789852 147111261 258146442 415436164 927066583 96018328 897438039 548527743 583667049 386396724 50473516 37693782 56219832 270472523 401188002 191969120 991538912 183354959 288490495 32751653 288646060 110126431 231594380 343968272 608329740 358613671 78868672 946658786 777949804 229652269 270200939 761089555 464999840 867012361 365493679 183107002 769607593 779934567 519878601 656072106 799018906 30168057 957632819 228140116 603005542 228995917 388547949 827449399 769181003 748472026 785221598 138704114 403335741 640026641 423083541 736615304 793864097 157228974 533591238 453389798 154956345 105062083 617072485 250108798 554618918 336820152 562481126 729805736 419252603 105101301 568512598 715530059 952016256 23199080 252524530 532170234 944124701 682840676 923197524 321817561 262511772 134374028 948201382 401336614 770432445 303024413 478883946 530330070 290220218 402369201 646571058 537139511 761309473 896005662 110442626 115571994 160531836 321835223 621521771 77232789 492094531 484192640 930041487 193936787 762367075 523426863 236541009 7316856 522471101 333522125 997538342 904137844 630712888 894518519 390914917 365828736 883354291 351915511 472837963 996642871 2259828 351774430 340134807 717154542 371083412 443259605 518566368 78620114 515413267 957250307 589007831 121925706 233735502 962736480 276559096 130344760 91995589 57864521 655921825 585958784 8333198 714568010 560470846 943465523 565187849 562920645 618933320 929619672 419268974 6127261 238182594 540307118 213699452 708775028 616042869 528932790 44724678 923677851 408905283 148253536 251194890 300179795 212599388 16507317 53770389 276301990 614092901 130681989 820707305 835705420 589068953 533308809 372335439 860724658 284888354 785654585 540059454 324876882 830597793 178769068 839532973 814243625 786085978 666913983 428997058 376562219 857969877 186495555 972445138 85253773 6267958 309691134 58629128 470336518 988571291 528161189 936194384 179062881 878247321 632997459 610735261 94073107 294262207 610777674 359869544 131548898 19582819 119905608 680730993 433469174 809111677 325536864 943855310 181761886 543865966 880239909 649475608 889948825 28229353 167729024 77510574 852031820 45130663 146678611 277879839 603418000 95113336 798965643 941615460 378542542 511411908 492734890 703692880 549825866 385205827 414495761 96690834 855675438 175314857 528338503 245509831 285951357 927753406 155776134 782002677 625848230 377278976 534137793 308404830 481149755 90631902 31273688 69218644 565510727 539375625 404115970 767649264 234619564 148348784 99141938 105404233 865145240 395445769 831760345 296769633 151357098 468463716 970045183 38015641 292954751 700221641 805724072 789004985 363076960 268043805 674178975 262796396 810976737 339904520 315331731 543264403 845112112 835493634 748405550 825850354 713822368 500965434 326738465 416028655 701943811 91538676 635627183 144597497 9649477 903189708 126312385 548571558 579109303 127395899 35720226 2397053 277618354 984303153 396568005 443792259 953428360 814875999 297584596 982817129 709518624 900466096 669517755 361448322 469792486 332280842 209534099 73799810 826678245 662874181 681528222 611148632 947745927 994305772 606822275 580871605 491832762 747016223 515890201 179379217 733484857 11931066 681082125 483643701 773381719 214708306 384534343 304791762 252250425 915770410 651365170 551564565 856902505 416947967 424872244 495627985 848320217 823045526 211140873 513689451 442501698 981280315 948530468 863789326 349041595 696314807 68607346 156306777 415606751 841870164 276915025 353530666 359673167 753967228 482100397 891971983 481453477 314223573 62429147 610406783 771895085 658547071 936186294 600395783 257138649 946365427 364052242 393212203 283812597 609390816 843897316 761230329 321898891 218070289 586206691 488386935 229559141 237257280 606311845 268977251 296054825 574900933 782106233 687636344 952329662 311989705 235355065 471062585 216242830 122655770 444286623 830392305 171381172 781661724 51306941 148350674 570498575 572337867 379720731 87196368 333127807 62164679 224206898 576291388 113118744 2737050 248740071 34350352 477138745 801283974 367626318 877307591 872628879 329397540 556278207 908307615 944221233 657888227 111101584 31319047 910115858 596841288 288202758 641378498 308935026 11943590 386097463 741018622 879852327 696481875 741962144 223693634 299559280 86737480 193359061 821148248 351952284 409646549 72651751 125624058 385842689 303392296 261655886 330487361 52557851 628111555 304916851 790726433 471091364 786911522 597954358 389438991 49873341 97599500 437408014 42347390 235641534 60018889 719451271 255384506 733926566 170575459 518474401 700253677 805467347 123243261 723320212 167079705 945832764 221252321 2351462 240032554 735725152 157978672 345801002 983259139 256696750 397383803 708639344 655962704 98508931 546164603 919150388 562396667 988649980 621218016 621119186 924213157 90337203 378965530 636586491 596536761 997356615 12937821 981771169 163449001 581373918 213415363 593675954 569021426 295527506 584552146 605392358 730175776 939734892 229938752 737783479 892940876 658725192 743920114 383795715 300517970 541888609 534165035 492282501 714189346 158297442 427261500 124970282 770516342 551758143 930087371 813223097 551860359 988672648 373065742 274190655 206671375 715293585 963301425 921950740 353613330 528563419 227827081 702411000 921911905 186244605 901418188 745225161 274022550 18514325 925848113 97466357 658699044 466417099 263035593 930945071 950539745 976612821 262421810 356932904 883020766 975029730 795668730 705453445 588407460 604401457 767632965 848503871 402953435 707938614 413445072 562631444 550052571 245751927 78785166 453457792 23201711 674493174 57583098 999627992 174795890 202334082 271138200 487506071 222316149 221407958 259121385 666510969 164333182 527888726 953113502 355502647 808289397 306508041 332321833 124510157 170297864 315579279 881054882 410811551 386210614 208143325 465325338 989540622 213202636 631473560 841779488 193619947 600341149 718690153 850917001 181439417 472151926 263801274 206082110 685192722 392959904 733030203 745721208 6463481 128199655 468503520 17971995 678827608 191005406 11686930 423695014 695034965 940062155 57808010 575185002 508784744 771394126 851045336 354652343 855554835 233802073 368046376 562446909 469805901 947169847 47006579 695762816 140546307 225644219 870046612 566149140 77569890 159761877 1355250 601045616 913768402 923220606 995332871 928965113 520193931 29309838 739780247 869934530 968596244 317912317 7958454 261353032 163039858 810784297 424996763 572611418 715204693 104388122 420201914 324550656 218692027 490443454 872065617 171331382 397822117 95851053 463926003 749312917 287814287 84311272 123486997 178563482 917385717 641832167 625081983 97097775 707356785 700578890 760323037 512949656 362488752 309032303 284174491 219714776 758205517 325514224 136159202 716184870 276655544 297428276 193098536 545554532 676401467 874554066 792850631 158010892 989245782 320992604 350198468 823633430 573436348 5592807 987761879 555572548 711935691 507808398 236735922 690696413 780663342 49215549 706828149 665098062 700540385 767012710 86275601 895605408 441635670 658116595 357982829 416435774 848988938 227779348 436711316 430476949 696596315 599507945 537346158 620476724 404878053 358040318 986923702 386577446 181158656 998723820 624840260 573098335 328997760 640090028 77350618 221430002 384527892 335192242 306720951 421183236 547055728 692988150 926068800 446701129 514147616 3556511 38527234 916557027 977867738 325255441 595942088 113216020 4202580 271701000 699711393 337629324 168838898 950670359 232602642 621729622 849798834 680926337 490839591 310979358 814865262 256776333 336120698 772745102 241323706 906172510 172468476 539943303 71982158 179653455 184052325 708680750 617590568 914954752 565460747 789851756 633918806 913767938 696405667 891650359 169743063 7668310 837561365 86015997 493781720 760190152 85197114 777880537 340596265 506687885 109739710 112205127 864110030 17946547 322639365 803280443 949841686 68148337 744392093 570121593 679039067 722776458 908642373 918614697 278983863 12218755 532121902 89668893 704511403 450632716 35183411 916424770 896096470 68714443 635103578 905688917 626580157 748523281 592797229 783901167 674500269 6280383 657604179 825435902 379814020 579421905 152203422 311263927 410277360 850430538 477624221 805830990 375866749 137332211 202330562 19414808 904621060 704981157 939113176 620024627 771269729 582747141 674085160 22725602 825145671 553213619 503693081 634898434 109052188 770081770 168218828 116871680 900269581 823005653 415800785 709717597 644894042 870806301 290949539 704326014 46382713 466854272 711757064 575228182 270239681 133083863 539145972 351121154 557022660 587168502 661337769 80451994 950452385 238362801 699402243 161368630 776994423 417814316 29592947 311456332 121181794 267091587 306951860 124565890 934743122 169842842 398511950 228806111 912809622 350304003 751470773 503593973 479511412 167145411 412981432 436930493 618986510 457651675 799575056 142640637 197776114 850580557 829003701 325020700 637200489 546998949 907171263 59035193 441140255 173390997 789284247 567653748 20065974 785316801 300431193 627395900 114038798 79827097 129693299 468048264 805078103 106850083 738866293 751854084 41619462 382609483 891704737 843543406 295839467 323871423 717038486 960905072 417960207 853965231 971039019 808233333 676483920 117271696 863841562 539301580 960277387 319783965 649775963 529325 810537205 909205806 481944241 497558806 640376516 526305902 127323102 123976940 709243942 91785868 521011677 989707558 855190132 730232627 634031840 330859180 900695036 316605810 379060340 725188317 789845791 95510222 515530828 51726094 666549370 916072239 968186127 791882257 653415073 285704090 695261072 231888840 488118527 374814444 372706295 690007270 130988962 134092867 234566649 262968625 367560623 176885411 370645083 16895397 670372355 649676539 707263630 236471231 137050415 824956140 649990976 464889320 977124183 92162412 278890046 742686836 996755251 198033572 488275150 306375132 253684834 588651578 726552287 244500988 340420855 594546420 873526302 661420070 882173731 273602489 750590110 851063616 885713936 177542016 955651278 401752421 814301382 823751786 248245700 681063654 586632254 635423206 969424715 476550909 339408469 894017210 356783919 456251923 204245785 839775016 409372350 907343632 805477343 530086054 408623379 775215858 924723694 668388302 54610197 57193245 297496529 903968466 740298561 924216586 212379289 687532374 915693796 856565072 186416428 232805874 404273627 457372195 594516584 903315110 620015460 341156273 61412634 972740791 689746733 652702582 161399992 388675838 998915027 106795721 44354024 569149798 797091146 110628235 209621085 491143877 430746358 509675377 552762991 108672998 957486076 303013467 764649927 571172572 633815249 357599699 146586520 778744042 664072966 947381152 167567178 908832875 108523481 21472289 678115830 224130807 183682349 778123848 301766447 355924176 615874745 690428896 222058794 12416699 927627319 91640472 937709086 689994402 197471576 804949915 832382884 341324155 362087915 807728717 558848073 915351857 490543843 838307065 752182744 103199427 530549353 837011380 137382232 981035112 596793010 602580761 911044303 794326307 563162274 923996943 643053285 580738281 933985277 548558130 377327453 956079497 888970207 344635946 13670856 730295709 595890316 967909287 577329493 551650940 405988325 66175045 818072688 841161054 437262036 732983850 132230720 211526403 269271547 334603039 792486188 667843143 871978176 611269119 280647600 628341998 185264488 66759970 764901024 61178273 473653456 409199181 772611276 606724317 75939079 347956424 849153280 25387617 16170511 742071349 190046406 583729050 107856710 901929131 240723017 167417229 162574391 751605891 462866312 777183246 503052593 757999754 672943933 37201284 764054765 279466488 428731943 308311935 204909429 762539775 363809832 896797140 588776947 148736946 129235351 795636223 883004276 441939736 962149861 806669169 385593324 446215480 948608423 258820267 994215310 364857665 538906347 493515514 293552784 275760573 629880867 788378941 359500324 719427329 482353083 958086539 950747860 37922659 867169669 269470830 556242041 942741290 755423443 471296642 300375660 97442704 393306284 255022273 778395954 26074988 926164763 231904427 479873925 415980332 664381972 612083399 97124732 330454139 111844324 688062952 740066322 269142434 912645385 330201106 518229754 258455064 714265775 477269485 163460135 140168527 964340905 945678783 373820790 111080795 861223108 406950211 332913957 384795882 245295639 909981902 461907438 245727810 52310941 276529893 139979754 323630748 193968573 181362488 915254631 552664156 126076653 387769638 24905859 326242823 613287630 651692877 1128063 578371414 4608636 113198963 130962065 981741900 108613650 383451434 854853719 535647676 643666347 198304472 875356412 62196136 968958216 748485579 153847600 79338978 334721843 563790556 316257412 883932608 147001566 333574751 951857543 662294071 634324148 649108345 282139870 434788175 937086751 863631859 715867968 52802788 585241650 89129835 637320871 232575859 677477788 122453233 818630864 277710121 614969296 46846973 113668752 339834265 530947514 860158310 33198668 948701764 267647070 785639695 112186391 780539276 192655337 345673166 461249888 355959207 98775992 740947064 212482632 162181910 720084774 287088403 739748590 971771403 725827241 634965659 596397623 374712630 11740454 325488658 150786676 184509835 675805050 480420637 931903598 905005276 855465938 960955600 579191511 530655805 512966836 875558872 786777252 105963172 723928661 928420559 397728633 3251726 352983789 805077020 333328198 579657303 236830354 373282659 708952252 282502998 456917751 813270454 498447053 768403205 839317783 671937868 152447256 925426125 969915266 645466717 182728937 780835640 491070984 352381315 484007582 729798380 773776394 995048803 658375102 881772846 487206364 575208733 288458135 628333528 781050336 527773126 40720530 579332775 948938032 694496822 583547736 295263906 610978430 952672563 216529786 548511742 880793671 808177296 994478960 355138787 986926660 743664812 291227267 698874214 642901143 5915287 71533746 642147272 474949830 85247461 798374908 871078410 982978370 655125944 605483555 195420902 676000535 544479827 961533618 489899196 901964861 129997689 567444943 735212946 492352872 736995694 393336979 470850715 470079532 338800486 925251652 252386406 828511236 550271235 876374501 31779710 755843248 944560158 24088730 216644468 998181762 71284988 535086628 713820785 93245571 341559245 726352539 136267940 686509004 230625863 628800956 848171741 460106274 121433506 870244041 669469727 670371311 281220477 99507816 838971762 662768436 486838695 612410691 315109377 558232667 561380594 244581836 671190499 248852497 176123568 949846104 921405932 321575899 29095929 645933156 171138012 590960625 825341646 3739891 303806666 541282169 80207938 670077492 502036088 566345846 362250793 604407756 723859550 770310358 16752932 306220139 729120563 130271540 997695731 661726945 502014745 322810883 446450678 88145710 155177851 357650760 132346991 928220058 637471163 782274575 327727889 305218840 408077710 23794127 235527253 428580687 449997415 516701780 670932231 646455818 137475024 818827133 239550404 924028257 562212685 849065512 614659316 854839755 174474912 767466483 779186625 218301603 621263405 985302819 145637425 175909833 753681512 244805846 749700790 136142406 765146787 39947452 896818742 798747284 857470431 666872989 107138072 497094691 886729878 393610542 641852715 209932166 956103681 619662059 148276905 808149020 272667224 749124906 976872083 68586989 768259757 498375459 302565357 624082845 983082691 191698755 295032443 756106618 654059291 517353116 761621018 789061297 533343086 351010010 240822566 637373239 688397466 444859529 187023126 859930126 787614816 651978715 775496444 620175737 477236782 351360642 278352318 199703894 930133981 700038583 346227910 645755524 427571234 225417362 267403596 174817700 763921434 827347541 175127604 667064330 517298226 360616866 522986432 493350562 194288336 210505519 868601024 484387840 828766608 967825886 256159781 823458487 852226051 247101819 694781891 165621559 14523386 565849388 836068716 985402740 185399823 414062076 239696836 938265664 84516937 310970604 825899169 641561028 153943974 38445627 681374440 835591038 476242075 140578859 540458358 815204350 201128502 791719101 39493619 344282947 648646792 121555495 189928238 935189613 538504434 886541039 160117689 666257244 728743230 561648770 112430755 409800960 748182275 533323524 511390261 366200597 82912401 581125622 100524339 943551888 300833102 307555432 941733319 451115233 715866070 654617773 297282233 655316158 167515035 458276924 750016115 708444892 324074920 386792941 57819976 44679947 311998180 212413370 466177830 625208243 666803632 910184673 258280082 596745098 411780337 497164173 30451591 306644230 486121201 725227624 817720026 986775444 373063326 208804517 164912559 998302855 81268843 416441670 580531675 1890970 401251091 963197527 262801191 645959845 300166157 349925089 15230368 226215322 734257615 823751854 333838274 690036862 789219532 705246424 761808149 603504529 484264730 191236513 369629053 221904524 412691436 310870216 380210881 655188092 620763779 233670984 312478354 803566941 467403383 756503120 398405514 457461106 61352791 43184622 96984174 163735590 604785909 159665782 394525367 715186762 78693561 6810049 691351192 550521593 853189637 453833760 615223834 456418334 835347280 349743708 327498506 576406074 381581009 65564921 57136596 656869917 511210126 695744880 328064083 351491053 54901558 875254771 178857126 817717035 502318651 752095149 147366020 501590126 134344021 900102681 32387809 111058647 356928623 117354619 800208932 914266600 51750697 468674975 404556252 919205799 884688662 358887669 293472923 418107200 60511218 349395088 235143928 943723512 58229152 333794055 393162321 725712417 127029417 912231804 761557165 401783058 306032184 837822553 355230098 575454577 435768263 764417024 656033392 533793267 736703617 246494146 589247033 536552193 661738703 561924637 59526104 926137950 314839223 505886670 82146858 201533307 114705982 291731517 161527679 269166827 419892050 327320246 213818616 942838650 759540278 113594019 372146843 298446952 890121598 797004670 491977040 803841830 558947103 857756618 656433455 475595530 583060048 849935730 234642646 156307960 945950248 556669988 942816247 484515217 633350683 784180433 562298740 119257342 373196688 336934877 628779621 215419830 276424289 760155457 172738718 137382101 64789070 456915899 538534329 141968709 739109590 413284974 710113712 91003350 88118458 593248813 694324305 466894459 783491626 399945260 163087347 253729149 768234220 686670576 812418165 722052325 195736145 879357079 919715544 330023177 551532761 307734433 670477424 417024873 680878033 615744069 411612448 289173496 589508090 730857578 38278628 244504070 599752321 645262564 597845261 682486983 835319541 136555358 84795786 655154966 461254596 266812509 551773408 342492171 303891888 12364512 553456261 678117009 659332857 132206644 746213010 556088749 341427585 700825597 510481085 436717724 256056601 885859855 957093756 495983132 202203301 22676009 132128905 62298781 384978678 368824310 612720769 896523973 960163400 658464025 248685723 457267246 728281546 707592966 93935891 248843937 740671831 73699055 399510721 266616433 97027529 706061340 918774513 178510540 405793812 966578787 165491313 876293432 256495146 924107597 543280754 112280604 365364357 154993202 635681766 508609979 759171821 917282523 666201572 438484292 97812089 803026030 76234921 745726380 161270060 61815349 123292144 424050474 888627586 799742044 584278928 214170330 446903784 688470860 836849157 915281169 377552712 280450028 5345952 342862716 42760503 31211289 404097152 514562651 92793659 203389694 815781914 546461516 730752583 17831446 384999258 495824337 230404271 217865725 325961946 24390731 51496085 131936530 374004932 267719591 434978812 333075856 928598329 351781617 728190630 441078304 123279121 177587842 909088784 418135817 889475604 452532633 753958380 373407711 679271084 654658432 423730970 179920134 126886763 89098022 225714756 729960842 946941078 162440836 93498981 89034672 258923306 573050971 772149539 764788027 753318866 149732672 606582778 175505488 757518363 151477397 522934527 373042196 734785463 221321058 114291361 148747961 909816053 203915821 722038831 71413306 558718891 769777774 367412906 788452301 12981103 933549643 683256265 390146629 179088152 137211944 249315018 997501071 685516808 155380869 356431591 507186613 309919797 804116944 237741824 209383517 111551784 23814892 900596740 924411824 969949483 117779887 68318580 991643378 242438076 958567652 420597200 3487007 55871332 628996052 138299220 667772540 790379890 141670256 994412010 173649212 33722996 974978930 264225432 660248397 174638599 842019661 793109625 613412260 765578011 907835145 446268491 979339119 242595601 560206504 947568089 352796987 519031574 286879544 833905791 119540453 348178218 466853221 706006145 274714704 703755724 889913532 829840682 247359095 276295219 119656230 338031962 265554340 907691868 40952339 248078316 811352036 631692823 360018883 862969534 675230188 993169000 127138424 544332882 887742506 367220500 520133838 868056714 148258610 202766852 793875253 686157005 396661737 757302347 987890384 541316330 933322185 441043735 842657944 570333220 575540520 384067538 34127025 964449501 114391039 940492465 861915699 211799104 959055874 463803165 936024617 62196309 846557123 367216355 323472668 438805688 570489758 786175576 371490027 771937194 930321467 273098110 895719813 766570391 4065380 860352784 818149747 360163192 505810232 497065061 784180877 473418882 454094451 535548769 349723522 115239404 815948940 433335973 867915525 761717545 413585005 670849306 217509801 322749210 803093287 774824554 842446501 969678650 461146645 676320509 557854577 30887044 584144316 669285516 500298692 814128075 986806544 524335672 230259854 925883833 475291353 3122846 570300362 917082010 664745387 890801629 18314686 688565302 158256190 500091099 217597331 666482611 380968628 659423959 261937421 451828694 329249925 423256351 244863689 150983751 800726742 764918658 318243525 660696495 333512195 806894090 754877940 581957776 705366529 379511376 125057115 115714273 161603601 694566107 424734402 980250578 518872023 53062442 528802418 803980463 260438669 679687867 878736879 524445417 691503615 40564496 456492275 200257762 841217792 250752181 776246240 834306539 965222669 188930444 332262054 904293920 621035173 830209891 933952039 667911801 466680365 633482523 954949937 35618845 86576205 796162717 173462450 510262170 585323260 760442228 44818505 716372277 228193377 71349532 349745902 748797636 978857465 491740749 390778080 710003264 498209709 380258053 705825972 623351363 229295014 238838502 733067318 687400513 924340954 549120052 490208107 728388795 272383840 808181200 786360105 640909939 957834072 437964048 899621547 653195196 163706439 545668315 343545865 660208380 212501602 20119628 643837682 100802831 969469663 197067521 374413472 851970805 502904440 250882132 55901139 310914069 728229984 491324601 644123915 499569635 506885485 567058586 979677419 99057292 873100861 291225404 998414953 325693614 18976764 729087991 280131363 696483990 146603618 232604053 414408063 469827525 655130435 469207670 87689427 677309179 171629633 574617426 719458028 543459047 53227845 651652006 352792082 786052279 788074044 199145679 847141962 543789940 836249771 576439292 822417473 441058891 370165865 934656324 662206860 433465349 159518644 271266384 269202864 447979766 652887194 360622402 816464568 139966015 893979601 607242134 294537121 276826220 876021747 132850892 100595246 158802562 448627775 340006361 517509170 32439096 980753370 158511205 605504753 605302374 64049068 210154243 859187350 788872615 295738179 914053249 217066836 408039455 772708913 387778772 565439983 291468539 601607469 419238959 267510519 79454089 994047265 598543007 252924483 418270502 425244749 430976280 58125515 620791304 653691507 149679895 490540590 152262830 60772733 737518726 777878975 759393783 49910530 249687428 732092474 51123647 73608918 164788843 184699303 695161676 898856773 782656742 811948265 661252830 28426848 639277960 835310013 911760675 223027726 16814814 513238804 727595868 114759905 458258183 570282417 375209761 434246356 361338179 458169053 430015559 49306255 779190890 75562681 913046077 12894985 891463801 944121427 575336620 777111162 729420065 342231769 7168130 961810621 498700819 20371524 16311135 256316354 616273815 78443467 885579712 342916671 890541035 715482537 87551547 82737691 68445683 360669957 540447443 793928300 515785997 978358487 586106527 919630477 786889171 135878385 7426138 380590503 133996392 370755850 788557325 223309711 930671553 377457448 920406946
