11 1000
103152401 861116386 397084961 310812693 944438067 273599970 69258854 828852571 665135734 416752401 104886721 940403350 971399618 555779096 569806629 978465280 111881391 169048508 231721082 527183955 748413068 495437457 699019407 937947314 180694734 168876287 198095039 388629172 34942675 683620973 201003333 506325595 504679695 183767566 590332071 835553681 21675533 685584284 597832670 827541902 572262403 476187592 87365591 931442102 199255760 371130187 790182411 602680883 203253132 542796552 569751677 527391192 968986022 379022710 338626780 180464694 166077037 727476387 677858404 571882621 58995857 499332918 302225153 443974541 942236526 838809545 216469321 180210159 570944579 542098361 382257936 134210483 748800264 111504658 458224556 89609132 912664832 960835908 230901196 186509146 777204094 488039324 260067973 913481647 710575929 854334277 50387912 416771741 294816080 241138692 782432694 92752534 616435813 601704857 30778030 421780992 200022024 756907283 58159255 944049410 929362653 469340722 768203420 455036720 194212770 852747038 394578871 140525819 292849200 941256367 558492620 785670998 140460939 759636016 865025853 270344410 765837868 23653334 47934442 850836750 974446434 893974574 879388995 388911346 8018709 356972040 872937449 147373046 862956388 65218014 281515974 415145629 435722500 175572485 967809310 482370774 330473905 841195053 813958363 574447437 755195101 207383524 445132454 451020218 244308443 431956640 360061691 732797340 305492985 764317872 943906767 271276950 405253464 64434876 886557443 216786878 728425531 189125289 618559547 813041521 675695622 557037987 992718362 303910831 205698781 832764596 691820870 146110048 673466366 791724856 97219974 326922511 231664354 318968340 434109190 831990298 232045630 480880638 540279661 233670140 407296098 936024972 215632260 833990324 158392810 20037099 871136054 14910762 391386036 526817556 673126892 803020190 776307075 426914097 730709206 753796864 738749601 144150129 946820037 221005991 549050956 316843935 914879828 956453013 76324384 62199694 320048350 944133084 636562118 656693788 967075766 901870712 858023433 815586560 338293289 650171636 481155225 88988337 156233954 159447420 831289883 274961359 776594246 666488853 435802096 841123665 433172377 185098793 128545759 776136107 934396958 577233844 195243326 601882390 572145474 922092221 241723879 194329237 121138182 477847725 728584386 689357079 474656946 982419058 994930391 146504573 586759203 151167018 919819238 911130658 675775673 593537261 171059380 697585144 83455746 330716702 778627804 41004131 936865388 180227556 725895895 837227431 496417627 321523824 189130917 366133560 460564516 968385321 290263609 862108394 732125382 11902295 338940291 448621726 92766037 97843475 203726120 76119387 308141367 286077745 365278597 970428735 745629976 344397137 323095024 572374427 895015626 705839260 957295596 695888207 579873521 298023438 104346334 279984944 505320619 456227793 585090636 423005761 955971768 372298055 563147390 595525644 606463210 198666260 9910109 272400985 943508820 258508520 296172198 571985563 607688518 229031730 756761731 259128899 529956430 455489796 27218470 432735658 436154456 387325571 541752895 83209003 571813047 320418081 659555809 868498408 903122615 379828964 835584841 887283932 312296828 67830778 539575554 924225841 993029366 473840560 371664357 769000841 869561992 703842736 423915453 9730507 768387543 922939360 996361331 964456597 983487366 667151713 918823802 99674931 61313734 608756237 188513759 800036202 913634518 477573245 62185243 816602605 257651932 533749101 153246032 880566169 959009473 182929792 809741149 542445161 230159900 16404110 197287874 802432366 974339804 959826127 15669033 774352268 540501577 426749280 246213777 181749478 591279189 162394840 706658808 294855108 323017156 124622576 82218192 745347668 661471711 519625417 308854499 339947571 780469496 240046231 620050737 187112 58051501 398098400 504979620 558421567 875715262 762010900 829221934 297168059 479079396 651955686 736361090 98693510 705212577 637621474 674021527 76951014 926356698 670599171 122967517 735090981 692677709 75734714 273742152 924621368 140546626 389920853 411472314 363546540 118385626 976260615 496767498 327059553 430742566 685473716 820290446 545422520 467143727 891933923 809090585 276600397 162047689 579531118 47881052 763354254 725560134 116030832 507652469 393378573 421079738 556087230 712963414 88728767 948544220 45250775 738319225 269665484 659302394 950987023 495013851 639821793 121448895 126824519 79230846 733111513 47035188 131194494 318841908 836084085 352091975 350902226 425324310 373715434 769348368 257537149 531958283 825205519 137037039 842891440 119121980 164843491 647320853 169454534 14952072 636249026 735906446 437777937 372704126 655288322 999560457 772976084 577127275 9066915 865159104 522114901 799934614 583006456 361500120 327122185 726695181 317443818 938510427 1293257 288460617 500989644 257991698 884569378 194320491 929469885 897758129 709841701 135684752 255379844 405117768 427746102 458284952 830287075 494586170 804763019 896254785 926994335 293155951 526761987 845287209 524556956 555669852 680108840 878017208 469768219 338891201 929066404 231775854 489042641 252902521 93026497 192656851 307404834 36137048 385832624 248044154 265350466 630533695 643213660 571479835 516868895 80068313 989621117 429977786 378011646 919661969 556860306 200881965 295152167 147957309 111896657 135332852 959986220 835293712 283991660 495395591 815532086 234597740 620806618 839239242 218059108 646552896 759404493 968289842 432067609 346454499 153903953 379072513 809264701 19418066 517039489 143532123 910189913 37778429 43547493 285866908 450635253 532990524 202466276 109498017 674356176 320590099 953983345 477636387 469282232 138351931 1535733 426293395 357450061 652814684 541581032 813801384 814671731 167446039 241709118 797473587 833048548 686463661 395765767 921450745 887600099 142601331 785574542 258155056 285825759 280903294 931435980 40724555 59407434 59515284 850596377 839888209 545363876 709047352 24033665 941357644 757279741 273607633 703470918 951937290 258433911 74640508 388424827 824743135 706372267 781411824 266774306 426507664 318890293 959299158 94968289 433585623 475242723 756543691 43814138 782893121 458826081 220228592 31797031 487246346 747388420 986578004 434473706 135011318 804621433 352686893 267151567 311912891 151079271 70196014 545841355 207283812 671476089 756210865 790585023 442497746 163761733 920546018 172867692 11746808 877946962 531159088 264693469 687555090 405023807 743780754 378011365 242562298 233590751 288124183 243765225 763815077 497703786 457220220 390379531 943633266 249335618 973845865 314108257 552143711 936575839 78923582 50840873 707405104 749573154 300875240 247606470 228245295 806540154 859920970 485322373 178865809 253546892 48966306 48757835 604644908 898885783 143858391 562131637 57622115 150154612 11136963 661747488 478323217 136051676 274547424 479921835 747464996 204504190 93687158 350426690 704006448 861197559 330450323 598563116 357019727 923552814 78097222 890144825 381981709 529049816 649316155 402052748 198771055 133320708 666540740 221310930 635874661 229848236 170951816 300663841 316602250 614019347 668028926 219265907 272566708 448172552 980177100 323070980 712965122 246274414 23332212 118213580 548515051 566320924 114419236 913284628 649111975 318144740 261260404 742871759 10275676 789943257 206167367 160998896 181715274 33131711 762064809 577783364 55605289 989889192 60008470 414283312 921880977 259624609 189603026 573848861 954184168 841906788 478418019 68002577 339740365 15119672 910193343 52007183 63077924 20063350 610161073 501217243 778039080 989776339 393087960 395845071 597645064 354288058 992142418 468590669 855544459 7011575 928357119 121046823 909149317 215626428 434319642 305156141 805543429 79943337 965066273 27625966 532531426 362791984 929533179 477713465 8876603 761548148 280150900 180471907 616425574 594768666 361393753 238667615 291368690 86219601 897285271 653659555 45260190 139340981 349071347 124796186 324189449 198508689 299285008 199181075 466139334 524434311 481195919 205380978 662200318 649042412 665236169 109278274 261062270 305249161 464648508 867358623 148569573 810922867 433010109 977408134 686802290 274859157 705964423 927673301 891899820 780483409 40637844 987875251 433607836 432386425 984649480 325269261 534059097 82746365 489994104 730423043 501928235 457001538 449430663 619517696 87281438 554212639 316164643 649501406 574920918 227275662 664501572 53894441 600111354 215259201 571113305 303717020 985739394 250754376 799109993 661530940 984110044 510301219 251111518 161636127 643639947 740911256 123959101 877880483 730274896 728694582 731872590 400361407 562034378 693246148 615839468 336169474 757642458 189085278 797368171 494791497 88679767 876398650 556762933 577046014 366736833 474467240 591745390 437504713 79673286 151423972 594261391 73469175 635094700 512108802 354807553 254623796 460099345 114833109 634609621 669465990 348672243 746784415 193183471 692583969 858171591 453539167 184819830 266923493 731989290 910430894 284055361 731798364 173227725 947656075 245631371 442702586 318434783 742962178 381234704 407589777 160081876 113277438 865454121 18109164 649777662 366574425 545568294 667132941 104327063 733625114 253195675 10451422 906398371 88468882 581774632 28061549 75648409 41485177 48064995 789397652 864897330 22356212 485011114 724294246 330125096 357299424 948033393 338496857 738543442 722624040 329274924 49485432 331097666 535498310 869506981 678278478 898079528 700652884 637072438 158451193 721033074 73864677 695348454 317783788 630349992 255603447 286632310 262705329 998508028 868972752 942079682 572062917 684964660 251535424 683225833 391856857 965811549 808241327 405940854 286857775 335630379 588289277 944161614 307371810 585277776 742934226 824732844 686858218 
393969275 866318111 231351491 942194258 334848602 880403265 907741532 402970417 461005632 215691036 114308123 422057407 234112050 158606900 605288916 704648273 21135963 475817743 208984032 36209672 154657612 184343284 937400274 286070845 8577815 941578838 175753772 883048933 769274609 580791019 500177270 447268568 549924738 281950468 974178542 182984308 529228545 537773876 521373792 608474940 577235403 34764197 510142478 189079649 688196755 725300799 791230699 704498584 374048474 25011491 641278657 826156794 291939309 224693133 735304683 888545815 204464025 720632399 474005417 912975466 981453602 996406369 146118053 655671419 649492115 122595296 748964752 311783184 664039490 231525651 862112407 342256921 466125332 380019135 633897058 514843982 594412097 562723077 542650520 265813230 695793590 524127323 433450782 729728094 707001211 487042341 157397771 658923713 81191893 956359902 374407883 331961082 504805152 696792481 796928013 113921120 176438823 823275222 810711177 837106422 980374361 114239369 274237134 178109321 380435196 986334321 953312527 737704450 230286849 742116592 605466299 67791847 630024557 961289985 240274918 783854946 318720388 122356236 184239585 407058688 765648206 970015805 662238757 447006069 910957336 443782120 448064210 829380772 229021931 541551889 504100984 375113677 980749033 476075942 653280253 169040561 614869493 130495324 100574329 625426194 408124506 383565954 21980335 793520569 712548255 251983772 892070411 828020075 393101769 625836417 587106800 526048745 944083741 408416772 534144961 1689811 333935637 924099911 289435146 767312067 30001945 143068240 801328151 860959853 950191630 343434818 976914361 698767188 554793468 105990310 705782794 966112405 67266167 514484303 992361936 355175714 806240324 671016903 37719132 990834397 103086897 877435783 146334041 144545851 467987905 320608930 873057361 450180679 372218521 994169258 850407055 544472997 157903928 874187618 97992859 334959908 958228368 866138850 652832896 583577879 214270302 179431612 484068763 869730749 53164390 417541069 465874130 431423004 860607910 127347271 942234760 219742017 734620429 740494120 461002768 135112122 294501552 880107055 110810851 911070134 545640673 833215061 306780311 397956086 356401467 159974426 141644047 421315400 372582120 489033697 143379737 186813002 638043015 957431282 72552045 917646302 990925543 38628075 94823767 183449866 845619815 262015077 243597340 406014380 203382609 276940324 446825944 108115560 311537798 847839367 947514682 475990902 528534221 222237992 309275120 175711380 75958466 499544886 412540882 508227627 983136765 996590894 952362548 741523718 856868384 104551854 777708602 390997214 180191671 461424978 755057498 567551928 829389012 546248315 236384663 948720933 871927599 209808211 119646535 416237108 118306425 255104676 649332150 167832350 273919981 594802909 406700971 824503557 152025333 322710707 764608245 649755073 944238657 981222189 140630947 406568195 636493923 850181296 698906412 869814044 444496205 350325380 494682231 143941962 755634029 430002057 886002000 841482450 154924006 267368729 315503102 379250938 807432348 773773016 425737750 321607563 504199543 952163956 854366084 902828086 702258614 265533454 403183034 440458801 616350176 679391063 84251031 403155739 718270187 706778376 240931041 218083752 364179009 657534691 17325442 810797933 796793332 178767094 405147000 271472541 880737232 470769823 479398533 118467112 755847729 253650488 699396623 237642360 473156004 379569705 953135638 183868872 73293230 629212261 557496240 833309360 51452212 691416844 757378032 515395055 313007262 567095924 584607635 430685676 344878711 107084619 164048412 58548734 183591529 258281167 995537843 900783360 647046458 641261714 179366687 339391365 388210378 87854818 523818067 555597069 129973895 190613304 929514958 615091545 856178723 598060894 612675225 860082718 694379935 989488695 297211195 857075574 480574275 627025836 642324620 88221730 478875473 683048784 986241858 455132445 974135347 491882531 608697781 780568036 489346227 453678518 711561925 266395151 314034043 129725205 483568416 5099916 726502897 873062561 635684035 520079691 613710587 245667383 783907870 293280672 454452767 645347436 462867409 323387065 615789169 391368575 909373931 412740439 374704128 988895167 6572342 115049772 167577285 397047865 874043995 193957140 208963003 890477281 15749315 133254275 382831524 698142447 764863773 696497061 914781577 289973756 400438548 243769751 635393363 819387235 194703406 394719331 457744372 262998888 418374029 535444125 906135556 393664375 768429219 444450130 62966055 583768186 375744536 443641518 955746005 183388815 500392024 514383536 812702545 933155362 990770806 895324068 990081859 775139927 182581444 959564736 359526732 358750726 476889810 357408376 808579186 343708477 289099903 474791868 604898513 513058077 87029658 836471535 325339347 332023567 970476716 925056682 909277953 796779327 191312051 492182340 673154227 369427483 7132656 287484066 141016880 197263345 681286441 820503570 692139039 324237318 504755684 367329345 522917418 230976963 245963375 977972329 116772982 961255552 72113954 866596193 860362587 507755759 637793187 648551462 990224141 276950895 119237797 987973390 307542074 261583643 286305763 382803751 445623257 256397233 223633831 723877870 917759567 758163772 462129739 878358674 331220187 571638425 498171808 734426789 223156811 988214897 859185034 905793996 403709648 929923339 833365348 269180956 290085002 751537239 318322658 245084672 487615233 542464201 598045332 735810784 156176799 28704585 73943228 797084048 623432317 125446041 964073343 814417093 496693216 653926945 799191459 7150786 408807909 433348496 46277094 505607269 223893720 5846709 279980025 926406767 886578690 146152346 814132122 647648425 156700843 905466278 379833092 601698677 890197671 898309370 356525939 471321017 178938458 961158416 971040885 854567550 742766640 873853930 697608424 200984099 164498327 32819465 336885983 108685193 166425755 360194169 200272230 977213423 219555456 741605096 128289457 773030093 61560812 129157254 803287405 583579117 358903114 361320165 238307090 880109938 703698899 346484608 270314746 905892028 365721845 199017580 569394794 274645223 945049181 680116608 68442313 375342037 361061803 753879490 21838362 964463051 692879153 567780606 253387413 117217920 567160131 683184288 265723591 613873959 176315410 129583731 532314960 996286212 958276928 356657556 716640211 160242157 984520181 512842379 704512123 240514149 280602290 149390439 856886197 704896087 769186174 14847218 16294407 516256871 409410349 676716575 301053852 572403339 681021958 774113935 416200989 59976783 252490151 311292877 703141987 844184687 781007825 404583902 797977332 192619456 238716794 340219088 26001719 182484437 732942487 975386922 471704530 776468832 156559669 205589057 347710063 877685335 83097559 340135053 508482197 815254654 837086226 615681851 421970144 37831849 746801079 632019631 356375105 894328076 930497836 532050052 138106812 555047140 984898818 299319706 325258178 835365724 955882733 561338876 236691287 969454146 166462109 393542806 197234587 69298109 852077057 478460340 458670426 173116696 355291674 628003397 339231525 229475407 241268520 767067276 874045022 432279681 482897272 842610697 384993713 915544330 137527099 791693995 86413731 679681128 33933495 485787817 578179126 836714038 276188374 740399919 227870996 992881762 929904900 229422884 914007691 938748267 697716493 398304746 541493790 473822301 45059773 492088147 580939841 249565258 506360949 59697837 77301004 404569898 308184917 134768226 827805689 4192927 195316652 548172079 749115245 461627347 857233505 645720136 997342795 542154576 741686681 31375581 390051270 796500758 24402999 25875335 334693884 715229328 265820417 782625829 935854546 443376618 422369446 71517690 93850794 860586442 700667212 510263654 851099893 642959811 203152927 235361228 490197286 610134145 256984071 504945512 955592732 141289072 795612604 73474061 953570981 909266973 128884397 794859333 114417402 14648971 839379784 458086343 935034475 986242089 60345325 236990292 353643232 491941394 876501322 661325670 73567095 862785214 681074733 994275305 870581357 662562895 941972366 518617702 825116397 495200279 894124095 502034342 724336089 373169486 178089064 303125684 639687001 535055551 857132310 558774394 956990241 419907587 951141866 201366254 4701155 702248886 624665446 92547110 166098195 830668819 273064565 761370560 232882128 846478829 907079616 998448000 508641455 802890955 230120471 853604084 599048904 30488019 727472412 71378162 828906653 916660116 991805271 763098377 153826258 216496277 90585725 822269014 552395899 517064753 447370772 548152358 56104120 741166119 317333636 704319596 472820820 798616900 299589410 648853555 798804817 525440967 360995774 276291938 764334208 194359126 345867773 603817765 534703474 377158630 525525233 620202853 720389511 839996688 832749753 422186514 194547933 371164469 752319093 479834499 159953607 948709350 644926826 336112024 201588914 992594114 790582839 284765705 975903083 167538161 401635368 465175344 418545709 411493046 466881040 578275875 745222346 117260062 24623590 247548173 676189609 769546693 462212201 403265784 35274569 979612054 354277860 520283723 250662538 118896997 916789779 217573050 546951925 842224118 590665100 301345570 800628463 213500066 333932983 736203682 598031368 244947386 936500576 346198790 175146102 933787803 583935850 82952930 153291630 732989933 419674531 346636790 289925848 85377981 886613008 617448649 901632600 958769775 333953930 491050325 826341097 83357403 538226566 57154119 885884536 91479466 350537255 10069216 23615079 247905547 507246378 19601594 652526640 136812120 58511744 587049531 817390881 114523672 632347871 274754276 394743431 178457050 569136839 224044232 995072723 28566871 240589894 424604752 238801812 199541425 78866767 513195857 186143714 774541766 897332617 497569465 813611316 753759829 
241899935 646066629 312226507 581858348 358535293 772247029 966585993 912414575 385217764 387764054 394180036 502698596 620188874 842161006 150603456 720861926 782810259 42581063 202559733 302101322 467300666 994780264 86223803 159474370 567259131 475697746 374443829 554205587 942149312 543273932 821649762 3048800 111064431 905020553 123659102 872111521 965507104 400367375 935038884 715790161 144575732 306353990 530631554 583073189 435703076 770235641 241790066 829667846 265527984 401019816 57595976 447527171 835750963 887618630 804454929 181449370 981540649 475980110 374001772 132207838 137667570 759421440 341242347 66603505 509221651 776630688 495871289 168280500 777563120 807859265 526682266 182264252 336447661 963455168 192985987 903722713 179724161 728867477 452039847 398644202 31025613 482394658 458103303 75439780 662067454 336827226 395455426 849691681 895955065 284613118 239729500 42869482 837252471 293206340 579446992 13783833 375106635 422781272 484112259 680127868 637879941 64332222 159269653 86970993 695789325 628334908 579845328 652480242 703880948 552926208 746949173 559776291 354757220 141255035 18307233 743649655 334103245 597824413 484443613 975492158 226094051 488445423 959799444 742715249 630023206 886193579 140218278 106886025 803107735 763965582 743513403 252143012 215396246 744895668 310609116 895798276 379801495 864404218 693947556 636653775 445153399 388288272 355803601 136251766 356706724 135259785 77810569 840330251 512060928 216220604 683474007 25604776 738748904 921595009 627888069 626066197 915305172 115832946 169944891 188669502 27736828 473582128 150270402 73555180 876368781 222215243 929872296 806468372 509550655 325824915 464854763 371308151 258297877 347771712 646513710 202396754 878073980 779632038 929027114 653646573 643439854 919604010 945077943 871795424 661558011 367464086 384757618 915367953 328893845 10880232 215918092 152540963 434074258 611434697 663212083 787154467 889680628 367418757 251243155 161052238 552254556 738667881 94892986 156069926 98181846 637168463 729278341 391579797 959276854 2766224 133874155 281151014 564077352 816470335 812282106 292034692 77990940 756933830 363338330 669245491 563019049 399099878 193816274 846956553 329106858 192835976 747226389 108430407 243438105 299995385 40961891 544994919 129677232 805568666 931841998 603798916 158714147 160934807 686655618 345549743 89877196 386584219 668567942 405733836 853177621 581182695 992426435 850132131 58657891 632190606 447380892 785222581 585721419 890388193 750054435 619791317 419133146 89893186 63518269 966719588 105127747 509739758 346502837 718838844 662755839 511811867 135196615 509828121 666762389 274669537 660109668 303005663 98087996 748644110 717864071 569804876 419863384 650283803 828307841 522202712 199947776 900014346 773105436 863635604 877226607 455036674 471463025 216311081 632414102 237322397 617930887 581612898 753704357 579929118 456826943 73947777 607319754 677568392 187088093 275546315 745062293 44036595 961339103 76988514 230105816 949599606 54272006 658723446 845702094 448432621 233214939 706398764 77471483 665389945 823111477 729610201 117367353 313892689 197900801 552491210 447599900 492953803 168001861 293722800 164222383 265517679 78991802 371422517 783857319 853237449 157712712 281880311 480335610 95364831 340565695 473467173 994944314 671376629 393536141 975563328 960490045 474456448 512285272 231910297 833960370 750140576 870703164 712709867 187854970 115789397 583393851 207304456 885021217 217025521 736288209 896472975 747004969 697714530 493641690 838692628 407210542 181560339 82487113 615419673 877778299 357264998 276324531 855753105 599855808 932294157 355128892 332320178 844611126 78457263 692356363 313695066 696859978 532803620 742090977 199866593 616462119 441057947 893116716 228372749 378516528 369829516 621209301 656671870 664233512 78938242 595137466 699525176 726109838 76322818 759838298 167671361 229881818 95132417 559735387 663941296 975892515 462862351 813943990 127095196 149700399 154670181 35175832 224192433 553573891 101695385 18280930 55449069 29873500 946386826 601285026 158095375 618191105 50653731 356099430 794084451 538152439 223973679 828811976 79185680 353906407 75603177 740777847 389612375 408237786 849239900 450670388 902872826 612701396 403094675 147992307 369403219 464495207 170966212 964514967 892706402 579815050 36660666 780604361 810415120 898013692 316672626 432866682 77590152 792458932 358772950 369262636 327729325 731111784 433436528 328106739 390515857 330616670 740996628 603901321 293329043 279522856 771906933 670945943 985421321 997006394 343007018 819812168 855639267 729340922 594186794 169437115 850447827 729965184 55798481 327238378 445054125 2962442 792997312 745892324 612739353 747974931 340914089 548754013 153016933 167085585 99303693 811263761 631559558 211552597 617101544 257624430 628734201 148697434 425795820 59524709 656056859 144119757 253720971 946671215 690903042 797064352 948987632 737823525 525791552 572604510 295145140 768175877 97998502 768353922 340308974 277686275 166953636 165957586 512217261 398528282 265472309 472303662 783677363 59300799 247677965 908916176 993398389 263187358 908190853 814279575 626531332 244444742 520169396 208007092 220045508 345826825 526462806 631952761 588993325 820994616 620526769 388859098 970098649 666567937 317574382 252636182 441459647 228834231 127517401 423905191 193602429 933540682 935589375 41321242 564417865 557964651 48088549 973406364 637722618 607910657 343708950 911819043 937208676 784383455 65786350 479332218 762753885 354640378 605954023 638705489 495364148 890532443 263371292 45049011 545505072 757495461 30335408 349643476 337768241 4111394 575891881 40849950 707657052 47197860 648179313 659064452 632989846 521598882 540352348 332335299 109259433 365856563 858554665 211462082 226735912 428312721 481616439 249710205 660022461 730797732 823508014 273785390 567304539 558864760 701435145 799226027 99207760 453012499 339895093 371508365 749977252 71801355 773737636 651221122 844731030 33537592 76486226 846461235 595513332 838964166 647582919 484182479 128535532 530893251 454169518 729387443 521154543 854859398 768231778 430099866 538804581 947774789 521032755 545071285 9077684 855717520 981174972 38993930 887514759 228376494 193908749 541178502 924906539 41699622 942367489 506048143 607889671 567988067 361924045 517403190 642561286 114487451 751993444 798834809 534182996 622195757 993587667 742956169 119917806 410771604 854064789 815484569 563412124 281736968 341774431 925871704 165044965 441228119 366471418 259809107 207951228 821671639 749580298 552939542 264996699 286783551 289091175 155872473 151772594 952735788 810639336 712378128 95213786 937246355 605341940 732150498 330228197 591257962 732277100 507916111 242554986 999918751 64229947 261632171 375797312 371848884 751988697 854377428 294658733 477083894 111338076 156661605 856713457 492062809 347520909 582530998 335287010 699447882 562692683 97926269 579304553 783385527 750870620 267575309 548303661 284647753 281456036 713614374 488500691 181678265 946327388 894311399 75817791 654329195 78685937 282071764 76052275 891288774 278785545 341678657 251182845 42816880 740290468 958705454 299699818 245099793 304876877 879540586 618930079 584655408 836968307 950679309 983090039 833570776 195582838 616799121 13058830 276350511 511714875 977461220 891699744 652881023 447443550 149947300 239217156 208907100 947350496 343588466 439639357 498297797 298280742 303141377 520255691 155209100 355719118 744219312 201434185 46229870 928501438 178313797 739540141 461035334 671385962 275857146 709476677 877738552 736514967 544678254 980202329 976032281 26434698 763237120 483920470 84640498 301935213 27421047 337689368 467610796 883296003 142514839 647967464 480123644 168772899 329741068 112059389 402254446 105051372 436071207 556992678 46380419 773650735 960987611 64777973 983657422 540317709 491715424 596533753 235715491 16374573 156949853 36691604 888467373 461398598 987057113 382744867 281297623 594010612 351363600 737970627 23434709 68127539 990466560 687986607 436961984 784974409 505687544 728542749 238874531 208549194 841170500 446494283 109882238 173171291 366182008 865090283 350638314 667742484 402367455 807248884 382742395 582986657 604660086 697780428 236835666 695632072 509908046 333303605 242098329 242911272 630607228 869261227 436402693 836619986 683612960 751687858 537609318 747280333 186875581 23676840 66904530 462119049 138489024 567042249 294034442 456457899 477397677 189996422 768964975 685246609 444882656 764609728 153833484 684144925 6325310 195540769 317882573 217100844 369179583 454810546 168572355 724441082 998344577 608043224 855023800 500897492 302754307 38259319 460321332 215907201 466739221 396162556 16590856 83704297 546730230 894400644 679930599 257592505 3244922 206461108 463353561 533245844 858815555 250929204 450391817 16607983 757828132 401892490 624947968 770689047 952490070 428665374 17178638 586300814 126235466 393490249 697611544 135364918 246607779 266725659 983229163 806652254 152510222 642556138 494113853 574703571 496208661 920692591 721239201 712628502 599224309 313382662 678942476 849119089 591666626 728764578 524200507 361262495 65011676 998218772 690660917 36406074 411502352 254629818 329372899 784841530 5559682 901514412 296506506 430309187 652761302 322424091 675696612 858549095 38272655 702932653 170509857 366750261 830407386 832960431 172728007 923568400 715427281 479922416 564662127 363570624 290155889 455658101 989439739 681511293 544678098 645287831 851849227 540166198 673208604 779819347 81596509 116973969 385549064 358167851 319573891 110864699 479195608 516085980 255045835 231818598 220644112 881168255 203572393 990805431 611435069 901544987 872832655 725630504 110930950 609105329 188870487 347275987 578346014 326121462 638600417 415194847 234758952 113779448 169163002 789772456 
366106487 543730087 249926451 622089232 322488098 900890364 474076655 810567493 304437702 388079007 958174552 988509365 360769451 36610266 262320292 989786524 868944892 401016538 625766702 921807031 33566085 56989366 180711381 186618295 462467382 470890703 746698686 149267236 968239249 190266574 315787741 347931325 453697536 614217387 473844581 179467431 285913031 650375736 289463575 900344237 332170737 769883407 730338309 206308160 763750197 399121485 851133769 776881697 671014652 992966463 438543761 26191806 2109318 918526939 834033743 5934069 418390828 729072566 534984586 977543175 434563737 166316457 841474831 53036889 831245614 298485760 321188609 985404653 946355759 503327447 979187555 346499537 341503544 940278538 244217064 383351403 837205007 942978932 691687658 94795817 825178532 809390120 381704573 505820220 291116726 484638002 520822645 409632441 741567420 303911770 258709308 61645932 534517932 668565684 527945978 496484215 654140202 552442271 205661604 804079212 540637417 374794374 143666730 549427315 271305261 253553789 162195784 976511782 949141441 80181978 899397221 511639883 542589108 148628847 100791360 959888547 568824993 302995620 73595731 68186095 895465820 590049287 234485478 426587568 592947416 260189007 99471976 333093050 70489272 205362683 593932280 121493257 779558444 830071273 593548274 711927062 709460935 191721808 877021336 639771035 597662179 625250183 225727617 536060295 450192220 517208035 444007477 966845253 641695320 999823365 60657509 52523671 350267319 582316240 609671160 398800616 454510197 223334246 888507183 550871782 656655139 525038433 499415164 97060114 571573891 593170573 888363637 706121308 161512015 594486430 360135257 877928411 267663259 7200755 437408317 892342148 38413945 496287010 883481425 51982285 334087875 433253507 862274291 651994835 119398467 32097852 365990110 2413242 62366352 463658343 32045636 102716708 211328349 29351089 684307011 749201901 258356292 308098106 583447156 356430467 237146666 171806299 437933715 420327704 849065102 991878065 462786793 24702491 347938371 797159982 279020948 39858926 170800304 11961972 351789854 325008743 215843496 92075354 898715571 264271690 408753635 350645009 924889075 970565363 510700264 753192509 845885985 477603138 469799484 837709070 114640808 695059687 396304276 964634237 134586891 259516603 708562878 723025347 667595217 299120904 461981488 237264681 814883061 742178083 511054830 606477649 472954377 748579642 518729056 575921718 103299941 109518816 334927880 595247062 178995177 875805735 482981065 330530171 843719902 697552919 772620680 964493935 831890376 21274170 14170650 812540077 576604165 289329049 379237532 863215842 652253373 684992593 995947332 565481122 614060267 87722627 973800297 594633110 983106298 410856980 99238750 813655691 158745659 180705232 918913724 887987568 579885359 27747385 389559496 625340170 18286969 683874453 834549559 87224056 541262569 878164260 749445799 346530521 828243992 696487526 526978497 106964989 642709435 624094961 571227184 738732749 380806923 165961074 943572950 175572787 14410001 167314397 459652560 833523176 963612995 14777455 326938600 69008504 717974426 964935848 85920015 816953304 595668422 338222329 649213327 482902921 339146272 488300195 691985132 167850958 782258704 374249561 420262641 790555446 803564403 390546239 340471382 58946721 87370542 790376667 859063813 947938868 338704525 269556021 322413660 234244874 69982765 613334865 481257989 28652980 756223042 151536254 383386018 389431589 981043594 833658977 839619418 681525008 379750765 60243406 170364230 463974598 267369945 534411951 303124210 826592974 476896378 132171663 839652720 335953047 700032410 680040832 153639226 754240279 678355515 779823664 777042516 818399279 385784084 156658730 926794717 443297274 248035288 356324173 170697724 205959328 585267525 174763235 771560725 984075258 5549965 650379571 658263162 913745354 388333401 984052681 413437217 186652537 965902918 118753137 805896211 86567635 515241256 568807661 466326355 362662333 906797675 123484502 754307561 521459006 40546284 274871127 178329564 950419581 952455668 288990160 498343125 706254837 84603687 546916085 846850698 816471723 747783569 278960840 866700231 375743952 740531218 443251470 684617539 654060139 337093248 406845103 279097449 541133239 44287288 416145839 701847004 805512698 228403351 89557382 281319239 759145620 290415852 715259720 155728687 752952997 844685258 648460916 638014267 964989271 755428575 922345722 939022594 109841491 417712586 19043831 477588796 90193546 757842040 7850277 154398709 907943552 673074384 316676306 358737391 244883789 366488004 647727917 598201518 144433489 102303840 530050118 677703233 99909886 899263030 502485301 511710467 170558930 996212799 740937733 77237732 277203367 670846558 97111120 77679057 469657277 360635299 745308354 952840443 675352790 17765021 837269401 290716389 624694367 693943411 462465676 71211113 59738864 818025193 109421123 663754657 690098182 367526671 824459594 689952469 537057327 828718905 411242903 345497342 826041203 797906835 218094398 574603475 809617798 388140025 113533544 823139704 525055417 602841346 837623041 222557591 219871055 24821207 549608791 803252873 626499188 927269905 677163414 555868984 36949493 586141614 746227979 401416715 365517714 959011576 884523767 539275611 450106629 718867863 345992899 652897903 518781642 544862699 336993106 263352537 178360491 351120812 423855453 526351491 153860836 693366100 697447111 494531397 290578215 794544887 854223493 938310576 86502639 190229165 457290960 575944058 308242763 466570954 631537965 615181438 128214297 523531740 15046307 741069937 376315645 787523066 583214127 386181478 437925018 167598062 234698588 786017864 967483438 379776048 24884593 684418995 239490686 68170854 742501251 984146493 705001635 290502695 415356631 657864088 333906673 542529776 227241228 221078203 216289113 847976016 367806365 419185936 771371440 247374798 456335387 125873531 721431724 889943997 759704452 838126783 195336376 984207215 699270143 245931857 422486638 996463177 134179407 615457537 410708080 845013188 231574237 837070178 391239261 821593587 416614821 198683522 669873978 642347815 341545963 249240773 189502828 93278494 770547193 948999291 569406824 315691954 237811082 979834696 840388233 263657804 648373309 757856502 573645449 804792066 870956979 567932653 7879024 938433991 520366997 697921067 344073313 332086178 544097357 131299990 771998001 564321896 343971593 520309930 753712396 555142815 750242905 372103302 548790910 748366374 984210575 453404727 285455466 886767498 764191775 281997365 484720608 424270974 294462994 468920554 294069308 207609788 788243832 851994307 240461755 120012188 987972621 946946138 464827647 111889325 27001963 227018523 267915872 493066597 523979515 225652272 697031940 576167675 819594044 223196568 618408292 883295167 852461528 194551830 152932481 459580700 350549563 916706279 522639617 880926382 965510175 592458576 35956269 146710546 564252897 431558214 386194069 412173198 418984981 399368153 820841912 465393145 552303352 7262404 19328699 707347146 279825018 293925571 116250006 538588740 633793650 167608028 141441071 770379044 220073312 697905379 116189499 43487733 492929868 287447202 991479277 830230244 248935145 504187836 932475196 182913128 772693539 768410587 704832648 546442042 112579104 379686472 311857703 612119309 851138168 436706157 130837246 118911206 660516526 143856845 437442639 636282181 144672706 156550406 31549528 774443564 369698627 13361582 355912911 147201799 758901910 495882082 97087988 432803968 802223066 636576544 36222604 251280423 420538612 157141129 217693064 361499949 744803555 13925761 35493619 525398362 317193599 664370531 908893910 854914054 647158145 620183542 328431336 477276026 965255585 503955939 406363342 883458699 312476030 762974760 513317753 867684123 766088774 350034445 974362449 446669331 282693244 800369698 199447208 991871578 971237074 309070581 770940085 31464995 178141658 403091324 894156585 288329473 42124332 586278060 940464311 854977696 863333338 828343834 933207053 143145661 838484883 856646602 455385147 456055116 423050693 275007905 186049875 951082233 482507511 418600804 293667910 788972779 104357759 173937115 466461225 603999929 942624067 677629566 982187605 408505528 722061580 771913937 418953261 753783810 692583452 544211153 52674809 50694498 619231423 619891347 867076950 270813284 837349998 192675339 156225177 767257281 925220204 539440737 687154551 975081679 755969753 197877182 486364985 421311386 475353754 950110774 486382401 177645691 644667188 174416419 722112605 170285196 931524585 853063801 304557356 253741167 470099750 291615385 604246845 855069603 115143742 267434166 68827372 533725653 369431711 529553289 369525089 428234770 428568389 269116825 80646205 360366377 359526558 678527242 269832905 172625671 486466525 285903593 150055556 875922971 978177599 429999422 386830064 822803162 936458242 867870399 799144345 908428761 821315241 97573279 543215096 427285655 26658497 850064426 115140061 631718247 355772124 883426397 393462173 744080299 51398898 253869637 687059906 462203429 777261892 920513154 415094031 733833210 970317970 826915536 476090564 179258254 375165865 162610228 698506531 745332267 333112153 994402519 79382560 479287982 430928963 411041021 557933290 699298697 41269170 839736445 726710881 659326890 768804166 628668209 67851673 316841629 162774852 916188075 85461150 138624113 453384548 97932296 846763120 132691829 434517149 78717411 524050667 260625562 618165341 906145458 830794675 152789003 553773856 38442848 609074593 354506258 398799135 896128027 64107663 724290784 110620490 956227949 491235971 88263375 757233760 910594261 297631363 870004361 37455953 366288622 514308821 354770157 525241934 25572476 443417624 513854574 525486530 501524376 424387124 681953932 361224775 194561359 734507571 188305301 977746496 790229456 479168521 912893642 640810199 
694945744 141079819 470758872 678570715 835900239 665937691 615747696 318849481 719279181 285920371 479305388 869713441 352963678 906685767 703607569 325870241 536485582 596912342 668885565 354401844 904570220 439340175 764221061 681962528 358864376 564977911 217571485 322166347 284038416 902114765 185689985 447648587 791323597 721557835 900114166 890503689 838105907 853899620 256717328 528300326 810409359 305132752 146505361 531033421 971051852 804291288 786642078 742802787 131330818 63442299 303640468 75081578 127893083 55003363 415886419 254576520 736012069 114457168 501504622 785656724 694990498 948939458 670556118 335161602 568680309 726749126 413089263 126134235 171559770 899051692 829690025 284222163 19406563 81286595 306231199 125612102 13080839 452077802 326679425 337062381 176811760 159077491 549965912 469802453 435019365 947310096 781985758 460060202 126134240 996404541 494693855 409185649 881524996 279889351 864380786 573296288 456954590 213936950 889605031 727366697 992170002 925692074 84528135 334021542 138982774 468994589 616092603 152928896 694887914 993697737 289445647 181899026 316679860 778090301 524270190 855686806 235191147 302975817 984335492 939306115 283254700 450226737 828181496 336407552 171162950 190682685 922203878 453871591 513547271 788883005 916665027 932989698 444307034 126582552 581759246 105796757 689709060 537940850 856675300 678592820 948934993 246100575 260240575 672175021 777348791 743640148 786866525 585917194 439966266 48595294 508938022 868876093 333109373 284442515 153703406 330548988 767946021 747004483 81332074 183721186 724448167 956403472 931982375 483535605 679247861 84355554 546210081 790888416 33452138 79416491 837905739 677911627 775537580 292778839 668966597 654462003 957029317 38997928 605454991 796966468 458710898 687483953 623703556 650558974 203298575 588883516 61204199 649769200 770717076 286863462 359659377 83626187 184438576 412892084 36188139 725723656 336827401 12452087 538675922 596753733 473184198 465680695 62436464 653207621 888387049 360288814 935336329 335394904 69617206 676209186 614140617 107035799 951320789 657655923 55296701 476354140 201520131 758040565 609667920 862579 526778104 685617789 252785839 525747256 393350802 873534124 881875829 968981652 236009735 115501954 217808564 552997285 782499209 130670722 365887618 351631913 770198933 487462773 42726542 706495721 613870378 91705186 972557213 249809456 182536125 855957824 319390746 679755913 246546280 290776291 432205400 821176888 672672691 227746005 794875967 565937158 909474856 240883450 856598734 572382567 420908863 405910508 801461049 579392964 376754469 474032655 749804030 242285839 634271065 842097042 722533462 61482353 96789361 784605986 98351151 481794734 216762809 236539797 310852055 765483298 975137750 592570655 608096937 656856396 792864271 340764032 283478527 600535836 76634792 264970643 47539468 555935838 564896462 694889442 634538470 108005970 924540490 849725384 151528491 951446157 169118081 343862490 977340422 51719750 291807684 525846937 400384150 897670088 615560397 498340016 668340620 528773635 849367328 660268981 469062883 406956390 22887843 523612971 311679160 202506016 462369325 293133070 447171094 162680313 869481956 874896773 351718151 254372221 455287578 760001277 629281181 719693288 219888989 449541943 666458339 579132858 500401688 506916348 420697293 746681623 401206368 4110013 786838772 496603949 311606622 946204699 148967653 777481947 385343348 84734087 285979036 36101873 21742193 208789658 285942708 885437950 557062400 363279916 725368492 708343792 574702129 878985438 759516205 244981212 97701596 660556162 778190506 484916485 861950224 90953847 465656838 604638670 403241595 254214236 328981273 66958891 409425991 698693081 961195286 822209244 736360064 837368024 48218880 697886942 797668551 248536130 158562948 421298742 507246657 22995905 169639603 792278501 46509919 737968164 459965252 434345251 844797542 669484845 221817970 491254114 54356961 494413648 880430316 929259921 187329475 731678142 958322307 325545545 212038643 940560261 208510372 448434196 388819525 651433807 828656228 251144934 610952707 745504725 157551884 405549560 583052759 346081383 320867090 723264189 807105002 823837400 61517651 313969187 889085635 660454834 551079738 56406510 694045098 805943341 250870131 183781261 298598717 66800058 186657442 545316439 88709616 600619391 404871322 698066625 913953929 91842334 1308183 795847353 10266728 389306829 478669152 956062894 609034098 158461565 691920567 381677663 621150268 279940943 663084981 354305110 447658125 8825650 402998861 350346618 586230677 985860380 43179247 736585916 444834874 481136371 753553128 850196542 982862922 311753100 308378440 201970813 140328977 532772849 724771540 898795861 536426307 466648243 597210005 567610416 953845967 31243121 326482057 402709659 819499045 865612398 545346053 317508966 669432280 203269360 927630484 192883526 391145552 344966632 335011821 182372866 206114616 957235716 435006663 821660935 564008234 173652230 600719222 134615482 928028887 795335482 415712142 364279134 574719986 218153476 233492643 843380131 220100083 292149896 703263211 67256972 16363565 676107244 669800405 715549378 706908969 235666546 736820380 535101791 632418817 725818699 514222219 403015634 313186970 42846458 286908170 172421938 200625842 346522892 516801200 87059606 146626724 852729676 975193227 693535993 690225248 777344878 483718588 926597394 432515745 762228584 74952559 285235806 505913054 642904736 82771797 993392619 673645795 44936262 41852922 629525475 973365736 734134365 474380505 676011606 847888238 395014104 275352814 512962796 359558994 146821851 523428148 921666238 410928264 741055186 806440505 54406062 997927744 909355874 506788261 139487504 123411677 12706812 75117506 591025708 966745841 868581843 448580956 69742782 471161844 49119343 666706078 23854022 375940926 428468035 468896967 162762055 353734169 630850583 156197491 291560073 810717617 380652124 774998260 187079034 830530063 871816808 232125112 306284639 390405061 133110160 231575537 337905008 87078499 796351291 270066541 436156608 250347638 288927417 263304454 448993538 247290168 864018711 764323436 933269255 406238286 354450620 544592517 951431839 419365132 973046197 404511964 284278141 657150503 711925462 551138134 793083131 934772162 438776255 941863033 495609098 840401677 904948684 210907700 994545949 218038640 529968688 857680201 840377338 694628735 377333524 9480530 127388657 862718519 376775134 609583880 302765480 555495255 938879561 582448096 386522005 242764411 652253608 229395639 209933954 202877639 285249319 537866367 399151013 608741397 297320732 608982009 887620580 182210890 105284073 116474459 917960445 559099184 758497090 822172808 249328607 193571767 220526675 755428508 510306505 444746198 795333128 70881735 533321694 157838930 770178341 115323025 957363688 434863849 764219184 701789515 425625076 181621935 92165615 136628622 141987062 617392384 27726314 755265741 178656274 359100039 156209874 954534682 47766898 53378748 492558645 755939528 534611870 847684330 995200221 359997191 946073047 843124097 957913581 635863031 3654776 471367476 271271310 246669044 291930229 878380670 396770608 472886912 888242030 744126841 346480002 698021793 777053279 588578554 159046094 950797494 848412835 349831864 324020853 252616947 354704810 475742419 514086273 340647865 928858694 876418810 506909612 117107787 36261787 207858970 5782337 262381935 49015057 577218107 61454795 520989535 702963390 181635547 819133321 465991328 910860914 320379116 949300536 977390337 56994963 307388664 55317329 669167733 558028090 950348885 738940995 312760461 900836751 248788117 493950994 609088162 806854681 806391913 207570716 681782821 720002238 197961271 854365530 482243980 664248752 815069521 419781309 139658541 87243160 891251279 706116311 939736750 443213385 383435928 469158375 706461777 723281335 26404828 322789484 668756986 311588863 646547021 324919364 38697036 472334070 603557102 76469152 438644 264081573 393532240 160312537 249338166 797026829 687525237 325185859 61407763 20970701 685427995 476392911 347073769 829377426 106787337 407683177 651344735 880258219 733885349 845903763 976503909 1021891 875249214 576655443 228137218 775568622 845907637 762916336 321942329 836828777 809431498 257630147 76158490 382513641 141661070 140180539 608333779 193923836 634895635 202113600 541358050 693051514 713365675 45879258 103043733 213899228 127019820 274083154 263226062 548055202 365792157 493449903 594495667 734146267 686233161 802220582 347933245 743169569 487613800 863436411 90271336 245645452 798876852 706109120 467781709 881167351 598998561 448066037 316290161 504957153 280324616 530827701 366414529 617025517 891115599 284324227 70073673 885384204 36102531 56547440 555509754 344531279 488766005 207941871 523283526 731051941 133680906 434953339 616198496 48353842 677990413 298385452 765784261 269545081 624209722 483291388 684446795 338464933 289378527 968698489 147683080 202347099 486076766 76098986 838251080 745742576 571078532 700873291 469222453 171237311 434594090 883463374 774761021 691463244 640109781 978539529 918950385 945439147 725938888 942368816 613896450 652324082 913578028 475249230 25742717 155449166 658257778 475669322 37179032 368276197 344186455 908119241 267015060 38401051 886777911 440709316 140530792 887354024 725698152 465727318 878096665 65921738 219348113 151519692 156817305 297817861 548933112 345513849 377709385 616104375 507304313 296467595 820478559 935386650 793301356 637579634 660533292 482881226 136191770 114722104 37333151 401965819 335338799 798574877 93209181 21410787 415407287 823254230 280589412 409353175 790334774 996652664 839220533 869185510 977955286 579130750 970701203 520555845 21511601 8353116 410706704 312606953 998486331 60628075 352475728 28680169 463094362 934186459 774820146 249383266 737096437 134631260 833609177 115594494 
265176307 378996454 20583882 469090147 626051705 711239533 690427768 946721060 537585293 560278689 138974032 704360751 280513587 200095010 112556912 543011500 346470925 681637644 185693824 770928106 490935251 972667351 355363504 353422099 157397183 895889689 357678023 85490654 882791299 794846410 262359983 936932917 394090409 45486254 172808130 854337202 796629541 984812002 621117512 574491495 3918251 857512908 448879505 694333870 976996926 263354958 918130311 235607898 958443174 996410992 928975961 420381289 627922829 349243308 328109982 197452025 780874933 83902990 4237338 43273783 455715518 479611736 892851644 812404083 269647497 155761524 75708493 933750970 103651020 39436566 425053790 255944963 762699167 639127644 487570486 612411716 500614818 72875501 562619290 930756416 367075060 215476222 318600360 116821560 108198256 924163909 674176295 275024866 202336287 644325742 288785537 298386849 947157516 205883280 572084340 40635395 846910269 145869471 447594656 198637177 632630255 335618432 369981460 641281900 811037245 41362380 34381211 734807061 785433899 215017894 837185749 568491825 823379436 118439214 828933347 214335171 914308250 569359337 523494494 854992685 670863392 187478287 337107090 804060631 497753871 510030423 323138586 850506826 611870122 774220487 410810016 69579351 367380402 894583952 32311116 96580839 486002112 854014487 210805051 337800275 249223402 436352144 114672597 534232380 328960736 430973257 372829657 586130649 795616912 594529986 18108121 434214922 213947203 74474987 595871006 76005994 564495266 134999894 255602903 578351462 944060507 871063444 40185595 956396780 406476826 274570916 194992532 289816396 747531719 431087641 982458039 840459377 936265534 877888530 390742166 843341017 456549456 3082551 176652974 478242820 701715173 166129000 340808914 489670133 777409347 547723274 786494423 318611842 426405631 852940542 705161308 802471916 599552574 469587016 709066573 853261327 754427190 328271041 39738723 841904176 520392544 849424548 755366178 573625165 509445399 938426743 424357048 827179281 574396057 15873627 85631540 275665513 891742088 166811815 31786182 22997071 305392051 131568984 31749774 782567712 404242395 620986291 198722860 460734652 47411855 917699027 67451636 303073302 468796533 51410098 745160552 900220069 303242228 23016233 138792096 334379640 665650068 237885757 908795902 477171391 943171933 596069485 952726296 643023335 118537344 990685814 833435996 746667544 20540314 58505016 870424315 973169075 113174289 276665842 498566883 745583675 885750764 967276520 402147368 304596688 831633084 221368540 838267366 651353396 508709120 493694904 414125854 726893187 809386359 71816070 455763988 53592087 572655224 138430620 287091776 524851188 283605887 788067188 645263541 774433117 722695182 100749768 608612885 606540081 866356086 19598436 852750530 542823368 265949627 880707261 983555922 842714661 840208921 520776386 452942978 506458694 586956268 926603754 292660665 56820637 225111947 104790327 937686017 94057554 201929843 363563526 114936417 246786986 827568981 153147394 565742133 679405701 971683607 442370170 122514173 718590103 215507717 674899489 882855059 149705263 486455025 24560250 940284428 608071364 184334352 691235139 690311894 979402460 386991297 910791904 928758803 532359312 458343746 324180314 819774614 88617350 867599337 647873302 391432447 110340484 206569703 499302373 780129449 336156734 603354659 331641391 882892361 989939686 101904996 856007351 132708308 88962119 717782986 854154020 899080758 884567237 465928259 928781615 909921712 116272491 944007898 534121405 211101962 637038418 541427925 687628183 727545822 744784524 681498777 330655897 691515102 284277583 390178257 450644652 395873120 644425466 822883227 962211832 509062630 574275397 898719807 606544304 129610233 810601775 901294191 79862486 809903401 348067178 889572083 80236789 529342278 499545088 896419220 154523217 564308489 398336439 363338092 467521121 348656484 236559433 331445119 85187525 307643810 869825575 643910629 628866818 863128472 349245790 551202965 782924645 261337524 264939138 332664914 713528469 512776075 562166149 867147009 887590381 341111172 915385786 784038977 464318948 540474724 177367016 467060179 772315589 33808975 901633397 261152896 822882600 700027332 990453905 899257154 631858115 171871801 873897815 225467901 871549380 89188879 586758053 451656103 920919749 432948456 314300792 442500330 50303197 622082652 979753606 949194349 712857607 795517676 487954469 118214929 170292802 812509853 895824574 53710536 526414407 61583442 901948698 588725008 788377671 110468731 388433816 839221318 743783905 460105971 655020010 613087856 835756240 386534357 944910175 932952544 229422792 555957894 651287232 12075191 302193225 21367837 102795145 626020042 659628886 537824722 97231443 288335343 336816565 619026743 437917486 134557700 337319144 230376857 781565478 744753195 594112886 875797274 726088758 205071565 875352990 673465327 619727745 297391640 987203885 314157607 261490929 504494128 271511064 177083307 555432168 693771893 390658301 439394275 6839631 282542817 353191076 223750057 195624733 24051089 944442598 867446371 6249535 678145187 348129955 332099803 895920515 419790028 747327575 689699243 743857010 727933648 498974172 670361709 390764760 453257928 877695442 844074376 450362450 960000020 518352572 334669214 525666000 817669663 230367459 632100452 578039931 436000377 599094864 939605508 553782933 638773062 142554300 88337241 278121977 737102638 854936619 514108168 371166734 700073156 715964081 8237249 309622633 334134959 574170002 408480171 49604696 283748367 507118123 717553716 524072132 877537598 148123531 374923098 370452227 86609135 250790892 780072988 23010610 321155801 159739948 723996607 436826931 267619099 61515417 668008271 915100231 336501242 480045463 816495756 929049996 923383930 30216605 839161588 124292336 914810553 538168056 359838809 927214403 97981069 815206333 921978240 54406567 907636524 583327464 547507368 424566248 435200445 189036480 666457074 738631176 77114652 17161359 314694936 857650282 690659703 549062655 885312230 753950199 763678585 671051596 69087848 728334616 56503953 550197629 479133664 950161191 492641696 494516605 472517680 843566702 539415229 310576096 199287244 762621548 715208867 821893953 331768724 92601486 213095450 307058531 109800617 373061099 155708989 810953947 44602796 452945124 629374983 188500206 286566372 671533426 93088716 469075166 788761854 144788502 386771635 802008548 652433645 253184016 970990794 370034264 364778019 120908092 191769059 258857596 680119326 294408754 664193894 289795816 300059359 22180480 812810800 115780770 6239264 483834682 136480483 25881984 360682092 799489681 437915162 670481151 423111071 661374103 29895992 219752308 329031308 559126147 606731076 577445243 788700919 319552971 516898300 829175710 755514723 90819713 182653411 439228810 196150128 252221377 673890566 849903509 45866000 674436762 518257075 713575466 328641728 932541163 419448847 316800725 251439551 353085325 259468030 717961930 63704820 985201646 4810855 629804561 218118842 717800896 553303906 671108665 415860154 363792674 214795481 305199162 898285583 237741536 842120861 933240801 268928046 785509004 574284457 342065879 12004599 342488968 560854403 724178340 288322978 616216895 997248604 437126409 345554914 5828505 84005725 700544080 98008159 554289031 751424414 586544385 576852637 72908788 226050799 852852897 552039245 167047446 766537833 919840531 955079603 115677645 191330719 437456587 394032563 754217914 829198160 340115215 516789439 636513480 628420285 782927444 771356322 599400981 156900264 277355168 494254161 980325670 130296811 124150406 529970561 879206502 774779712 245027863 184926315 304729734 987982061 815221959 223453867 285242764 747645247 710935551 512324849 509274099 546237358 929858247 166036685 895314972 698779238 365806972 895404663 726854489 94459096 803511788 908520361 389567208 518245821 417963189 356009605 997786322 688829611 398682276 653728054 578305525 428318255 305561907 999317001 754140067 235765893 552250440 484226183 7104702 550550697 179033161 113865771 976703814 469347171 772321140 788695938 146808331 326872558 403053131 143178840 566211096 673381120 71089228 182269536 384073843 584617154 392314622 435001040 902336055 188399164 65336553 698457392 396152592 740776053 162820124 141988517 257594574 453040262 749217771 925814593 774767336 772431258 727887108 502692309 681495763 90963757 660776993 41991866 358412354 101384163 739754673 801958139 196104325 683471159 404327623 82109886 508120821 370094110 562742855 234398956 992952194 68383858 135362208 285381003 485042276 706461381 599169468 820173522 247927083 675015599 231459197 346447929 362695892 977231399 589270144 839580619 42560262 757519999 317475710 374678222 635551585 701045706 618231189 27672578 152079334 290602925 418141106 105441025 190635026 991990236 790882230 881954615 765240716 611483283 809866346 971829986 44725636 601685989 95523940 920689927 281193552 567769915 627564183 472657504 15691916 557649806 377857552 252437614 663941680 96240916 543939116 117496742 345265557 577236070 154545752 124358984 871279920 577624737 432692854 922047594 404762184 827314924 619228410 483386125 461478770 178388449 216052370 729069952 35935364 190348247 175614799 909362369 328455682 320291550 702271455 703846446 598215869 383219133 899859312 583328097 264272917 22407407 903422510 789193015 26947760 492123985 836688481 235565555 416623870 219112263 701132494 907210506 331310114 75396831 683692053 865240989 916549066 411595408 501654052 454442889 642984003 153900422 774810012 61711730 242807429 510234207 72871760 115303917 310371196 699545752 304230454 496391783 689321364 124387202 960359399 246403833 231849965 417785950 474061925 524713364 106038616 39975906 652743095 582900176 837161889 743486864 667675924 257961110 524151082 528195479 444332516 774580247 522624720 
259832858 122823460 760079417 226670556 193527916 346519565 970031826 420060089 495024558 128339110 62027883 878099961 771622802 360501653 630721183 871071797 30283961 663095115 978968099 792858320 387491489 548603181 846449695 959916096 373209350 960363359 898912416 453074860 440448157 804732051 764906804 989134659 910777322 739729500 864335851 451422530 432409018 193049642 14447002 109805695 125783298 15101212 421574735 904742216 399063560 954153711 821271843 604073378 694866822 464232411 333193517 768330266 65915600 44013778 467699008 143638903 957254179 421370412 112792699 373381417 325832968 125114972 923190879 402157124 193388581 418046165 330145839 882063148 127270383 726182656 521947645 218105247 355045117 902402024 979208101 683432888 22149287 518011858 464531368 806587518 256382552 424396766 758052454 700628216 754928976 507354016 922638728 806218598 197866902 16602757 985061177 685733526 657490129 867025731 375672895 384352432 766433412 15307775 668325578 241075485 881399870 403086178 929861353 98709051 399174605 294800278 672903587 362683530 973925735 124476974 838841021 299122374 123733829 339266645 873762552 530676047 295540425 426842361 796947472 395871996 850078959 427016873 836732523 406953269 359446965 337975803 152357402 496379485 216822132 344071549 786687453 99313977 165526319 609044627 92681134 166969318 651133619 678000496 94320405 729284372 274409839 340825560 602487124 232881396 778051961 760211939 151677584 981210252 59406380 364265346 255670435 320188237 75647521 395714825 393351970 482224217 562993153 57199432 389082686 669271550 587594365 321990969 58830590 45056000 463936637 755127284 852533459 475949687 775486701 206916749 604915823 382406605 672662836 149629925 657675279 399527778 19916084 121602950 190993678 498293836 455837916 745480157 731913049 356442705 137164971 157060813 765050566 708135433 411016602 741123934 233323083 494891304 10229174 425017684 826985871 348897143 578413773 79481727 476128697 608337395 579490326 174136604 946939603 566071369 480917748 396657074 198022679 383225352 331406533 705413657 261322905 305090755 525685911 717791532 580196364 93132136 624282132 178466631 6324971 150377653 215294662 800377172 413211998 270282888 202547567 131982431 464517928 689283348 874138905 607589505 766052954 909551506 357616868 879381492 442438249 378399728 479399716 890928841 810455013 719180148 739097994 425621194 113967915 487729688 33404428 696185741 511907478 247912834 33339992 306195441 729289318 753198465 521959441 141170262 469999399 789994647 325848451 240000940 632806152 436775612 866871894 229867770 835765614 489337394 136157369 184030298 602705559 970157335 392207024 447206831 385593923 976263718 207407685 467267381 793716249 927735067 668970744 329319308 877426769 23075323 200052025 335741414 260538113 326378394 662654749 495201368 204275211 833689312 37766951 150134921 121862436 41105609 23735568 93683441 459174567 722577434 43729480 974907001 443508273 770446730 806760889 529905540 999717789 654052252 494720200 445035932 883616693 958127903 37316262 672091986 922745678 332580930 757779323 532136232 905294294 633030483 814931687 438449793 383944872 858926703 527514836 926136574 844115322 85180608 196618048 140295104 145293232 719717307 815831296 773541752 721835097 492984236 832848230 626701480 394049958 7362131 225472673 448050680 437847315 793557745 808308896 712868642 289731610 381922695 204317101 855170848 112738192 497121191 208144309 146303293 301570287 645177867 818398201 967713947 656768728 112935967 706438249 69386660 724280999 74799315 243425311 159522983 168860260 377617882 189281046 894061106 190662275 627510613 46503725 413949057 650119672 223925769 715422712 505365314 692609614 712802818 555181977 209231892 922944786 735821123 753848305 855517012 141981323 488796363 999661517 561424881 810424540 948202760 679851633 408131892 717066151 66796768 122705727 570121405 526720054 213039119 742125740 450205279 690518492 829952832 170547696 321847975 944129534 586736715 487434217 282542101 791676031 272290416 917008179 34065861 305367561 669099936 248699844 198069527 123755015 702817672 73898685 790706466 915689559 729197339 83239676 793179396 856452708 76011932 758834247 81225061 945892598 767430659 16045201 575982498 696208002 805363504 856418670 497662267 560188312 655124816 710288050 326682469 802156683 362827176 368162337 210797046 987612744 200141243 916654750 832424101 282093821 912601282 444558494 519753424 144495484 4473685 308664760 694415789 201733948 365593163 784276985 865469953 803290705 545580613 99590238 456933357 311782544 94050981 954078813 976932094 967736783 886678419 562615410 430360704 900025310 457072815 169280143 253172338 944997583 376543171 140952709 886771371 678303570 226195224 444394488 744296347 799847107 379040148 198873858 388491937 621419270 498867356 422749726 577871072 426739365 981474171 542701063 93099015 299328181 162627847 912721648 203657683 991177762 898191101 604755416 774154185 585296092 665414483 896745681 864948891 390978978 264858684 289671249 705534115 154488567 414105829 719742368 335813283 826717461 285456367 588700714 719737084 246049413 505393899 314984933 371386496 914602834 969256757 290780056 56193544 556899379 397575813 955820655 60304057 896538366 896338817 410451916 698956814 348580226 986808520 467664357 168948316 50705814 429087677 390506184 462675099 677019838 821266233 367262299 78510265 869176928 618966655 60151570 647985276 665341476 129511834 370496108 649844700 807125691 533679291 159309574 433563889 115048266 285755793 815749263 282236726 266563391 85388114 324372242 666739775 819991994 145295729 887397120 7746678 265696013 479296496 334538339 843313997 76646626 415073677 316614410 405638841 271510830 502058241 147111872 617031004 393112970 109089404 252598488 286315651 576616952 392173597 861002554 95624059 407833331 142792877 332694129 664246557 418967587 92885679 67263214 660964554 751779444 905553454 152085352 787241285 303798962 153850816 380538042 907785640 792348941 815070883 931452788 902146684 99603709 811431875 862252671 20951189 757178543 403846710 261921700 872099752 530149122 202220644 872639574 564379590 968365555 821829980 709520413 150106243 496729120 946335993 951980286 236725680 95507627 915622780 518110380 999865096 954610292 387893567 496870249 595816165 100926579 213701023 300972556 399371608 359818512 229026553 124338957 526829943 71762760 549403695 865283212 312639797 941130034 885967614 234564818 874762783 518529729 246571768 179002705 222930358 370423901 755761834 17049683 951906690 749075077 254448323 655493041 91259119 351171440 74213738 792920508 30439991 313801819 817661727 528146241 598472808 74481371 957371230 240195740 708129823 529409911 166568967 355199796 27340021 248792861 969247101 663135585 170727658 570824775 592872078 744872569 108575167 863993043 115953963 864254434 701143441 484027402 134577621 793075247 384551790 311720663 88497339 86553412 718055516 300893219 295987857 858646522 111803062 921963602 783985784 290886248 703488231 55462836 401341037 329244085 832800704 768815262 197881365 181472564 711573475 680038278 11707905 336902732 724160969 421317766 477268404 561671308 950119862 60528585 96131256 815590863 271772832 656238200 41804024 165256802 477261935 17137466 402748989 793929899 268798649 501628430 544628236 40061055 82847279 161872502 597680417 609594214 632146418 425010353 527577554 861682118 13288552 952203125 126184316 288266764 279078681 10788913 884619700 494056249 384007581 68248987 620602959 265825993 949619346 793474447 37067090 729849200 46317393 720645772 76799527 26916466 231081939 459655706 509863435 176418151 844044655 877865157 403290405 798440140 329394835 80103078 758704190 692754261 558797712 573244235 770510914 266543295 181944357 804338918 670463682 954438890 752178731 43670195 344939504 478347652 425954288 411580139 398128346 963141493 578782750 535334830 252812172 419883901 18057182 62244903 279827087 284482444 16271306 67609038 929850775 603388981 772903997 748208070 930564495 572330768 333116949 918132127 447647091 592420658 665840899 427878367 440146076 289459257 293314434 329074095 799989295 234938784 50796681 762695419 9592886 177842665 429021715 172374261 878464559 81323226 49449203 316066242 775824264 350791453 470300940 581589357 911461042 744891790 115229718 574211461 775569779 574863684 862901004 895712755 203044850 367253065 325083865 941671522 142060409 165681011 809885690 39660876 764178269 674908074 701077757 150396940 609844697 697954319 44452212 570222249 816396829 215579651 199426635 392464786 669119876 506445903 577090817 405226500 299728164 939194570 330389471 879529484 248119520 680086605 325952454 275839371 954260807 7843849 808734512 978887657 227239699 984056216 298035224 328411304 567205070 881786765 283026228 544339820 936086696 820811072 15313924 939500906 975455096 324848605 132492533 806529049 546530327 718132850 393000082 658359612 272106486 160861132 731845574 990652178 721601589 318698888 137806060 853909041 666105536 572252270 552842854 167937018 78451674 403831779 288266424 29539478 187618750 858512851 606503698 118293382 491946878 7215812 761534286 772187539 806723410 261279435 318386790 561072851 466504540 141014022 521427828 959532513 234923913 428403998 31626505 355487748 758514813 474690397 492647798 507601479 367495446 844711925 455572915 776739821 626064600 925400046 556904429 368411470 75223004 880547120 313664888 746033877 58746371 559799236 585328891 703481148 465997528 408554816 802391695 887672855 705304497 178442685 152694060 600027312 682266405 831948627 426900057 581006479 618583880 276543251 665396281 850890663 879561848 468642192 181752948 92494987 29850261 594620631 787524400 492651765 605104031 696392384 379161728 33553601 614860100 776891777 291484689 542067731 123592691 203692329 42838495 15299843 902175189 964574981 449753008 608976590 716501489 
60390768 89042337 312631355 483996580 908234598 480730558 521514299 884526283 337481694 470717276 80220603 534641597 232889993 904665482 571030013 827936787 265670009 921678882 912153890 195725078 460576359 255385503 654443408 289530020 419966643 963930921 509673110 598093641 474372868 610878877 738432970 24208 456280437 46865572 187509415 963701682 613357538 738527455 845366170 344739324 927649892 836292729 661135001 670333965 308494259 654748702 626581973 483311552 209800428 751415476 485690975 156219819 401520838 811621527 608451720 368768335 273164551 753123418 506749633 107950045 661196206 790928207 584053703 775396028 720089826 915233603 935555855 667970592 228208886 234546482 100485916 960154059 183985151 792943425 793433797 355543569 367885533 602643498 310451890 223800552 839954533 622250878 640241333 671792168 536180196 678662509 428897983 684632209 469317863 22995913 665744971 237731112 384091014 640493980 602144861 45716252 853511624 703729901 901417388 861175339 201599063 59642584 147735667 686740857 571979205 280132426 84473852 550509143 129192214 11353862 470509133 658193774 160719072 305007711 296942443 826357208 445123796 814733406 493814823 367696729 484965133 183490065 186109316 806227571 598637985 463181907 728499203 103442256 637624990 831974869 321506702 627527240 932454642 71463264 683018435 540595871 655905822 616598262 318245586 229664818 68870066 824191804 61871581 568663073 987141166 356110375 941894590 253239090 330620868 893918606 383713479 412318717 923638369 91384977 332207744 75855595 530931935 908702396 284538154 204100145 380685225 939800937 566622157 202439237 36042361 460827314 167319914 595483963 911830875 588882265 79719025 718258038 654158952 514789525 288618505 665109698 107024007 418325383 196788751 17222491 344871835 412472961 888483970 314044784 472526519 378433573 263628253 270241199 766108889 151659687 453062577 188876298 754521046 505719383 68201606 18575437 630937602 97884484 401924514 369867757 646223063 366254189 514416191 723698095 591171237 609368827 748216924 753650908 638297880 195869294 627434270 915885467 142201672 13462767 960313495 551287968 512133854 885512488 304617399 343479968 350092607 733318884 145967792 128241925 483430377 793982608 932806833 141963430 812352502 961007489 812256089 183909025 653936462 231961693 923041215 992528224 78265008 2122111 881077116 689849386 55892220 18390897 862478425 800509521 492196166 906157059 563538920 102188617 997543673 183116196 911555784 8431849 199783387 664530399 589261583 789903698 613288185 794606771 390194009 227027837 255355636 928345318 899476704 621375203 479970782 439604748 57660675 536038620 830997619 953278646 482307039 897428459 840890120 350721259 177930669 231916127 434788310 589919555 417825560 171870493 135917642 828819584 608828291 378234112 650340158 574864129 976049615 205560354 752869427 843336466 981824365 567589880 417790885 128918617 656925856 12013446 775718984 491669913 25962889 71592419 653295788 931452967 485803798 580107256 281009594 493186284 291187149 128208062 403052592 142931013 976856227 34116978 200358676 830492845 183261422 448261026 466215720 648926461 650703595 378790211 271585209 927505027 731744103 110375466 5063783 674692780 877029699 294310530 78210703 24647138 798715987 362468659 391669915 294286271 296125336 452954337 21315491 841473720 738576730 202577075 886459097 604907138 229526706 733319654 777595720 753490161 22842571 962842673 480504315 701255799 405563922 162414650 414253619 266420786 598622324 977201520 720910358 224938311 31348565 82620489 489015813 73972275 575158091 863496537 938182547 520189268 860092037 139885395 857887820 969173715 146501934 568219777 590643103 489969869 468504244 14055992 206938314 100063750 562319445 121766554 55463449 430133802 855006887 454057063 291740816 50369988 794505015 124167018 729465907 399496550 850225108 107802413 198965491 514476611 27306875 44427877 187102941 668276749 28859070 67796191 382342353 248587135 808191073 744975420 717086681 439339881 616651651 632067491 172806584 257616103 824950250 424051378 481522944 291640914 712057762 888889745 962272170 686104014 599043364 263233059 265446762 605916330 262094885 254361646 791266111 370750263 594330855 433265351 440889996 660153274 665371175 797830712 866545282 898742250 871766533 2739054 218202883 812734038 887792480 840346570 55423458 48516633 821514203 248948058 864624415 414740893 66600630 678886653 693679288 491749691 684809337 604094154 574456327 824103782 236729613 649344216 866609866 707432791 259668728 810064258 424803921 842707193 990058434 38986275 14235059 927963397 175488081 495624050 779213501 540599686 244174802 38806249 385352335 900994624 28560388 583235212 524609203 430339073 981043992 898925503 986714049 425952317 755261269 148118498 757702337 242818087 682746992 113774101 134832117 927032799 483917922 321770084 560130594 191070567 585186199 708479773 428710175 104919984 786466297 50164678 335418071 706239927 843198807 973020703 9164303 865097642 450759980 587528519 179697489 327676770 221195348 855581100 489368478 752067376 769768385 821679614 1368870 290601756 681323607 180995135 329454286 823356630 52036954 992318039 281890769 391172276 151223142 44422078 579647238 444103675 161556542 959566415 437939103 864290366 733883526 615517526 770207692 277366930 829375894 59918005 972030503 285042275 947081512 38741722 951757543 628520056 940713631 112510325 482703211 621164310 994240004 115831662 630724145 253896737 632747227 915852865 442102077 455379500 151026007 319154646 432676278 611674761 921402805 791675146 477101743 570389194 937015572 548389796 527618336 665018211 507437445 260382418 826892585 875605573 459917102 514789520 570514540 897983227 10213778 861240601 625334244 850399997 801209763 9019873 42632011 452159712 438175046 946215906 527019479 514809677 411329151 144639166 576507005 198414704 580943148 347145596 596009327 300092446 154512297 706256764 760154367 868780944 404226289 812751775 929511918 731553727 757591660 872256704 142556644 736435114 529264425 473549283 8258182 211953007 921986105 712622476 591555919 22950649 637497029 623059030 191857238 664584262 309208154 705820261 538678483 917781253 304805942 872835296 397660796 811811105 996572547 608708552 5956040 419939324 635841565 567858133 782644228 729372164 732355562 223564771 22738927 517044304 574379017 493996837 41493159 702506381 561662395 184304783 831123807 410493590 474279025 423005842 41283930 675829543 671059144 778570037 481564916 31631367 934068564 324654519 474355069 918150261 413999267 245533945 409634594 225654103 597625135 702393327 609907004 536186290 514084208 831415312 989370121 855406025 614218659 121868213 661509768 504826320 586203261 867474825 412645668 83171178 337729026 108714566 881866691 711044798 328768498 679933056 399082367 681736599 68162268 522958582 758541884 198360500 219513985 544109392 657167135 418667104 945125958 566020906 692687156 330919826 460165707 386137452 263757328 851970186 515354288 205366889 508189928 649083381 599491893 662091565 569718271 999253813 332780161 775482379 606106805 425936805 627851084 476384304 405887613 598863193 918858569 176463495 76522130 488160562 234975155 196832392 245151368 33210213 569452348 386986559 848558445 397901520 372305526 726040095 164618666 564475383 974348664 935841925 9867765 408598254 957611575 552774399 764495412 435222815 731273181 747509851 4352575 966352093 641763136 662424582 369160798 961882386 156023814 936077877 533229472 250734515 569554986 321068034 472394535 171499096 404540496 630991992 589735221 783447531 30831060 72246791 428523986 584423376 59128856 809504050 805671138 334969890 161738562 9919344 808139638 883325955 27649791 441875010 778333971 793123022 958375453 73009543 256502047 833563716 349635221 579407801 604891482 932289944 786688763 154311627 299102379 405661511 910459866 823168100 227533583 510657163 36370211 913760751 945576478 707393723 73432672 17038602 32737117 176681754 297115243 491791735 525941166 825443275 332461509 498116493 398697923 702014172 13122217 853856406 841284323 430109798 741014881 770649161 216607782 291101280 645636944 176278949 471534892 429395146 972651110 993209396 128226857 598289525 245821531 443075883 766241076 186897388 782613249 431115360 646096320 328843683 229112175 409169251 531631440 62864826 89880964 931814778 801511862 884187443 962876065 18436142 104685898 984487655 719565556 441314506 87421692 309204501 820274231 149630127 895346754 921242429 13492107 9678440 443529026 609393717 135453485 957442103 800656338 933446906 707374139 356547070 874031810 472526487 812376829 603288366 551799968 562973760 99856834 812172145 829444974 917895227 485770781 941601217 464994677 389343472 443878949 297709569 650967444 935248754 195998008 639735194 715138881 65037990 393876446 417826087 667793275 878467570 925735587 201623440 643034358 725137583 207369619 106649511 761849243 108191129 753954729 173702138 100605702 840694719 212093068 39376275 77546093 241439347 85844004 932731114 635499565 831484806 943419355 239473783 560477036 221065988 292421098 495339964 226250539 93492947 193899393 20163021 196242221 615998678 8528558 897180832 56714729 514042924 116793588 116116640 436637535 170536344 586416492 20916248 581434835 682451780 352269274 866625975 245103894 875993015 141337499 903163857 955368956 385684600 861059204 586799615 493563291 474734953 300215086 517748409 20490356 272470108 478600266 749227155 778664921 519976084 645784593 185840271 440075448 636049053 490711394 460807376 673790966 92677161 308712238 969769632 241240857 935426176 766085542 365069622 894455799 820329104 157889104 323300487 889453320 238343847 715340171 69666196 968738369 59727937 468315507 185236282 239170065 2505196 358433449 389981356 725675319 728949155 687726655 982089641 310930065 373497230 115494124 670746826 676102032 877645936 815507528 846664963 
888657256 869442443 464171551 367171313 853076387 59303911 516956140 868970446 272217327 585514672 557706921 216115661 145781559 838279291 684670484 775836082 841411194 982611033 103422943 380530089 484219989 793717137 921016878 394588675 236811473 226347075 33364385 527349990 621239650 459683678 82077642 822263241 3190605 977056575 679468272 779960502 76734322 620043428 643096065 820740395 696080379 486265678 473378368 138289787 477214651 95188461 464426688 856898810 35168728 981777571 670791316 202871271 61369051 33862944 508759892 289162222 433898729 298113662 220688376 93978107 713529708 679981524 593578814 195321839 127665186 161149016 105593954 9852694 856484193 722648550 942475411 380963257 664288309 559763494 215363090 758390534 357818285 590998660 777652451 872804383 544990563 555167549 338014028 34189156 179642248 410179905 752280716 625784800 475067568 16444692 894219737 821508869 355213876 13437811 420042058 956958518 631597208 77987821 648402968 467229918 817178273 391552121 943259777 998558046 267259014 285197681 107010446 817248283 836751319 294551820 89997229 253716552 94394749 438606949 452111202 881242784 404598185 621483004 654166704 52816969 557359470 320386158 454626542 774889628 186136718 537374597 675866340 676584551 477559070 252789891 245239441 253771758 305265822 242442989 734682179 322508627 671458389 603520269 252511457 9835933 855980348 434683865 959478698 94668447 621705585 11325170 728617939 965325083 906859111 19344531 871105900 962137538 79119700 257625260 406773030 761829874 822955347 894641350 27482159 145204541 673002716 59110756 837563791 594526896 855940995 585432650 69708864 305199121 770442508 278769667 994182487 457989978 107538869 543775730 876201564 667682014 118937390 370880847 21529080 947268838 709485650 178321430 328129018 564401849 600027421 325944203 258065272 176194873 900811304 935440905 352762330 402722836 87720654 307827424 82915937 762859412 139262802 207886017 283626173 558211413 559592795 200927417 876463292 177512801 790539853 604119416 835986421 882108685 168724804 670852202 72815330 586542761 364683249 398453949 541566269 422838203 977811826 290327948 915123090 833397978 646038365 43787623 552809511 37042713 549046782 595512009 27795141 24590826 652887021 619006604 15307343 211329893 400809438 511166711 473625770 189924182 274780494 259249440 736533165 924162275 931261434 504538255 332981267 187678338 47885426 80529544 750556005 169496546 955136985 52201966 665262157 575809460 614273427 21703009 469325103 242977414 301627020 621732050 832663131 749712054 235403766 165191265 596109629 350371420 400059238 880885592 508035776 514459537 71870075 193860327 184473456 405551162 678524263 310471493 342375109 287333389 751237220 974816301 574529211 244630197 849689946 725069990 630195300 54595712 385152620 130609252 451477764 736266710 234512168 360559074 491968527 899196774 122339884 38240416 820605672 226189197 38576651 364522929 836020484 163279000 634084537 297437431 585277865 146315987 562400566 459885366 178315387 179824829 317297738 340857466 612603469 593859523 407166041 547781396 551373853 703303016 84553475 959076561 117279059 624336213 535884696 353715450 310151353 210548725 997064044 91110931 36806424 849657960 627272011 134388754 464819364 814213777 455824121 291551620 133593830 243592245 708742853 27264758 937892287 215946512 610222180 917457440 393491223 84444911 866190284 1668551 474126099 545843953 19351390 231694254 570699807 466668649 57272603 640088726 147355594 670394978 145958050 135206413 831074990 709764971 451273034 465363591 268267515 732442556 823970867 65427407 684938644 94109957 721309981 454026650 302213259 264581378 468543937 44625452 122956124 411533162 808065021 548835625 958657006 933534576 800335493 732862821 498901954 706800091 266003622 973708322 635610094 454903795 934293167 842099714 756984269 387238233 959509026 379074409 652006502 1262808 183649843 611214363 749007866 454493231 904205448 441789200 383936665 860614639 392642275 695134250 135398046 184084325 977221751 446399469 349345898 534665967 388875624 736239510 567360312 876765558 60029283 693464606 475175841 73076999 767888992 428083099 866222141 953931322 799165351 893111267 270478601 195579838 965032780 503917450 77313546 605413667 130534706 554205184 353732815 205151725 518983681 284544561 608776351 583537647 40641475 686690269 726994398 224062896 610526405 876771081 675301797 450690236 544906631 864979704 907172115 394709727 727237919 666791742 731804914 796403746 600349092 119796664 435891398 809217736 981421167 759014852 306187918 388046575 953494408 391583243 729594630 758451319 54156311 310028249 727732587 204408483 388957173 90284083 749439057 641372114 239314383 43177081 955433740 337864780 673746318 758779644 526269620 307450404 450119087 405304841 893510035 9141455 642664110 821826252 818738325 97896520 802051397 684728182 405890512 867850546 740071971 161424531 169398345 429311977 282123682 68580853 733114851 861794910 862396601 487484449 282017240 191412586 724094745 343579961 854011726 202985357 947946039 441372731 339577770 875802270 147022130 537598788 852324200 215579647 186004800 200078384 146662074 929654961 929903086 820718524 690625827 164298390 631967689 245848221 769415117 736727635 534136836 104156703 780586741 203235199 691326200 60129510 610949873 868038574 221661778 936667152 120558468 835640882 947353283 166297243 499298365 385483425 437458775 591703224 482042650 57388919 51400241 602799953 63536785 667407530 362747788 598643579 957906210 97678388 40009770 475361641 456655260 42753664 336359083 536547825 391914289 632614976 258955940 869374463 227779719 542181411 139714170 862979436 284261576 386818853 858324386 7163055 614605243 722444873 823633474 254728416 780072110 317824066 467999701 959179551 710525446 299594127 827509592 948606610 381804435 570757630 388271784 232976970 499392583 708224887 90677021 847882776 472951803 433871187 495664120 154388749 813219056 493002447 372678891 169253597 482665173 196733406 444593667 139380803 296122910 413991492 286982118 562116330 254709810 667956169 966568879 881466242 92008566 489730106 164471481 917605507 745884368 36682456 659324574 302849854 537192741 826595292 95523290 453224414 675231822 692984401 110597207 777426645 431222965 850854435 842928078 488887768 83488796 946087613 250864961 111677430 137371574 502908418 472781156 28721852 301224657 910041116 202018930 169151740 188419948 201753987 172291506 73960742 970683168 951664592 878785416 516375776 318011279 586733189 101216989 61903884 895861879 535371353 590871129 640806306 137446792 981410186 531871525 557015677 677539140 663075749 488375789 819505628 63288348 331326139 570530378 401967210 205422398 15002661 898859983 110655463 253325516 139402073 480959478 675856903 916066927 408219316 785550697 272023827 888502511 174631805 360086877 605545573 542852206 122182532 746957501 742930911 343708755 401283332 811213451 258350282 625000551 117402659 593173247 622023640 117630676 615970740 610233521 797667826 679007508 375663549 803399155 400590054 253728236 854243647 455522364 416323402 158417495 320101392 519074946 118222344 583153042 893810712 727755918 520076356 362842378 144810043 572916309 428686210 901279065 325354215 433094072 105098832 78279639 522936663 211106838 667875989 114385987 668498500 378352822 751748671 852034134 844894095 100876166 25209290 855807651 790919871 615318880 350000748 958322901 704772186 967132393 181700836 845114446 245776545 584713122 287176322 255842012 863409874 114009024 304423444 340728775 565089813 827922984 289840289 19155446 599388937 978077752 471365197 701877630 307201456 386943000 283147044 158213861 314585502 942489977 763484023 136056518 763602136 876170931 175447574 656742002 827695131 243874577 881598389 469555943 546076678 149026163 319834311 336117431 917889976 494005612 594095711 225313919 991970927 701703398 523400551 939768053 794837315 674706810 726187699 33616363 204395170 227930207 930906898 918394985 294472214 178533303 675285412 240516760 263629063 111571262 81925228 67002632 890420353 228377334 298437976 976360709 108343638 109468099 891779810 572076665 200741906 499447002 47363363 958087287 858293 790919405 77880745 282501450 104297440 27796455 189772340 145497159 45673214 649263010 109201473 737534455 144612577 887645226 500733399 543073374 388599688 742892219 988433733 871879233 379993729 420471881 900277085 859159208 641388227 571915349 638626467 903483040 161942719 139211177 598854588 353766892 327695759 427490022 508428340 634566371 478961660 58370954 921863348 613462312 263062204 268801831 337600311 817924970 199572714 445620140 533422007 646511495 212512708 916400226 825020655 868539633 790587707 652519893 558307644 858309497 566276470 752781512 866398175 538536561 82763915 559667925 692303264 498583236 849179146 798269253 595436793 771341814 165314972 431810757 7598341 981579303 120013072 885794526 50593110 196716985 93713255 300004313 243417306 851063927 491405837 125752566 598976643 338149348 306926329 628049645 349945624 872883503 297249275 412659623 466777059 784090815 74167844 397745059 21721868 470799025 661967849 407234831 897290348 789529418 551759655 936404777 351316892 743909156 255492354 930295093 770178840 735911496 518687261 140063866 596500680 796566992 762971212 567895087 529752235 882270685 566307678 530422129 602595284 854054265 172919715 221369680 317034886 405442939 761254477 621879817 254003420 968270014 147290386 733889620 527197499 156061739 553980309 224529290 737171512 955122265 230436240 981868362 51533284 66893830 930698219 442311560 183995213 435906502 678608164 660247374 837894202 691252283 824594919 474976237 854987473 143888193 922625054 576351889 798305202 204957408 130618423 250131740 968703407 366667914 300067764 681550887 104813016 222871734 255883913 548699699 588630151 746435252 433886540 423523860 259743002 283127026 82505190 
750402585 423449923 820454330 918145854 324545483 389686244 944470563 208826312 770789962 208910869 733192475 886523281 205379815 65827813 712647473 855316516 554480413 463009134 654153435 481382438 250073681 665281187 876507262 371861871 89290787 268087741 347643475 971205685 209011462 880422591 855293131 130629413 657511707 630599718 962840502 392594401 427454679 655363475 526909544 773716108 754315196 657563827 860257401 194291798 340642516 929190635 349224912 607391203 47216674 395716374 897273760 725341885 472446024 861932358 620143383 932056267 227030671 218818678 412997609 590599631 172551673 209382160 624623047 877435939 670800112 421768849 645826401 396805010 66916557 145888050 390290504 788626852 618856139 834391093 7615568 689324749 403128437 871576341 798006618 284106472 922927245 423274977 505232303 700723965 143430061 171490528 453704133 986663926 677391163 840779560 401118217 21568128 28375057 882114851 979155358 48427206 238438390 477894151 618790309 252321113 502107652 652698258 881584067 260325104 448639706 228830422 130818592 880453935 965205865 130325890 572067146 150937785 847398064 494299190 481578283 616440186 12186826 850700597 592807522 400132861 171278008 243051729 773797871 613954187 778216849 416554728 283653319 962724590 841897098 739286050 659721329 336297721 53602420 216011284 119976452 407110427 574890543 339117757 33669067 156643390 526512816 67916589 163585972 339804685 63588263 88941824 229093319 242248133 794868990 767254623 486108963 86977048 82572853 230585641 602091714 62069281 562445461 806017491 312603716 630991276 850158731 984101515 70833478 598740594 45685343 327492822 828622830 87974934 974994348 898363943 637360317 475841014 229511255 169208805 814067129 210897249 458738378 906432320 603396480 527235528 765427259 567231136 829774663 757702835 521914692 255495296 236939008 307464963 729246705 261938495 523737897 290074721 659405853 663200048 581647007 599099209 279998027 804835488 936391225 577619304 424398865 11029812 408443985 767773476 897158529 417112267 136371570 930421557 419147740 891629874 219341693 729186278 609497705 159067457 823818115 59409859 859499299 251953540 357829776 233706465 646867789 218460315 469169036 609730273 733419943 326536288 567822722 341397871 251553230 182222126 566326692 924837552 707365583 907170276 368670346 592472647 350900969 838688085 814933683 958786770 268608332 603015864 721915212 156423798 472604715 615102021 962392636 717812279 448896261 431890380 840894236 399704843 634539288 908196137 301723401 936217779 955743181 125651957 707412711 599735099 213682352 288171563 324286039 37665371 844602214 204302233 933448117 692205925 768732 440144146 966215962 58441729 598631811 329740798 579481083 923478895 223704900 84556171 305923849 688094437 526719954 881188230 512371960 926674680 323526627 913434328 217016992 4113858 914336573 41053858 420845864 235785419 113053436 646695023 477572642 533038418 470956574 581271870 269317584 198533565 488107519 229304729 588010177 871690222 929261815 238949797 14051247 119132255 924618736 169974968 45970288 113214866 363692814 715428032 304863030 21894890 816130304 931651260 140587064 469194601 14822801 926270971 436199964 467808576 57524839 665668907 974792062 827973257 351381422 305116106 235928928 805494366 222468273 677519272 870129596 912682074 97728667 97847588 631832813 617851136 117428861 521125314 849531928 686551492 380928418 981300383 921869737 60960392 238743476 798909696 111056657 49030974 450953166 772695499 438633529 536002629 403694403 476226195 4791311 258125039 516970603 230813231 909447065 862253751 837452853 296755742 330668999 552605493 27755275 639261463 764279648 518913804 997697352 443020337 634845283 501489148 528926134 376682971 146788644 390638219 562959371 116211234 353624654 101748863 355263554 305458074 414258026 255730021 292767951 319512575 706933177 642761705 16317300 856333258 293152428 910320260 613518448 988730365 771605792 177946754 559532190 708946944 202449481 467261291 249462728 488020810 978595447 966050260 920214138 313845050 772858776 388140465 70238170 81060923 685018319 38482459 715771554 663258088 224490820 95961074 134873290 109295956 58654191 522997652 120494254 938946548 956124508 782417171 504828465 706333505 814528204 284207354 599682049 398229206 968077199 495629579 453894130 782671619 347419981 146944594 177212138 774493151 681315074 711730516 329981598 637879158 540910287 135356860 501873146 842572728 838848160 170133923 804613260 140799838 85669798 677732996 613220988 565268268 662814972 352557142 44828478 853394713 450816332 779262067 672403914 501228455 499488355 699085270 172428604 245980501 289411143 152890990 152802183 987761599 178378721 884701432 513902381 718735575 322323301 775146126 823488440 886461125 192929054 167926314 69798990 407044476 846236886 457731023 344266094 848870009 782806485 198432182 718484249 662518573 69993707 301212122 435140063 198045008 690847949 72976532 379916914 716606589 812406440 275445888 191880860 528722203 658849457 3065000 250895857 315051989 550396031 101389447 38983736 916087556 166653717 335195918 685405200 709559369 712249035 397538712 758183568 574505398 103021737 609636715 856215558 217522679 126234581 938612796 830607394 672591518 286509438 73668719 200417543 919527202 72005115 595992065 856717118 788144996 967281712 677466054 610199112 60155857 732541080 14067674 954785186 673910763 775241245 714632112 569280134 596011402 605531969 354706261 658139870 214950730 516207878 799044342 310431930 436496105 265245333 898460632 403610054 398257151 330514267 68989914 465706471 624000268 750864074 594888586 98635992 886374453 730300001 572685851 195386276 954116435 750384552 236469213 444357701 347728714 310969526 300922992 988497542 461176192 616799920 10086228 156577202 373902449 154500436 471852762 102706600 277841727 568884633 886990777 850664237 174306556 342775748 169051101 20905661 976973851 927985819 419186142 489571136 266664607 914157312 52388392 73306535 350794481 64934448 240103080 916624527 191075592 442500738 681637925 435666422 893697017 138364561 618103318 379520848 817679741 902282600 661366184 556033771 180329870 850844102 132242028 416100303 683712267 618219783 827107533 905127637 893296737 388734231 776592932 41595895 147192182 415944050 445568914 393254513 132346402 988271944 946103939 261747933 811412851 823460443 519648217 641259945 797252756 234794026 519695088 758190020 303134777 870714085 304456214 242281245 505540256 107401130 754084512 369833834 409065286 254174115 454147929 151916657 488908706 269012905 636702878 953643329 946775804 622143270 304226640 853360284 783209774 958324213 103030006 977966741 116731464 82546286 980733349 489717031 708584390 758365646 135127553 15516423 94416243 872434748 328394820 680796268 181818404 648405510 231136979 993944111 63387784 451846688 276526997 596021048 764790159 1163736 272187685 287855024 317875780 405198639 826434165 733207361 574234292 7947418 111231276 48032299 290256427 231777382 90345223 600358363 493459419 221785274 782863308 909465857 713357606 606988771 18059934 751845763 831192906 762625662 100400445 183807383 105945058 71888979 766700774 663843483 657687482 245237842 40491496 106972391 339826857 748529411 643829843 990306395 715960612 463436275 763119242 951288699 831596019 364267878 729245910 136507697 460140267 415173575 567553294 734005910 909382971 955316955 363136904 217794856 599365303 471084954 84859876 60618680 629561152 129879606 717776506 636394088 984233806 946020215 797154321 254167722 202617958 120837122 836761919 923903257 943634366 584446591 814844021 30330222 380876359 367203544 265390729 458731115 612839250 222771521 516669204 952433166 677333231 669328458 199469481 981037965 773630074 967097431 440482303 106637710 998990108 947238850 648695529 983141152 351220191 877685299 119462725 936398118 966337214 398548144 295825483 21729991 759621604 704305375 938115763 950391600 339272038 530993311 129334455 29329826 743350727 321777209 856182157 974838000 991635541 925484409 648804735 817106409 935342246 240259469 792474885 436597220 594621950 616825323 437682799 864151360 523856990 447574270 898660686 902513862 90022654 122781669 562561775 717893094 896486647 585259286 17859799 383359509 515670186 421921649 97071019 203363155 813343466 546128524 560592507 888347188 54551169 262828791 534538797 376650775 702935827 296503378 569102646 529715614 868510901 193672868 685283266 709363843 440455811 275720318 153392518 248189690 106890029 101928183 628843849 497111960 138568735 323590317 292832057 995840452 809841061 969236927 724793812 33239495 961148757 285446080 255727535 904821000 878455046 485253888 517349537 746855580 282891577 340833829 683824088 384163131 734879652 817676248 300126813 236812538 308951367 594892639 66337405 694000557 322119000 157973353 215366390 787458864 646560871 631272024 160346355 619947603 279434934 709687957 133010031 17510741 523743384 315924734 898697201 159293895 626867216 653033691 137719787 217658841 764807049 505475517 877937793 332133139 216046208 824840364 486198448 40152707 70016793 260892538 631662021 464044481 850775574 705405772 314213927 537331697 14863267 813053865 972916276 519477754 335548653 623140163 283954950 263054616 169571426 666646855 620087378 591065091 541696776 590283757 292267921 479623398 790968287 592945213 26028508 751361989 256603742 178082346 313166075 950637711 669915689 580466127 836404622 133258895 592505402 910116169 926295222 202025559 72148445 349150159 168243211 201987153 753421942 833989863 216192571 484278117 589433623 36016221 420924170 312067049 884238056 642981062 247367687 357091322 306675027 276154557 382070876 542225499 930624980 460244801 91348929 167197058 692488349 685567925 757862780 326899731 149487722 816189016 762105374 712061584 768762576 836056248 969802973 447218270 579868664 788939110 130678895 327717153 586542341 136185838 378161046 
401283957 11918439 756164074 565023891 511564212 504642428 307030970 478812551 934927793 937745755 445020452 284065772 127460797 278450285 892240282 672181392 77652508 915870726 656613940 451828592 421236430 377842865 189501904 755863450 86729753 776723692 148265810 434159623 582545064 37243451 501917055 227450425 448117039 932743309 111140429 250069743 538096531 771093277 31924073 818460437 526748202 584156594 66533158 653983610 49544961 512666416 860733896 234390381 914544055 370383444 219099777 982438391 886998666 186056639 553928039 766554887 418883639 884550318 192428847 152636788 421986654 921092691 295344621 992522931 717246614 269195444 105125591 648684620 337482004 389432415 406321725 575191401 340916722 158316276 550274770 316263933 95947543 295087601 956403449 652502768 169838835 368654664 826183226 286083295 575568015 728523321 318568313 486678529 257440593 603846389 654670472 397878344 954752965 43231331 93921185 997661083 352311424 799034117 692520667 898824239 367218308 348858690 421718724 256505526 542118775 793289721 200279844 450282646 165715661 791506954 16413592 323642909 4867015 465443428 654390794 655751994 691853835 218472585 74673635 898330591 570433669 178665362 842198060 994168559 441775606 430810288 319794219 263001890 854349263 72432314 890662139 228003860 182427462 79966948 840745010 71347379 266506887 781245120 372582274 948016087 126262021 742105541 679387886 332429197 245828325 228018681 315695962 780279203 618807032 543758541 109623294 556793748 250965542 713059592 322128358 611636875 368064303 645129861 354274531 766427470 686845943 447904595 667118532 720752917 56849291 533837674 736330244 530699459 653961815 338603457 166887841 885608392 465762158 419399678 306957310 456742508 425487405 820425998 110923752 272176670 527476187 711535821 346569875 80562166 161464852 977639607 821281991 188132605 215264143 570722690 666367450 214099412 521817456 361209484 242603809 336125334 310318106 787052765 593081872 238288359 575551935 453391554 730477240 252444374 744214814 487058345 147151960 668615645 852483202 49532353 200476127 621840383 106249374 299482360 300657558 548228257 724539851 489217987 129980443 162756634 244118435 416020199 777753190 479744541 240062268 839844022 866095961 672946737 885345268 859019600 283279234 258917163 680923340 424963454 972062353 734273570 74394432 240663089 114885425 370862993 574301599 344155024 912904786 352610533 320440264 135892495 851548225 650316920 100384700 778621611 614421234 939023441 908255519 286324695 353827538 424175989 192661233 510274959 977694557 307797797 6349921 262526216 782268320 859972814 73276683 299213423 810436273 682638998 498444066 210121233 829044988 295238589 33430766 160202896 753866872 565657911 443270179 948716201 204364547 608054121 188994815 903165699 790644737 43985472 667011109 581314323 657605005 108033376 529132915 553349713 540292990 750992999 238286467 817177859 945911223 801473051 42656009 481504951 687843999 398250938 17918232 921844378 622013487 229243092 279412312 151328900 985791465 114435587 150734845 741328951 728291493 651822433 427482673 187271862 224779311 916940809 894236294 933524987 97295409 793934681 241562451 45720360 899061148 975927962 702179290 758685769 965234784 468150540 90456583 697307542 705976106 481287671 63939881 688619469 349539256 218664652 510876638 760497062 845546248 984598090 775975747 135708162 953446487 632428675 200392027 839575540 565432246 580057131 287948212 781161557 878282665 676868991 566670376 193346751 151922679 472083398 151040767 187406193 975193944 963974841 129175427 922286568 238324447 745079126 259845067 903256591 904658723 614381497 572907640 430569663 230497942 522262402 985317485 328264367 208017950 274474089 172161509 821221059 913313516 947560005 393265913 739389192 750419498 355943326 939711717 430670378 470744855 237413709 974954758 252567278 875905305 479709470 330258396 531059837 336227235 627995933 842081382 728339221 115958402 152019227 521237112 627191838 7795266 339442737 328955848 47237704 823198659 479516124 548238241 260208740 489383168 634705197 177949715 287903935 37890783 829976433 338827328 535036943 988881264 800435463 256472165 104464761 338616928 243604919 708384661 588877761 886008820 223648844 239857227 732867406 539146451 436017982 922300851 64661830 596125166 999994821 781144129 313085968 59582652 920447946 636989112 924457473 193487538 468483660 131651135 975337134 97620193 806758695 127909739 544939923 793205039 870827965 57896436 193320048 95533030 481039706 173166633 555359773 15047081 864713324 252172512 778461760 594023988 219771705 115523635 176845670 154766495 925306347 279089363 186030991 645312604 159959147 962050576 497881059 810892156 3052003 668417743 383155072 429161380 111322612 900792707 980574190 634849782 722827390 116246791 665200651 507714773 245653713 503346498 961730727 537949089 531605720 323423475 569174123 11260138 752778385 979313184 603752098 167437714 63583707 753927368 472636200 995807343 280086640 334927509 900388360 259788880 593948176 651239463 533858528 339051903 625148183 104519441 159624432 394016730 820472415 90602982 723028442 408346812 960474849 246272661 301519098 432370613 658717065 3237606 629941036 191461442 111295663 125516795 861709179 558495289 817070816 976441892 12252680 310069813 746721811 101732959 569735290 350701134 904315368 123103230 470492557 989363601 557006122 485079667 160965052 482108967 775698316 970423148 382614316 341656428 637230586 162915084 185145740 51753914 30487429 132907044 364650063 453026678 571224664 872838698 441043933 413599449 407031771 534147385 618488209 891484155 110368665 170066811 655773872 394376517 906806913 18687772 347222400 881408124 802199843 276398456 435758408 669805999 20701473 660675102 973904940 6354855 518721237 426439509 633301849 61889200 791127822 160313859 626880808 260419910 957753743 122443858 986406629 816551320 848418094 541164512 8153172 764206322 75800338 306533143 747446704 521682895 254273107 162523239 784843593 331471394 713664332 870468914 713990766 959694841 82639297 209705424 545013072 881955496 817770340 147443049 203533447 280027497 790302218 217019203 883149918 969096453 859025667 655622490 135828107 473673206 960990249 706087800 553030930 179390641 169325971 105874442 322887206 525434432 391719288 613281623 119093334 817099605 199960348 170042488 489891580 782800310 35576289 479348212 635573063 700996328 147888369 847248393 725695725 966240186 403287872 375603204 428568506 638764246 296518422 33862273 352232189 716664873 974199304 601286995 944744151 102177237 270719723 500561309 487756750 939411443 806727997 148675495 590476881 39023626 69267753 795580125 666139252 741069576 69390398 308213836 19241281 835581700 414218334 589676409 685814334 82390267 691772253 85419945 401229101 557218331 632614850 286313388 189923589 107837221 930876922 313257604 805254542 198916651 493047895 818464104 125210925 567054713 185207641 344534725 556992258 488583025 76520246 232345598 591001168 211295371 660665699 893037814 630524670 905382695 888696572 95001635 262291065 725140420 382500840 942716294 213492251 545546112 709339976 501251588 167766364 837951282 264569172 958826813 971542957 3904362 597487068 84986461 327394475 848759583 233179218 48970472 649949156 506053738 78904126 481122891 60916854 390268340 215835727 800080001 71163299 246409591 779449928 821566508 274440990 212937064 362267795 53045989 41668924 300172150 230566738 451686692 88359538 359084519 394539016 60410832 493813425 759878100 399978827 709438283 132193541 229361879 201175162 913775745 234229259 670065454 21598614 566869783 712634468 222434371 785856083 739590036 195606559 630116592 921482901 635408412 859146497 703563038 597945273 947236564 208867607 928472709 257505614 323266851 284423270 254756941 22540314 511611162 635128008 468946127 86355048 634986655 27477014 158023761 410783634 838357543 6387788 63244280 46134969 42295375 994863127 192977687 737177720 479046367 383534996 479935440 598938241 918432336 393161678 833477182 327637246 588137354 908609846 268897955 403306521 277975611 418915390 686533164 686354813 928282578 860108064 900223417 58898224 498066626 486961446 770002038 673079566 162057209 416849686 239902954 831436424 488086706 217958835 644154155 93026504 680299990 891983755 343819687 335581183 257624049 58098893 292340480 65281032 828244332 916789566 531449820 281885328 178991506 796302810 391590755 303667160 415719502 364439625 429718323 919959048 645513495 49959082 829340842 141999701 208129834 39281767 630288124 121125821 591902240 443427825 188743840 54784663 751605265 399156334 177135703 418494061 448109687 996154845 204447984 155081571 73528942 703764861 367249187 955508994 557898891 528870949 385968720 445141957 366988066 338335490 13744071 583098419 878084777 996560158 405022179 236126151 786456503 984436856 63289361 620828991 400560460 488760907 979768671 580833254 210683583 866368300 753900150 502025910 928246698 512437721 832369652 590378277 893557997 157632013 791559248 20593258 376386334 554164364 389387071 652924054 543641115 175913678 416552554 955523013 295443977 714063647 597535850 603644821 765474624 683183293 805935410 685839731 992665873 891826898 749685274 491048805 441283964 745750097 243906366 811751970 923524178 399705298 996246852 466253568 446161441 532395486 718603210 974159189 791236878 210597152 765568375 80972116 726020664 150857120 555495764 516562112 640395724 412909748 70851092 22388055 536423011 4237214 815137068 360740873 679497356 755242963 645489898 152337614 528494761 235717568 173269131 710473315 696250140 223077879 543737222 790621791 216909190 327350370 752230124 223124794 759846386 418927662 682453132 879300893 220263080 895222766 218252849 129914132 599449094 532465562 923534587 319611161 71808733 428890870 839370061 618613654 385283519 40908016 617142074 143145877 204830258 87407840 959460045 517865766