4996 71
817572379 841265153 985092212 258879986 969354686 274497647 55515178 607378505 773597758 720756469 26316154 371192203 940208776 460484973 820179154 422217334 171910570 51358765 544570613 719994323 996712288 431375815 421405112 828855753 847721907 148897701 289611219 297235823 548670671 603199217 670930290 785240380 623584230 645120665 35854981 463730884 278791759 106093022 182781250 712014048 604750533 56270884 713696455 510715541 362019101 763796339 791385623 749645449 277004386 102874792 441065943 479957668 33613554 547869310 519132384 820180684 581285631 104293513 853864899 764495130 33396235 161793211 223266041 214092944 859769069 585495602 726820089 346675721 360036102 86443419 58532696 517010745 313248033 472370005 375768923 9755856 521458382 273242134 754240644 258599116 184398053 936473319 84284119 713580519 177402192 100784434 508356895 422663439 206447145 134276075 529235069 102340283 935027239 178310997 109049774 669399959 566745662 240531667 515843797 104038254 705373980 89345163 879235427 618900881 6779126 750202764 172897049 788923060 847745827 170773713 967417296 6693646 181352016 408311020 741409300 920989828 763685883 946802949 935425407 717886571 27311795 550371739 826028027 935902199 602825210 463149809 111669524 150143716 919387669 797113530 424734800 407372832 135456875 595147979 529513774 197841267 437746319 538960832 958267187 639880684 801886546 480942154 501387402 201351032 36944054 320565086 461953450 446912912 282768476 571968200 341159685 673584945 532070650 957177106 759562184 850162439 858666098 692604667 974272545 219153782 994308521 883180919 764342762 649688374 122433308 18488279 464571213 432874636 454421955 269963266 893323607 833902556 954626200 833742638 521743368 275485203 618947006 515573676 96217934 354219855 450364233 340534593 797470821 530179406 907557411 758627064 447797492 54196671 716577457 200897712 650732395 18586934 321873424 261454095 283559697 660428553 941283056 580696263 978250935 262547355 843723699 646684115 277896230 999432853 576233488 748809399 147865750 966109353 726021231 720117435 84886203 931257162 547176614 527902697 180927027 58579973 689596262 262604561 896996806 345513256 61302680 937853845 149244435 118639761 459802641 71893559 549649409 381647231 382853029 40595177 36533330 631118700 623093630 198753986 852394990 38120489 961495365 303288450 363329498 290271517 714574426 626684600 103846221 767529757 95532681 211901205 208966168 636992683 122980624 878045414 699139687 979109886 7564568 774504129 558008033 526779949 188058031 710728588 282300164 633737819 517292329 852404981 654776900 439493442 22463121 944746207 770757492 385126337 660872133 501265684 640634929 28924216 9983684 48504021 294660512 329325361 842698862 984692956 479854424 76102200 712654067 755828363 966328181 680108355 282939084 883172894 736110069 574197619 192344319 332641095 569529630 949711032 57786605 736496184 156022290 746830188 334383809 78777280 696960330 498181246 812457182 618783960 963911518 772811592 610731042 133396495 991111362 517296710 765041692 171299336 159756744 148468600 410678122 27625561 814269813 192415481 136167370 11493260 266010857 380080363 328624327 266431712 965243932 644064653 377241171 513269117 788515960 321300013 103866680 90555869 753986380 8853007 964885941 124015129 409836088 305323588 571511662 318639720 161007555 814618460 166650094 782070228 47573712 18052351 867340829 830981268 574960732 324857871 154462209 595881420 385495357 693308522 50907898 198713393 750911924 134577297 858969234 927343652 904573915 712155748 963598011 843948896 514500594 43008729 435824176 426364270 619406113 624924914 414732527 779644354 169712254 126006427 74323423 209004 464032080 171741882 821410091 322045337 915096734 863714805 606560670 5990948 193383306 57973056 830894074 538534086 901942997 587977477 448145745 695229720 664070263 210055876 637393932 585726643 276596702 19038003 197661132 452168632 108051712 918486322 745575275 187277522 257355826 844682402 261504730 142033475 772953484 460426342 291146882 249121424 942419814 403081259 622990740 981284295 252109971 60233222 52153942 683413934 731876741 221034609 444319754 392685849 381813562 820885882 849145721 281930545 328179332 465978578 301723818 622845275 90886502 354049799 250247685 154614265 123503382 828461769 469140624 617818456 707592792 68226058 63759352 122598672 342440196 237595515 295910972 409286792 287404248 302854197 522673125 346446002 723543868 70054512 514445251 185723413 485802127 834949941 355385846 703719364 575768236 489715929 567474104 925451165 683572287 466065689 847468985 273187451 514232482 310491161 990570475 969725578 920707264 674435228 234882812 302014950 837316134 922580007 90617869 4011303 413997997 555028278 801711638 941488807 537129223 892688163 101689862 949169403 396369948 217252223 754224413 16452180 318202670 98348401 899098290 746860606 29681564 200436156 55025777 144163923 268707185 533649065 86735882 335018300 688884694 599445885 477494445 55196999 262508016 115216055 244765236 40437587 972897665 541014017 160952665 790815737 174073868 355316780 207806431 511921860 50800318 124695157 288360058 383810629 461557404 60293961 254921885 250941561 640873789 243341392 442151787 99954858 346227383 506499095 193175726 784652166 730015112 780087508 105958020 22674488 49245451 857881392 101886908 518960038 391181534 961256817 512190937 34032597 9076785 564344267 834407456 77238948 33980799 946910516 624465238 471196780 499937539 278824745 293457633 391023577 114395898 352408329 736189349 138709715 994712476 683844461 889997715 510284353 505501807 695292124 93946281 776124452 209145593 298994099 741554970 922307383 122907641 11570367 846440041 527141713 57727282 514919283 138326823 44393654 314723317 93141813 226188038 881190858 729998575 174105860 146556945 257022056 380167490 900091169 330237610 905453409 216033078 431709908 933445799 671868367 696171845 327218354 963105861 818900391 107568969 430195535 741320115 448186292 378007844 276375770 302962102 47011990 815440171 278362074 358219152 182850824 232832746 910582358 35896233 762173375 36518140 608914895 301960580 326221675 59338488 433091150 354678083 870449929 436778719 690256793 802388988 826120115 277255071 759060684 314540115 724199759 386921157 359945864 920845687 786588780 763414459 712505524 55577184 70211984 926100451 7924928 655416194 897302972 752145916 175024934 28935358 882580212 654878078 535179920 905249950 565579882 213492208 223767067 40405604 683089103 313949600 153210028 331897921 915517169 175673415 166254203 871441891 826625751 542110209 706814639 715618445 29933232 566131343 211507094 552685835 132542387 76738824 294031964 635317904 935921321 164419432 34049018 406143252 1495220 427865817 405064475 390856842 80332599 243688859 742504269 257084585 718787287 441853869 641643033 30318746 304169865 360516356 213106352 427753862 513420620 79674971 726542284 259651698 99251830 690946673 754316080 988350849 704385379 557174839 595066302 539205786 86502483 230031667 581512272 318643070 339927418 575149929 417649262 124861272 60321515 887283205 578671739 382145929 533214194 79514233 296556514 491198870 392316160 804390680 22191392 47576070 857585232 176290292 966138554 847138105 444584768 24373783 175687879 260629725 426299924 148168209 375306219 123145063 131540803 429675513 128842215 227904688 602743131 452509325 441616851 589278583 466026147 486448367 286786155 99782277 97306971 221466613 282228407 748255176 502008620 892468589 754420697 627141923 978278908 379655240 35188254 956068123 732979522 246068267 220106812 81192944 1000000000 717765929 361937317 690787881 500814226 540659017 239037069 238496255 690977661 261630468 608371416 382161757 555105212 426125292 83323804 693805289 320734686 359498977 100820417 621668088 634740222 176365124 913785269 387279180 724437660 253238431 124307704 778786111 313533083 947947112 154332835 726861518 60722462 980910203 357484692 638190177 847133186 626877761 193507261 540471495 786877596 59503101 870107093 896763488 269338799 157192948 484304491 74795031 974202009 870976695 80435022 503059623 854934535 71446476 268194650 17938189 154009047 45303418 927506148 410060014 281159136 326173286 965634749 918717008 188817300 288097708 725620052 973688496 441300634 576300495 197316911 824357774 698727502 338852362 287157719 444395319 728614130 872054158 785831349 732574804 364252343 799541236 957394525 431900128 750981203 561213352 166487038 779817238 658251154 800762838 467846638 793845806 71175265 894827111 487506972 511880109 224493393 702509319 275614264 269910463 28151361 523343325 836752791 478937410 516687 741831960 586893946 925515771 952254847 121982136 829692831 433366480 66079605 358585198 117960892 639729033 773296138 915158026 437763920 403995663 376116863 419477355 208571649 19015618 138090707 351532535 550863346 496788026 195368828 397608195 414833889 226802862 396167235 621585424 723872251 609797772 606891984 992320255 509980353 327503938 222487364 640774147 863588999 807111587 98025558 294546798 181204288 148402485 354430044 131798065 828928549 429593432 206623269 239817268 617781575 568428325 838179788 592355678 74553512 25745299 206262516 94033095 150754374 298322840 87906554 200864325 216892149 892926171 775533814 570935974 211613574 992244759 358474242 233347518 245590874 468128693 9311051 184507191 375336066 134909189 200892057 515351149 698598862 217622010 259806826 843310123 698506953 605430483 894340138 503200515 568559907 691578725 273920300 86396901 747811674 972908820 175793124 203340892 881092571 557019117 375632060 412015940 359809192 105753770 109944747 414728828 491747071 53033333 223285494 974241668 646891741 228980357 261236727 576433271 707249269 609896332 556255677 56795953 16122451 407630714 509574860 870094152 226942015 190720817 882209872 257676357 379075298 406193680 95445793 165967871 277355041 630326624 696635639 173806228 168687513 279643319 241684032 730737525 33161603 440207211 622198822 974644237 585942393 407288103 154592608 317288964 420952402 126251277 702606122 200421621 25351594 730962214 353359752 435754163 197974176 798806511 99437717 207775943 186485933 235264419 661036576 485157927 12415532 437135858 332555496 134347152 669498395 488293436 30641896 45248959 599752493 766444867 749121179 964856309 576706544 634487012 746130927 898486349 985124156 322415886 726380344 204279720 696557629 242942333 64684913 729736695 253852606 129614629 995942719 318005118 734517735 235242762 15166926 230760468 16692085 892771697 147268965 348317017 861524262 314340133 170453760 573712486 80852197 616645502 208383617 410126257 620826866 543203200 979099505 737991403 270037296 784122145 480380815 906142698 294925307 540173596 951177220 883128325 767293370 606111258 823407324 199564177 630903688 131130154 932561089 26011694 11298775 980638693 241695121 156637451 467072162 798545400 860752331 67619014 528314217 797563854 762258794 351186703 451715730 264651144 244085802 44258173 338619932 411924139 854766746 403294196 676466911 244551518 498686333 485770975 342979428 259957935 205313448 827175464 357750309 342466130 120266789 976419682 374408514 321530565 487881836 459920042 798546862 909178793 26140682 722635846 436834573 891690301 434297097 217485773 751610480 227251205 204385555 7255450 908983601 149989330 18421639 879788436 42125527 702879871 539041615 126245223 564685894 998605849 612209560 183247006 98023536 21341155 807636584 861641805 764992861 574938160 66778603 381095891 206908409 309651955 122055757 206308241 826601180 263630760 266110104 46455252 6018171 247597634 264985854 715219152 761972813 668088515 125830694 603166289 541787157 189281537 213662829 166343307 865328298 653927501 241840588 225112983 76617121 110976862 518319420 741945191 486509950 73521008 542950090 685814950 164988889 307169096 567303562 926109118 557808846 976588249 546141479 361796187 806225866 718457709 370239007 870825236 859128152 387258765 931371602 989937188 547199300 647478456 372855815 96338306 306658855 136335105 690857182 788725040 173925039 564848907 771987687 225502330 768072916 674043441 152530627 425982692 435671117 676157322 582196639 249018450 206169170 375354064 770091075 338224621 153859302 183874716 868149390 415751061 838853485 709296728 768307090 459405536 344982690 104372518 979522232 98700206 795102646 282728016 603371412 413027704 98645430 264738407 616021758 591751728 703944718 196261754 490680851 723741121 325527757 321202319 425326914 153073428 649022925 391668242 56984043 362937071 845779148 126990133 911168366 272257035 428032645 67552127 694075495 498360581 862431539 318444285 936991635 538205134 348576682 227709616 282585803 195062432 497610195 334976974 294401356 307926651 247709675 892675819 565825227 697085856 422301060 151041839 553952178 901073417 851661301 909242522 796705846 245920243 747454358 933664186 235488801 989067215 398170735 105760669 687045835 90656508 821369372 422672714 150334129 287533520 219063490 470058058 209421299 255799224 826769634 566649770 234140565 262596442 124291074 377583141 653087600 484091418 360638347 986546388 204216609 154546704 962048312 95680599 173840070 182165742 830853081 441329377 129372359 911674584 799940141 360379200 775032076 817104525 933513350 991497638 505864945 342683942 995543416 276980819 800597044 301678820 242731741 906418651 832077525 176211135 413643709 103947848 536518616 136180216 486179595 679892732 245177291 795145410 791194365 891858494 84286832 686044556 938124405 789866493 70250168 646565972 429268887 100151271 9447810 846496380 866042009 997863369 677478690 706506866 864919534 43662686 949809639 189514964 722502133 265728747 128935211 783125675 440605226 956623718 246010493 659463934 577022351 8533611 930524307 249785317 41524537 170956505 234268934 166096191 880446409 717288680 328713324 658698818 491726544 35395576 857140521 958705962 392290797 80502685 333739353 186044688 89995513 239917596 886938285 612439029 845326732 474059955 935769413 686560220 932084810 957969715 615302423 367458914 580412664 770109177 269997444 989928798 883875627 295007862 713399291 442266758 767418063 484091475 927736527 949451165 502243710 372092923 201950125 333145243 318437432 475837490 661938412 751681071 372790381 822142947 510207286 453926119 170265011 432316845 416401443 573834329 496768912 575099886 887482865 347036100 233164998 330033558 115008410 293382894 61079381 683590763 813190300 892272099 114809336 308233358 265071694 270017924 234177943 495105719 491424266 705707683 590184139 147611097 773848867 868783239 5155039 978815546 482280825 536159896 762953495 257195347 190103186 137514021 743993540 65838780 246401759 526338401 834784674 154079807 673015019 62146200 783502437 943182217 239372062 423349697 894386168 291120253 451550672 410742942 482609047 498578579 275018137 854256122 787819046 10669856 431411079 881090967 149229149 79882862 300945965 623594645 76143342 636288963 729398337 845204428 557805275 134978082 853147302 569300509 723389066 721864216 105519125 787601537 727344256 419045784 642189667 629424919 634148148 934438710 170038509 834759059 362659770 78591287 276901440 510524327 225245195 774148585 186748233 746306417 648571496 353404787 295281385 977323640 288680173 372880208 565458325 103583077 144522636 646551947 849107830 351854456 884862782 26802204 547261488 139380055 614253558 850869229 74951286 406399322 31495880 804118736 990543097 111881559 344533970 870893674 81786476 598887841 451424224 810429499 965111176 200886333 83436127 530420826 545850257 990394650 761339106 27691722 97165505 631218467 442443421 449154284 24923975 811656660 803634620 451903598 900945189 226770445 709126061 240500436 569370738 850324437 306635577 626584074 882858766 78800223 625670735 360085781 138384042 487523223 314390601 611239551 216480775 179613416 97397305 632868366 964761091 975972021 238366239 508230971 379602457 700544907 454921134 965140115 277638615 478397301 684352226 16425013 199579303 519089407 892906917 331753457 205990392 726022426 278118668 728195028 956738382 377755424 121693617 579224555 490634615 508051776 136700341 770149163 559907113 965613595 456751697 217363975 501190745 73710474 583317510 192986630 388548375 936096239 241167934 681757175 968082280 224492902 4794107 316916001 349997642 518269720 717248008 110457944 947848938 463556971 684948879 163444677 881212879 222301025 49526409 170981614 743642596 716771887 124416145 139696748 63778289 224330874 878314994 177104701 237080934 690161858 702860676 983374278 750363099 91964000 549784333 25074869 42333025 29918223 426205414 255296143 254615295 987888158 544022215 153367769 255641647 658857254 312405765 44074937 937915440 840815451 109290807 262449018 283246234 225663618 950846713 183247358 534732706 905224616 274331750 168760487 172013491 320842697 201751294 217089523 63807199 4867077 735165416 24427024 732299327 43336248 485041284 357673081 247963909 907627431 255763904 830317728 552246601 480329182 2020343 886363320 591044214 28063353 133638707 464481926 569773290 359276515 195171385 628833888 749504867 20694733 562826400 186915015 690360344 871910499 972551816 391669812 908237749 840389173 912059557 349919796 38011946 510196655 407276600 491381390 596636034 681717099 953180715 516867801 749058340 624950486 584516949 37608682 923929515 899277144 758325597 293202366 2807537 631651868 263073088 590430439 326162013 421658967 226040825 291618260 74281728 587498249 747573300 759661798 387235874 262523554 118575200 525523374 409228920 508650228 777626274 288019649 126554443 577978795 261661253 51846477 983025454 829082439 405652106 530355349 896691362 595642863 154463136 881757353 144435723 663207631 892486356 793436951 385078191 724987411 288750004 820899691 125792920 227726178 229196369 500222348 70524989 881199322 821895030 265594011 328322755 321804775 495842192 131137521 668958138 753744195 544166998 338925328 773312635 145567226 915277451 569453193 36770722 251600795 114246505 734909608 562995465 913491557 695593021 765233401 591796025 68733056 918193143 690817238 734545595 740722081 637062379 65781466 568531125 319806733 33333803 730277563 366390340 508220088 531653559 380839699 212307874 676381839 609770994 811188431 212388576 505716582 870013737 157048637 207990822 934824849 605363836 285882643 652086992 530274923 528190773 208440587 848067924 166663991 38678247 763545022 18397976 498045005 596270235 552459745 193978365 521888423 751818621 515524081 169789079 436689912 262062908 769809841 400905978 548321708 683097379 36073501 148831669 949123185 54126624 38233774 566625456 940223517 149643367 520723084 551185125 558549478 317055746 120833046 90447205 226041608 656273164 114743666 693392448 650388219 722706149 641796296 822207961 494978952 46182532 999024314 961717485 630094348 153233730 646554467 807751565 913555743 407557501 85552045 920281231 632167322 665768949 607397130 791451622 285555067 332052713 139512074 953036600 826353406 212179870 803031419 366699223 691619018 605947833 274677937 150576687 953896556 355849662 953462683 59773096 132039599 13181865 769566460 857611193 737116778 695456300 592460000 106988885 282491514 644799497 296692781 523916659 567028418 749156173 486883734 104682331 44175160 182304837 800928437 259911369 449546997 227750127 243282321 435742396 453405212 514946387 476368339 304765724 507435529 803156049 797509470 87155040 971755033 280215183 80288752 337664341 847278713 58233307 105778258 648132219 703186860 722928021 896786591 949109798 569681737 876562977 330238525 136713385 954146730 912453044 342978363 871848194 50051660 248463338 338628941 746963050 918840665 692051530 886896480 879472920 474191056 402835946 401354621 919938777 876646256 661064317 383797384 18178151 87108393 362896863 916733160 373911403 699738574 397502355 727241164 447984170 484398391 798885732 133294871 946343041 76299902 415260153 362587120 944653633 187547715 741075884 797523963 26515276 723866476 637695249 427035462 231799442 50399416 931997741 814691581 729802085 332377572 209638660 249458362 245517372 230743440 392056890 967817578 150076267 621007720 746457169 449413148 281156856 387073528 670806415 748887314 140571509 948260573 460869033 55072930 438487261 176840807 390803957 85887821 550125808 383951885 55523206 490838261 248441277 208027414 213666349 853625770 959494786 364626840 473712449 40329817 33300529 973934422 972362322 412231827 11269605 856653346 932908038 34935376 514195136 693042552 946137142 62335892 108619493 91824528 990198426 671854987 265437879 621024305 152723876 478128339 844399193 233988202 189385371 102138943 677215012 818071385 591670945 433144352 282431094 993952010 691216865 83265025 327805286 336251463 312008372 721051812 508664914 728280174 919591691 941599263 562670879 800336912 35191449 73188606 787703062 373606604 604005627 465897700 22347604 798688416 278689787 193782809 914236492 619343260 121671642 284509933 496625707 38250807 248150384 656536082 137724446 422198438 691284718 515036687 719345156 502658101 608671886 953822780 992379428 53908373 139115243 198177202 823706178 966490892 994608302 461825921 871685670 460153180 783021185 314981591 645812910 431243421 194220606 263396214 801011007 176485327 12430198 784714298 860957076 836913259 708983266 60903283 854556601 433302839 437918021 798342484 174109376 925429385 78746164 235519230 710545478 901404836 404138754 376631937 651633750 517381719 686756290 777014460 587572139 408466636 446257051 56895062 709340935 913911054 844671879 958819444 300072665 180035934 820339912 400005617 364762021 203958690 726488280 527142424 548778814 13822640 463510206 450837806 730388260 194246285 229070997 596963546 653299871 706257561 407463574 565958603 78817560 377499540 167383324 546433412 546562366 116969822 157830043 123594362 733571128 648922308 354082300 584001953 479825916 200765395 883226459 449719931 809839912 85923782 836208322 186236305 718174934 230302928 451745508 300407069 492113243 120748013 374621406 325442006 355322746 408453292 120176088 623941183 368496082 358280028 339422496 520826690 340610894 984602498 674738442 431968696 543505777 691365980 478576795 926032644 132643302 489097356 459236389 570685670 465989295 732066114 126111290 690376089 217479233 748706839 645833623 657018678 317136308 758886303 732856583 384904328 946675405 574243339 855034915 332983232 403507070 641159059 288912888 257369875 718052020 743008143 87461367 540176190 570412868 450492828 712678785 113028381 328929120 315841119 760653114 68012105 466306849 352787665 839843336 13344932 287390874 729903474 490007575 902806602 9136967 475343889 910058344 569578684 136294174 524556889 101389659 704138837 692826988 908864336 68139809 904498401 16064443 474665717 486739032 353321338 435553641 387832110 452904538 150597896 500073140 986377819 817231650 874506168 837419169 123889430 991316732 371844997 550759837 903293266 146303881 9667865 106906714 989472678 731792608 350814716 24215956 825485411 38465568 783030199 983108779 399554974 748352164 229444114 625021818 497317301 963451000 68797301 898567305 790173658 705360635 269543744 159644042 808435082 432211264 765490361 67912376 548378630 640990985 338899106 258216555 466364459 29000522 881319580 557700991 180774008 815736390 221403824 107096487 944840868 290866246 190581611 19475548 917820213 674026416 232163691 343502867 511885212 277860694 739563363 421547635 955526050 875049708 480637716 162703516 217158009 894021913 531587423 919627665 872251314 251232058 57563191 872473960 91193112 568674221 101883497 256383051 114611703 773698396 664883721 511779371 451301604 228064388 174093020 204098250 751885153 226449262 210093674 905242598 455466097 157243968 512199147 826999718 582026333 74867317 939147940 586932100 309850637 289100832 460916225 632923947 598506046 843351897 638154240 99917863 737323319 644926108 600841946 114609115 431026504 466534480 297922801 998459551 869519391 516323942 263063283 591228447 782511955 824733569 535160724 846204655 414024954 500521619 674846702 983726788 537124146 175676399 249735602 996425505 832262291 995581485 295868201 179570027 173795947 161068321 971821854 930937127 290005572 86825312 749455598 424050737 299696246 220228663 784687687 306514575 185146807 112163314 543677347 9589779 845612482 735382138 740667103 334941064 383945623 93476835 746544766 352094772 280220040 539423573 308922256 792015277 267598912 327024583 414933220 76244258 531558559 534821748 94749181 746496221 259933606 993471760 719821968 722114460 156263726 89985540 275942848 528180682 330884989 689539363 951259170 104535452 448836119 415409206 848480187 664418534 662371102 841015105 410284709 863080621 887816615 235319552 200257560 137848132 184079888 106182206 645040118 333564484 587502816 357319126 925861794 282990139 55644394 842553122 198183866 124109575 766588054 51742386 175483790 407253674 353876798 785530608 728739797 717901008 824953347 324402065 375976197 65869017 835446335 828535273 263624512 42207732 885769328 135401741 830831777 951015178 259496056 236944716 253044799 528132931 705406638 296048673 810579832 571841728 557883573 764573598 477904653 896665420 808604356 741185339 634328400 117732787 718518997 412735557 5426246 725185808 243246831 437209427 495836515 400925162 331832421 600042946 100423588 685468063 421898782 722789673 829006058 956319654 207887400 437617502 861852439 244077237 473119230 524856918 242277735 581897637 948810163 885167320 894686266 240245289 175764655 235416641 98373649 374628146 325905500 281835490 381401195 128444096 107123359 811621236 587228482 595179706 243678461 554318599 947149695 220416044 375141456 919602918 477502945 242934559 261821125 94549353 977022122 888430620 282481442 350355517 223593967 193435156 619264713 158053592 313998925 879861470 191298861 374756148 677123549 562413901 953862970 670911279 363929489 128259795 626990675 250832702 678658000 887152007 976870424 451292184 606649135 903620042 550339017 930953757 835676086 437760849 620527011 202792804 292545537 424226127 413964291 712875330 24562111 109029455 335997378 574573638 420663883 956361370 244440105 136411614 951304417 260664392 235974317 1075604 983675512 206048237 674388247 936700506 293589111 453711352 649581891 110559741 650031313 741214089 58357911 765077024 373464976 71958121 453835768 744392627 847838562 492594358 339277688 863163313 59173210 529197976 544317973 194583089 858269018 773114544 237026116 585157521 245914181 936083541 722735179 819896469 46076199 810987210 379269558 920931688 980620059 721495761 155943453 376175477 59200000 383847045 656974646 116450250 475616101 919319173 118170287 1676881 938992702 945302224 264170309 256009784 666565414 739328509 114513981 932261251 372836907 60648315 244623040 891479844 382601963 908679673 402356163 887816020 447897586 511378211 409102018 675815229 413108624 438610036 783864624 665904126 548458311 187375725 109604724 203944405 916383359 648759017 122685938 142382725 222118381 295889779 936802928 697501212 815773659 307655755 75790824 837560455 271485194 874851196 555056404 609681740 280386785 767401608 782598912 83314871 181795702 794344330 705301039 880716150 930748161 590778398 69436869 204500320 550409192 89043458 15241294 279964807 515878660 567007968 16918759 842222187 105735711 584050729 447611519 36692717 88586691 333576488 889659598 18845439 400929682 157069848 395498662 337665767 519189718 977761773 23679869 192424020 875537664 885116107 386198856 804368811 493606423 843515107 382735191 164266360 111297305 859302588 459150242 464994051 223684192 225497345 782405722 538936980 229002023 63143417 642986748 3003163 966674037 658545073 85203231 282231511 291668620 73028799 73341621 62593587 132123029 153131616 540186388 679790320 707321867 147284753 713163919 966250329 164818887 106816710 182816076 76992004 228480784 656916898 470328731 350830132 872665533 809319493 505047070 149730843 228599145 859691633 70516994 345103423 700256246 118887351 5246049 880390014 829912072 886808023 958832483 458784816 346214288 508305519 239244488 844873295 688647737 972088623 306960943 29623275 987996298 689884681 495339554 992043208 796919491 199333809 484840594 397641064 365085882 185574337 133120178 367646584 690534862 510918668 477367807 863250828 841924685 962326732 225006324 83699649 645641336 577923188 877742050 840475158 580130158 283842327 513985823 584510863 535519000 738908927 285046771 44943676 626254466 504496488 251009489 875789021 916247896 740296122 888768178 721919659 864696681 943217146 945232345 694626863 718720968 287136769 692741017 292284863 455301102 381253516 261202967 353259981 32557339 325693789 883029757 454356541 731593263 35806121 262740546 572946231 751413630 572315304 135933938 213635065 177439927 82656268 121288771 781290090 311463676 686137082 461499568 586051827 403913519 191266210 802061267 173136501 557422251 901503274 84497822 869746266 71321592 643362490 325764608 540390266 777133611 326774137 122581414 996250785 604699336 97175430 856454300 204256863 39533101 190724294 772284293 654592989 198869519 969574253 89744423 197223007 685023827 89190430 315818283 906813856 572451073 221124243 498722071 806328865 858216093 841953732 128499575 606688884 458617333 363408166 895024884 183704479 556953872 994000790 293702146 668594727 372057881 341099219 793199713 1696147 752469801 76837215 145132750 55907088 623075292 224764590 889710532 150923724 14509783 140129551 776387618 336204014 676230500 931017 971135662 78521408 975345821 592636961 282711659 205151953 19730293 667754493 640234639 668336832 248858085 397884718 811723502 765242531 979764252 819517568 211519475 565503899 584476354 123970527 688409800 42591740 26000101 16299631 799874015 660026631 626314208 516275126 900978936 897912071 650803871 774205068 599588877 133727743 365291085 779686739 394279735 991375169 223527662 908163836 288113263 793028670 234621028 855376630 924144478 165373016 887620951 834570389 725440819 202939722 843492009 61571188 487204164 104985246 808140699 474621484 181455822 784703914 964029620 112231289 119132115 278821800 661756954 245206173 156069317 668112640 589331116 177741819 855027434 430019075 179397482 885943248 683952407 586982975 648172785 556590590 946600077 940284233 17449095 968757075 365784087 620891316 925208081 756986379 553596091 445168043 26547366 991187353 183357921 466435468 300772935 404717430 740197050 558558413 668361229 350739146 386039556 637547689 218747105 408521660 115685654 350784697 367803769 110883867 438196397 42363115 588379711 974291789 696854084 165725529 142835976 502902265 879871866 877952720 146911156 713349850 466352230 634363906 367622744 651004470 421807535 534089271 853657414 358068069 755117555 99238815 732697957 253006011 424035754 419714220 126781579 706622534 325586669 754261974 673685712 93054458 229718452 141858487 60617660 801241349 517006116 926752950 896909646 690726484 754251734 732268848 477263520 983515148 645107738 996468273 623923696 285296643 100791259 460546126 772362207 499183408 788587131 590813908 710044929 549863912 283485737 945880006 146391180 244669673 901311274 47568252 527732631 229358353 921280939 598268018 604427650 510195079 92319262 844578503 716432576 652253319 110065520 474222766 908860200 781265873 422835492 524151469 211643869 193590261 13752631 972912685 216945130 625717099 19673258 482718357 78175563 734484392 162908174 149643546 58502777 757907464 260485387 473212021 247379475 526640126 633647245 247563085 632580995 463328488 446366476 232409502 298020263 565091173 329650729 682034904 223374859 918338910 388788393 245696468 855421860 112504755 965306723 239686075 230733210 37894027 188476256 472166169 253116468 688915846 778081974 203780812 494503422 709484109 113666325 323516159 126406696 821065911 9656434 42406748 716605146 425819636 965836455 330202046 250036225 598324360 902998975 181249601 637372756 223906252 570109806 659432691 570875116 4231548 493540355 364810861 832646990 608812955 928595237 634269356 253098396 122284051 648149267 62576604 89118194 88958679 428161717 416255163 538007490 266097500 129407789 712846224 422550959 273559177 935718472 687608944 379697742 587490077 462024018 641172567 12734235 826264963 174968573 797319504 566088502 731165340 556473035 39206082 815836129 94904931 822768034 448207573 770928570 671896573 320614619 897563577 578136618 901241529 68432468 695520664 453833355 503200296 279208702 186764735 577361173 151032591 230590147 196123025 242808225 25247142 534128920 192156961 614052580 653304616 809071257 662442043 652817625 369108452 210775278 536385151 316554259 247241591 991559457 616527741 514605441 216808379 300266103 562019282 862153808 514091946 693268227 59958313 226398166 889669305 47923302 861884701 361253971 283667105 434977602 80137147 788786085 274641783 340390250 587779544 114694523 675148631 172084763 175960653 663409378 334454448 565153409 215565 999644025 179267307 988367746 980012019 697325345 715212627 335832937 559716413 64070881 835630985 379408778 935119901 417832501 701873701 241036231 64409265 645431456 276687624 99494458 352966736 884510652 249747151 103502235 132017096 893456444 250348030 881071443 401568702 574871358 81750008 248966487 315123544 784251551 917767224 124670033 424368971 598943427 637614579 414171289 496852051 487955773 849580992 894743709 413133273 362308292 486648280 493870123 654761131 744366159 977528977 522934294 912785045 573326238 170377157 14923560 418315452 975238679 504146053 736280404 329440405 482763159 25941389 791926346 667347480 845545953 5512730 895265351 207582120 600954839 443100477 76367611 610214545 976535603 655380005 111743203 739743730 244205415 429551342 457676151 17032026 16933257 967198316 282311066 189157569 656804082 296537961 167527922 750484104 517724361 623730582 924077376 364041441 797021833 313368060 872338374 327213570 140975110 26349773 601290253 951128260 494732077 277806754 416275722 479551734 471372186 137172269 44884943 848503131 906853118 587340489 12888110 266402315 489785696 422981978 27418416 53734589 368649757 620617658 969830434 790979672 330784873 753249616 743590864 22117553 514087140 290418973 711471001 912274419 6669392 522652066 892389655 774426068 57990390 249010356 336483045 673803205 158920944 698920196 76053288 567464804 567724332 671337053 535908698 781627768 324530206 707127620 592211192 720059247 121012147 32973095 752495904 628073338 988071034 248084179 285585556 985757861 481015900 203743259 818007564 974576111 479286873 190326999 984770938 929482086 93727166 39088176 660561893 240484829 255021860 635353927 240331815 185580344 197020063 599062010 839220501 864030713 543157023 660976338 824912380 120313863 963242288 400234448 496563240 825427392 367518309 323513358 164323186 249111201 989213594 82307946 462239374 235699706 84275505 501417846 704325260 949204495 137218988 788726667 771523383 787641862 32475530 691147440 121195208 758441518 2067042 656723462 359413023 239206390 960478888 124586299 421789279 311233776 225427165 845351408 237272470 621891638 286845175 846322960 112890373 323555658 208684154 972053904 331668927 224705985 432061442 961231279 963685080 56817286 755505586 134267491 287890198 515335949 267879579 294779707 33812710 956802184 626491517 329301476 515854753 227950149 41216410 403037818 73082370 634794028 309872129 988371838 650738693 54066839 238306057 562812622 771369265 564991585 896073309 252405762 137213065 270704009 505072972 447941595 871586919 230689932 409369887 805183215 324875385 297797066 207195026 368232496 405283649 181787693 241685219 126752208 641947611 819549771 155996770 934700782 471348711 317678107 60986603 945288387 288168325 872254174 308759530 219235155 440255788 866061341 647891602 254012390 148576532 342684904 249807454 185652647 108278484 261873967 105079170 838539585 746240103 888361851 629835399 603372122 32169143 547907453 315735925 242666716 463332770 973818121 436787002 407984712 870988364 122020816 2971228 135279276 758488922 221710495 709534498 676308152 141266192 651201751 68553560 887060085 486149481 819565385 670394703 62017571 619622068 182134930 139985969 518148825 522416652 428543510 199790145 635754541 264928825 108394899 471929498 963386070 978787408 200805983 233769469 112300457 441253065 908615958 32001547 105511443 280801623 917648326 129779433 384213690 849072100 147488661 107234053 428919895 860044266 772563968 973261775 416393815 634098842 434837579 341707627 145448279 202111092 154905198 38858651 150615993 822096044 611765664 301485005 121196596 112576001 891241895 378494326 799258648 544832938 849212990 691109640 510338469 949729041 598518845 139991797 425836538 373646173 937844043 17219820 746295478 330326887 908114973 914516635 861327569 448126308 673939453 383193064 657353636 895558119 721511494 647463743 423945442 489570024 685573062 895160331 122724893 927146094 61777416 783492534 147147957 900987936 580351852 321527107 764076518 450837438 602118830 190212690 217862674 653847371 882263345 312444741 453788412 53002326 661476042 657728770 110101672 976784159 115135655 67779691 848341457 862610338 104165237 134988006 343822745 137854845 9606064 267315863 752527350 707892832 731965704 208340370 591873203 621531720 852085094 515329427 41126159 651233049 550021695 155780059 3303038 128170643 82376157 722846419 291362160 861766656 22466586 276250307 385117623 690885770 848482858 704789337 620463646 869735727 277787806 999740229 262123696 181918144 699997444 208424400 505717658 876985652 557096559 298243459 275183218 643972577 295774153 509571122 222200155 450343681 146664943 270546015 508711155 976459302 343741539 473852890 262391910 533129092 22854850 919637821 635017502 3306808 12639721 222055170 1447560 928559989 96306048 595812986 417330402 314609795 835986357 441308979 917151208 871560431 534025256 161481556 213930793 582505661 119903361 406957675 505860888 165927822 529580013 582699577 563228739 413623417 485791684 559994083 353044340 920924769 953831508 70283201 603539893 101824554 223441119 257879281 122786910 350632664 80934153 46869580 616733431 60338314 483927768 307132341 58681168 773229776 411473991 277937959 91070506 140160881 531288388 761414989 170155692 870289278 117692167 653950314 477034529 979861865 121556431 221090866 75175296 980592132 47333519 360645387 315545694 718725631 122490382 52559610 312625091 296587233 490915724 353415441 281175692 568345551 332445611 298606942 224014496 197160619 7108820 162161224 929876096 870205607 219482738 935815689 545965464 96939077 910725118 729462142 328273532 127555626 383127355 966312012 619951168 108682619 254809250 66695052 346748395 594352919 175328793 898620628 142583242 69412047 226907384 769564822 408741798 175982845 433419941 49955445 113778042 415924389 202613403 561849819 812813167 898612844 155232394 696759322 442614284 307652450 750454407 897730336 118789956 52866489 87559047 570419557 865542210 570817401 478851250 737093728 417736319 120979780 839052855 24836995 212952739 22397619 503754708 109256836 270778378 384502958 361401031 263210449 18986899 35020864 923276505 595071885 216349631 886331220 137433870 126566572 24177155 711100475 731315286 564243310 782260611 241335720 535924227 214392103 887690767 90333391 616591212 989395776 499711864 699244716 348330910 331868240 121205496 775779395 765232720 357956243 320049109 910108906 118431024 753311969 207084546 442546633 787786196 227073460 317058064 212179429 349406795 932762223 193580519 355457294 317944844 60795245 790520258 473749388 231277779 695171434 589547118 12821056 377179383 642910934 260565068 869702253 705084761 275181111 500315814 293401806 136831937 179614429 148250498 423752950 455109502 279271884 936790226 79990907 118931412 979985195 844161465 587492817 780278041 537526494 481787347 42668516 251714959 621291737 496822715 708597719 46487571 742315492 294878657 743153897 82160665 708005628 896537788 18514561 805637793 710189457 310126051 918691460 890968025 509569721 112826462 889865337 395040986 611183499 979660446 297232408 293843284 322863106 978985806 798075856 244715632 73603554 813458374 724838368 304105809 217161082 268013967 540628764 563515062 39498468 279740072 583952762 74467966 653940392 898591670 558030243 856268923 413386939 889903663 28221101 721987337 156518059 117800626 843301199 68092801 572122690 144118461 615079373 464032228 345724935 822072109 336738718 682080755 105937225 500400576 689600317 237067944 163899849 828056045 980087267 415849429 551121106 211942535 56897217 3575712 440731824 338003667 940637382 5663045 1 583648189 107383279 642050425 444131778 514119986 202907546 638486762 81812082 776697133 976599333 704887945 579280181 294961687 725660432 238149691 639626883 6977257 297519324 693932072 981318161 504970269 32951139 557494943 718251777 331582589 70988474 312946733 356936606 611609786 695934593 28759000 77820036 111265669 655578257 211537419 153205041 79543892 49095111 647315796 701028797 182356544 447537555 125474236 455403533 556115529 624949746 102769795 356470288 250211415 156284306 200927568 470467680 147244833 191123441 23155615 68770222 775342900 224321691 768123011 257088861 992988743 46477412 373345541 156467557 541517224 603020206 827522735 466118419 267133566 733201489 163310208 569803188 379295111 734580262 521905840 179794298 289183622 502920936 188371205 951310826 456932792 124583615 192038974 129881071 89495501 667818913 197169643 954674281 873254237 537423369 258279759 905356211 678113873 285753001 556209192 505362171 737701469 299654434 501290840 692701596 968519715 128070869 824723242 150461504 942948670 590006772 401472334 893051350 308034307 497516241 473859489 93217050 341344122 662175905 246592461 412077428 734106880 445224985 318944101 305966874 251068753 688057268 133720830 819055969 860665068 294667583 288029408 470556481 99374297 837660006 973218277 149178906 646130824 703928606 853353089 35281421 535877120 677627449 637414949 830597191 473565820 286405792 402893833 419966064 295467109 737179646 594829549 544340606 618831735 707566369 24675443 912053610 259891146 245821809 487291754 660945901 556600750 791118632 946157981 852767412 135831714 573258513 925564650 655556929 258526577 622348568 501577002 107375482 656345918 705800959 990070677 774474709 264295746 793242180 614567352 20992154 326457013 794767173 194174777 483582937 300663789 498830611 997917567 463200891 334029956 599847817 690447665 286956512 866572779 672100202 476290966 642557029 268707709 269219797 399453137 204153842 982656602 658036815 814268532 852659371 603038971 293719252 296880201 927994456 194663657 238467553 58133753 710373965 55937020 851557207 439721250 869033515 912885598 306135705 467163159 670400821 20471597 871056383 264168147 784743982 618826280 688039419 572089525 15662215 349830755 377243225 686623675 816897158 616925697 832651248 69186282 612210622 67277588 303078284 179129868 298376656 363438901 270773397 709405630 287115601 244533648 611045719 659011779 465469759 947731234 285570770 676861666 911311447 792286280 940505432 235391081 247755755 283233499 772208488 119312070 432514375 722378669 48183193 499708526 49912437 594685624 841192739 840828652 961267372 933588972 219827312 807199509 113130418 108372983 19437325 293175926 173973242 374627930 13152352 617939907 806937289 61370317 615306814 293079712 262868733 326339489 176137069 701531819 555876794 813522066 283449356 705829899 931481435 589064846 880210116 877497926 466822522 161336207 691716615 719226480 750405924 264903654 70444570 147351469 788448802 606319584 789105777 566600021 469946371 521987686 573337485 217174755 983871525 605529244 662107606 788193474 23838924 66216233 402932424 25574257 458067681 932815332 796936055 980270522 900525015 638286647 289858584 79733459 964269744 220198812 937691400 813979085 283356321 580884708 631695372 532622822 190219576 803687461 913359738 559774961 285642925 16685523 498055101 399951598 304487654 301057781 891030671 464949327 49480920 176340113 685944244 27614044 83293552 69891516 156276438 562038105 512823371 946128715 851223118 552084371 828753780 247508759 521624578 154267810 956515917 620225280 530901734 461320187 250739789 387130598 90575876 963416875 357768994 879181486 235918992 323964177 791922900 5166703 393074433 906581656 806239161 662502400 821081520 495060624 599287589 635953863 899193018 394560480 145548931 714230446 171984828 597536529 125434704 699622598 378139981 251180389 709409836 379109535 57182826 234174750 475813264 249249281 696098309 47900536 366619605 709637413 402895358 920172569 217190568 136534520 916674174 83783570 203674351 521205444 959979952 43131288 38588994 190814715 193339502 976885440 811334763 932564354 957788730 156133519 40631797 474502611 1556470 728747442 102092644 299109289 363524201 222865574 714420127 357740218 454710108 821479755 528497914 567767906 721785239 911707743 243238521 842505340 252818835 740901068 365769210 24292443 885738610 925450360 709513421 692831261 238058797 201748263 165936282 659910690 437975617 122039035 407435975 468203526 520605472 220206646 503451018 825997767 329299393 268189370 430486939 379729085 526245966 833187125 97406808 103567642 878168934 61613825 818587662 149418531 409902974 525232679 773408980 820157785 809387005 628514242 798497987 851473515 53207245 650738660 753828422 44954445 577749731 398847930 540816316 449202900 268078541 109164027 38753019 429728265 269990946 762932782 635974727 513989252 544898889 321896714 935521822 803835624 689068904 92219480 176957568 42183386 754095725 733546717 351030244 466889788 118642238 125079854 294359814 861200664 3263076 482597296 633062960 81184870 910640055 412316874 356335705 727426985 196369551 608027442 493666070 125372562 164525904 78121846 195700898 580272035 930922068 912519404 810807214 206322521 501451148 741054106 835225825 541723389 147754918 284937120 571338234 533858487 405339264 441710463 241324600 701738346 275999998 946345372 286891506 650372743 291779981 70590726 498285315 67202816 60704389 894594239 429172523 379040292 848704739 722567540 504319015 653582726 651469376 506099457 413229506 788165794 7118059 451033068 80008053 458837868 17912553 853341761 258175047 762546250 202874614 81310694 141059745 929833277 383457858 937230657 847360111 911607157 212596693 205141220 396869483 174267023 402326421 341958810 869401329 323924151 840404293 822692066 994014771 976165896 576571969 321386339 130287133 248865094 588767929 123311284 905044918 579266630 286345999 708679802 957436351 840712256 748836487 86867490 106854665 584085939 725162841 72916584 979987294 936661270 829704543 743072124 925937118 626062813 534248015 6279165 349408961 549981581 656688279 675623518 248274597 443239538 136681495 108864110 44319681 78185441 37859554 471696774 471021566 50833819 849192784 138821802 682453282 435815342 138516703 644111708 699981505 752347646 713742550 644695808 40964893 518703263 606731384 726398807 688145494 839191134 420904026 178122246 273294845 798690637 260394827 359482573 63084270 383229526 372090258 501871926 805087726 189361488 953549198 87327699 172935114 426239140 773656429 88468376 90653637 281728930 722498321 604151888 882449366 921694270 501104615 996032705 3441173 837331406 858814380 137261940 977376643 557764549 309893345 899619908 986350018 993566992 203430752 864504849 617317185 836419114 953623533 108516281 859095645 181456650 619545704 204743259 625452410 412834068 285308100 898472614 882418772 870288922 387311796 196102891 444414324 342845932 78753035 342519251 841903063 249816747 420445407 949630359 108636422 784474888 835763322 872291696 450206396 299249311 830257869 797377428 158446918 862676463 249258785 981025582 986561874 792229270 480280969 866556859 561082587 579916657 794789579 269663837 203510866 70475946 623651439 700230598 980959285 499398933 571475214 956764726 873832315 774356769 961329438 241940301 992931571 870413518 155798708 822937783 792680461 156590939 197496406 255678551 755739520 607554299 27451476 787498757 736634100 405632594 642443992 359985984 854457259 151979797 509612387 588824299 510196335 894220630 197375519 953450183 798147851 399937164 235155855 709422157 988194491 63102817 457953347 67861028 102229775 162853482 289350259 746826378 856703491 510548259 167195769 615842323 712079445 81906835 160687795 496184361 803414226 799090960 261969000 488525639 369476982 684329328 266782514 23005583 830437157 737312591 477464064 103800575 496800478 476139102 924809249 480587651 984759275 136839859 521039877 551686184 364589364 955734751 23582092 776351435 738346148 748074645 784820236 752909483 138863105 380241520 35699916 13193979 665751569 573572155 200084342 87957879 108087338 524848574 67536173 100951928 461685473 313799262 254931295 542871694 479449779 42282346 618499135 465813689 596642109 409181507 402263732 620332405 957633035 462915011 638763738 347108003 162097939 195237377 100655582 722337530 128523937 315795190 632292285 618120131 323682049 243836647 932899698 823757189 30936393 574983946 585610267 115578332 119933443 384705125 786252812 595639139 210883740 240691724 712085171 845292272 867643097 269936558 204664866 923716425 147711275 580979988 629965474 322040389 435100324 977404764 559812220 379209793 199637951 67194788 214507943 896288168 959737399 666152488 576235518 254130479 21183779 184841489 78234337 88222803 165276136 928509723 834154949 716958342 569501957 394625549 708798277 525807433 61005175 384747848 504547627 691245998 400993518 64470938 996008935 494433417