882531511 385747723 387935950 166279394 592156432 151251699 877827423 259211680 244525290 1331461801 625455528 938345145 42447824 264402151 176716563 652044315 333808435 215377954 470974414 105125686 453737695 161434635 1496713973 691651951 1056794578 446697842 255689125 1064814761 745741659 322848161 272236698 767951043 509727383 402254032 1681936215 1341481387 224843782 1104979236 534826110 1073384820 515117444 293953669 704133131 672647762 470071451 388704708 737186841 451808318 595445290 255262385 743529034 541140989 712674095 1108160413 532084227 504382904 783514137 990303068 109497951 930446158 385296551 815843212 1525682295 169163562 703365398 178150655 1458778604 264246248 855477341 587419461 534623649 361616454 965146792 252465674 810712897 1013880224 410470040 842963255 527133800 424094404 362499113 523424116 778500962 98419452 58442811 258908049 556481426 1201515332 726589397 139851895 221376791 268608153 739527165 253018328 899280773 425489331 324573218 688215593 449281568 461816458 463289100 35803675 499177192 1077535556 253876361 770568804 1503119446 546979946 95695118 946659241 442693939 1418919201 1302719149 675366514 580818657 160642171 392863694 426988418 1167250067 125221084 597287459 1270995216 836568827 527485284 756938130 48976550 670039213 519163626 339552028 1221454193 334643386 1249746448 541756330 822501868 1025648527 51579418 902203664 45215110 524315479 178843257 908517651 573424021 463970294 824486545 1434437927 779384493 437907803 756059437 164275029 1032840457 1114630677 765589581 670343543 783163558 590384772 1488580135 95409036 780683858 266663296 456333569 578516061 505622423 1364769743 579779508 501813007 799313869 1100579766 448495280 492198548 191893072 1401672658 724463084 528450468 593315820 717205036 259350172 734612194 518752156 649857013 452871575 451181041 259387555 410972551 970508184 1059220374 730454416 992872376 1384237884 715029138 118640601 574015501 1299049183 232448149 539266107 1047220198 209107204 88717636 1000815152 820680999 1132815404 178395676 452722984 766573138 236540693 560373756 1043943226 207213922 810610277 361076801 981111331 1157982673 537001341 550023141 936217234 618617931 316927452 998591640 585416631 648814781 872637474 489267196 1120713204 338891896 1015005329 416364851 740756413 147972956 1106803320 281186063 501350676 304292345 238528737 720484853 782956340 723021776 890278620 407212430 706588068 973423321 641474829 585989474 157664401 131336737 688386031 109802404 313838913 360159555 580889664 559197209 1386467537 925831498 940182079 295017818 412937182 242944546 750527072 855096909 703836568 535432793 454667100 901280512 73603231 53440686 458783019 669054342 1152206698 557916014 584153320 1091736120 497425542 830920156 160590903 255404515 704756360 445894125 770717994 307818361 867453255 693862865 520427365 668272764 905459514 443652362 502878364 429229563 277853385 627633350 583687034 906073856 1232572143 1115204541 1223516523 410692059 1104947787 674282633 649477250 359393316 893127716 300958204 467246640 443262661 219963797 802408798 630209779 1319143443 1080594542 798548087 369535062 712888310 244733284 86484973 48402178 686821651 456778263 887869527 305216687 57492792 413684605 828914807 712032589 103553738 342198977 720876990 562245716 1537685620 392541463 813166990 431395584 864545447 1123734682 177726211 785518451 558280612 870416398 703504521 498816063 538631318 99144728 157894894 673454580 758506662 468685933 90145065 647997373 254575454 1014078783 504596123 1094485654 743814361 738835181 221050021 624287683 455832896 115944511 472979619 128190035 763556899 1038580983 844435353 629128708 618017274 685741061 771388003 967343037 409741908 291017316 616414876 283799443 749957423 390930313 271086310 230554133 749026985 616705352 436363397 302494589 426730489 329205698 493331593 489587312 1389813917 364917216 728620622 267738437 239468074 1177151710 752897238 297533903 488253157 429624658 831758588 37354997 1097643697 1003928543 399023008 696029498 392412644 677591147 661797599 818282045 509571621 827659264 407553574 696655345 1385130556 232530243 317821401 370158113 510615186 1059465403 55274355 492635493 660159629 81207519 796811991 708021434 882418277 353034483 901486139 235871369 609403550 758836843 605462427 619610066 217322164 893495174 669582779 1075259004 818945276 505226612 672561766 270531674 757044117 627001955 497012621 419841745 581214224 1107234412 355545620 719514995 246841318 1063047841 238899343 424108909 748273885 754777434 509317452 660211081 188703995 1108814326 262762208 732305911 260687391 529981390 653951368 571880048 1029499351 630234700 500338231 737441304 462654245 1209302815 511084695 102590268 676447705 868921958 863201479 290279464 604335458 660959841 398368334 679950844 416022101 548651626 229748399 515425431 548853190 985468164 397046992 638480727 709192365 176364971 901408296 126213758 925047691 411335124 1635641476 982697983 139804692 457848973 870558991 493081940 79650378 561176384 544718045 229854673 274775774 820086944 428663180 471880956 312543373 390968796 273900527 217396861 465942196 760249298 559852474 710341988 377828635 1107513537 1272903717 580849053 68983511 229173999 539217403 874284463 533466426 848937678 177552321 729727610 469142241 666679046 366026394 871830906 884156338 582999094 1596832016 714007956 857379101 561807340 440563582 1068980948 306638623 541179257 215801623 1012636817 765478022 801280429 856467092 554834784 171357151 471671071 449050273 817011661 1485083335 1538517873 197940577 1464163261 1465442240 816093837 697523520 1214725377 364025615 555266493 772545950 979457152 447516199 183600593 793952375 513881113 543151704 1098461725 633477104 485246512 792231488 179716431 397263397 1248293782 739687619 793106219 599828961 630293003 592302951 579950929 769991132 310456190 445015119 300190985 181349040 1073012067 641359767 482538435 483711614 685802248 1015993236 406353801 143829876 48236919 996226727 816740424 223693829 675460009 427948928 477838386 139710113 352843083 874011628 688579477 649636417 368493134 275931565 286417521 288398346 704324907 834338112 330611947 406268657 799134722 210647649 346521449 838507317 473238564 611309062 1236301390 136783185 750545887 576615326 678704686 542861364 765129138 389507186 649359595 332562410 432502314 893213263 371547465 1152612221 638471858 210315472 99600373 677661041 55054652 443251242 853835742 254395237 469290371 553914011 186958302 520501601 691751360 711741123 1154803464 358814871 976398443 859820105 251058514 243846241 720339531 895853670 277514375 1104443553 733835250 406065018 653709747 988497175 278949440 393332559 1178450168 490887451 254633204 72745824 508389188 292945282 568836627 528925418 1030737506 511137603 541787187 905979386 1446696880 338273913 1131684403 441404695 800811485 537856431 1170207872 562438077 459686151 556173447 820728067 149673920 803592517 701494431 653303316 622526633 834746978 683371823 312968097 200099292 217717649 16893076 195359709 873354323 602600773 79987227 427802070 72479807 123752783 812330248 427926375 562825502 702533123 621409554 1554879546 1130247107 311081673 931812893 802574887 896890761 898837138 1075696557 526666530 403448039 447341995 381497495 668554782 239017347 837025245 837392297 370161159 249542187 356912270 410587136 544084021 833863696 989801010 145001411 904405746 1001683005 639097727 591881458 630946163 260659348 592350135 152207070 735402765 257785021 401536730 181073748 428788401 354491983 581458252 399922538 494343069 765706336 180096014 414632156 64477947 811718660 70289341 684769935 467748368 753769030 420379525 898565852 614915603 770944003 696637120 311519068 56423668 1106897237 992851665 391101003 389210832 221816972 690601908 298131029 438483194 413818843 453482528 524710332 834116834 544978232 561775029 496705645 932422479 327714678 57610015 803189414 244774948 236844291 986664163 743052388 227872079 441542469 181339131 391611740 918090351 278053285 214312353 1232418439 425035208 458549479 1086971182 544457831 451653155 1635849353 214871697 193586264 74017232 1071927867 387318690 298722355 579489190 375923844 606581608 96898470 1378821977 619610137 756789086 530495924 834582590 279455598 395551199 630315576 1217952241 672148580 600626688 922741104 357894757 919338579 757378858 861477657 402834028 497091624 1009640312 477593391 680130913 887875159 364440344 1112708933 278287564 363451646 114438376 583002942 712464030 725595277 271408427 737417272 1133329561 605493857 633204607 224457475 1095288530 428858572 467052047 1319325342 614615990 179531008 583156207 310887859 311189716 160601136 218184205 589227666 984992225 822814947 477100302 1456405837 247751180 271338026 484392329 533673990 586161137 473296292 239518563 500825138 625176623 241287229 572543828 376535042 981974954 882716978 353841834 207350594 843808993 943885982 874360815 308337456 959539592 76001091 721334716 1648850579 1332520037 944390532 354172367 158494036 478855088 500916573 361622531 750015679 374991328 856223389 482934472 853023853 85360690 38160688 821448474 486726095 726726406 260887649 254299490 741745742 1259635164 720739850 640741888 95645479 380526982 599222446 499620006 833121137 251364434 607690905 720272353 260098504 139645136 279387487 1151956156 335945606 94007280 643900869 1427973490 721779826 103048295 703278991 829082240 73654697 682520594 789920604 978417938 746587145 401750623 726073614 1061667969 310691987 1376283594 763064772 598142283 798587637 998901859 407494551 318949549 708280962 455324846 595627953 94243071 412610830 778524694 268661219 1416444543 1160641527 576272801 505844918 276407294 620616786 418997017 715895811 1039172468 967449508 753294935 50357681 214217345 848558029 1157877088 674228279 340993150 350680428 1144343870 600784954 849800899 295385046 818569992 903211474 404308732 921318670 121607001 174471567 1044829988 309382407 438972731 1058725494 600242284 576555074 996381770 634025621 789476446 1281822917 934245825 343493063 356619561 945484066 770006388 91185896 337924324 464200017 133220108 1070405889 334263164 1068956069 315297868 889235381 302521261 685451012 261008495 248143662 299654676 221010652 356497429 395096875 554776871 1113700511 1151813485 198958690 417215858 388008517 446701016 473472828 846324238 553390847 452635764 439322859 28140863 179893904 866113785 562195558 228621227 30258442 1587228601 246464215 1425171210 358723711 569593114 1423744675 929874315 186223342 324313846 347031529 328717160 624431998 891630720 405569659 989989681 895433412 1019311789 1217286122 340921445 629777980 516869960 1639280547 844793568 569318392 157894706 891222493 525943675 1257510095 817187701 318484367 465768454 175660547 746109774 1256076059 699719837 227767629 526367139 709335412 216860944 683842510 898303184 792350290 388469637 618116314 447760657 403702530 531885353 493685026 586068661 185383189 632313610 418272232 1073791304 290277903 170945011 49289285 489695907 564350673 341690084 552978819 635180665 695898267 95122691 259240575 879532320 937922960 367343090 34613222 161742682 175117367 1025307682 424272210 1024189961 1202768727 1161623190 600288384 473145374 335834047 794039366 437450089 908916517 1092085243 237268951 920502208 134909752 304528342 278094763 140207321 955379425 380420833 416767638 394381800 697965720 264781701 146370638 148305668 408337828 1293163996 990131534 372790929 267275076 897308784 436498420 199762835 392307067 632185435 482388985 477036672 798164019 190530746 961099747 945399826 545845835 165935821 781779634 436111489 627215219 1006027341 884314374 655581044 534923382 194594206 887606748 130046594 373984258 629485970 845697066 1030879979 369173606 1720291862 70144151 593938217 965550567 991993898 172416616 483726149 520221491 723540749 634811890 1186923335 633392960 294994287 886888208 402609478 520176776 192781517 930149499 585529689 786627701 356311650 562301229 710795875 315652563 615924397 256033873 657997039 977211614 1102729345 391566650 84013550 847335972 595658608 409192070 893316818 368341629 922928617 1128600916 390864219 184956116 1045691471 612272436 426877856 301545787 870064480 829342761 780024294 128525136 456048110 148029381 477761227 194067558 128120117 892794581 351587849 193819359 553105320 237903163 722496632 511515196 559523523 583172903 681439401 191297497 251247180 312233803 507603386 504375150 39238612 368293635 35400531 823716595 482077823 1522703394 1080914762 1130670460 1013262000 418752119 365848906 221781946 494693864 496216246 832998818 507846627 541679429 486164027 66823286 242827067 272721732 473672139 224417872 335603493 1100606664 228478669 552430859 788560636 384029663 575469476 233745020 904554529 797855556 663091817 536533204 1141983023 412409843 992969304 405958408 1186766529 143767506 111896946 388422791 814787255 64959316 247191367 794135764 677371851 934458658 129649525 1168561593 536506794 584851851 229090760 564603261 833497400 666718714 1031973548 581882520 522954501 360521910 581833082 708183676 397891282 543940168 670234039 349237413 616906630 621985872 833641397 717141259 719813445 596389332 991575099 425809713 659764993 459248640 418377075 944054808 655706830 161539480 133716472 702286843 925991686 321667750 611942426 515885518 350497948 1484730699 385430377 615983683 639684370 614364609 532871424 159649504 111933836 425815333 127373586 1002490911 180435237 932268920 181084044 902322632 1020632623 1081268689 506933384 510538243 581543267 917534566 411640626 114866582 885432495 371407782 517266571 738236874 586888756 635280893 321812548 918586665 2133545 226194364 505960534 531266394 893098920 1236078516 681941842 448046362 504672745 681082164 296840379 474818431 548306318 327286539 1157598841 696582888 1202345045 1031605397 657641507 421822930 1010432049 362757048 985978247 622214178 231318367 197974875 255161393 699853944 370592800 561428465 1026877698 156137181 350730957 405509206 193727071 590973578 657372773 525113303 530635111 758821617 1004679745 454551327 219185626 386193003 629718073 498145999 852516043 261535908 415415021 903329312 576188447 632061902 495292049 603826338 774014479 1146812718 481337977 572650488 283125494 952823614 879056394 303152358 211650494 260276229 827025083 289535201 1180661749 1120282814 746976622 1140122331 854450435 435830702 473612565 658898407 339573240 387064468 828959845 620651162 650751474 415606280 1361651301 518670788 586801164 270528890 284984565 316055869 456578269 270107411 915358014 428933641 775497392 951839441 463860134 629362388 305670553 748322375 524616522 330020827 131368860 213585794 768306441 449989609 279653235 637904597 790372266 1178944256 172392475 582173832 607346301 1170919747 233063003 183553077 376478729 586728009 97350132 714617512 516417124 850542653 515832972 239563758 625917490 886220666 597320727 513257794 619763593 726613684 100900101 630345790 768617353 58234744 352188936 744651618 136170953 729623516 817400966 279708760 225165827 641153142 172917220 767231832 888789961 478285399 357166077 177439330 652674004 694511233 190283602 1193224434 227686929 327161907 601899837 839785138 1365556239 191955276 567295879 341828979 695893193 807301583 1013239080 884976415 695097857 665869298 930056133 430948144 413045499 314207995 306623465 483410499 370588919 339624961 236017778 317059155 231766866 38380727 1202552597 263030463 313481643 976064526 952385066 760669495 638745860 1089056902 227855956 769721861 688580380 505304710 1439222234 41777986 423140156 804767917 1335865110 786474883 99028055 513098969 431350446 462294382 546816908 1607415120 814932593 429809124 424734783 1358085940 332304082 1189711896 936361281 60409633 664761340 575114195 1125943936 218552121 928813719 188281112 519839541 553508058 632001555 614314151 134072508 496275093 158041877 774743548 194102064 261949560 748153192 684536569 603615958 695420200 1237639989 1015732345 577546303 796096006 246725749 494314840 47292531 448494908 956058322 594729514 533416060 85392112 277367547 476396492 133463184 871063873 606955136 752408067 166101033 98222382 449122553 108613539 577184740 320975087 249402105 638757844 1318070760 1202163330 949403018 114943640 863832448 932793829 432825397 375768685 217644716 1087910509 180049145 230735415 303620976 461442329 199041403 481485247 1297977056 127918623 604361398 734357682 729492922 183409457 433485041 379168950 293916952 426265117 335139931 258395106 401361197 455641273 525787074 935061738 678411480 583491283 359696217 665617855 410674662 747123922 131646319 378136065 432863494 878859215 462125685 442933999 925669417 126546721 916103642 446842221 266204537 555414079 565866739 408000435 328390140 1268145634 767738318 453529618 998802728 602747062 1006488722 791655129 956569286 92819254 140862053 370240664 799659326 820106756 302080399 796670427 529580963 1065530675 705855799 692940870 250015079 196394708 439540453 1159176966 258109859 1026720675 795535067 840243804 72461210 191192584 890124828 480850606 513656206 567392856 166668733 352120604 179383185 436192425 74950869 557458043 1507912759 164159544 268507982 1322458537 1045964500 514824957 288365519 817798475 186530182 376677930 543074105 82324553 733984851 676532219 474259061 284957787 903305882 518978324 344994120 567869332 952212012 475301045 1319144266 636022593 441830042 306873225 853645245 560949915 282531664 376258409 617307207 801827055 724974390 415531210 765026290 853916028 696313535 277908305 533145443 373870918 778324222 524484624 662643518 600765104 645892710 823714538 972017377 1306018121 557963136 560976176 892939992 195454308 786745694 244054888 562117587 583935571 1225016361 712676168 1096740699 887617925 237980949 262613958 390074985 865842454 327674536 862378794 501410010 1190275868 391519108 691143242 409537219 589241009 1164493178 306760003 785206297 137541301 672636988 532342250 347392306 727453146 1385215084 204882307 398424780 537110807 442737729 171729563 466369697 653358424 519221125 408463813 1185704047 858123773 1035070614 491134380 884424119 663776150 325426856 947823504 159787486 780186924 188219530 183400283 1096528377 474618294 609587973 102699115 312885968 249012945 442392146 778036723 988569754 304982379 790244235 586008712 653848842 260634277 384682076 1265423972 603318059 102780183 1021394404 731480781 840946060 1372653202 488136434 267446847 372648157 272764151 975054963 108616886 506413629 264028581 403679563 832900058 944922647 651969619 1050740282 371464718 1116439925 103740285 832193977 676290821 1015125093 468336516 523396270 247089725 841611087 741547923 1186726573 736292115 230505458 1115614968 541084369 397649962 300627910 1001647218 211154404 353802364 680335839 554954903 315913156 1390807015 955704097 602202428 230850333 1296890728 233918700 635046070 800156993 898762825 76744100 432264103 1090428979 431423198 721685898 618919783 848009550 906430615 331253246 433354586 794863610 545592100 225952835 699598366 690527970 798354281 749611852 484005879 369884806 783760349 625067338 1034936087 1096917979 832317464 853971346 920221636 598476499 84581470 735312278 229759303 136467293 802758262 467726537 1328603853 639655084 401867766 337718940 416096551 459485619 1236757341 233840877 123594773 362731461 283931928 392564317 399354440 461590194 639850444 317259152 93276310 1202948693 98801444 207143898 585601786 335750622 115318387 870898796 112859606 377074558 684337804 791406299 415975631 1193582288 851926800 472792366 356209260 485161445 431185356 91196929 917784829 1278627383 975800802 561080131 268114234 665360768 62211089 512186355 799776650 1114049692 755681790 1039441046 1241635552 435613424 787405877 523499910 870842521 1077074539 124427012 759619001 335483778 412477279 775790825 542788973 1127369678 878770084 539519589 484742188 530537401 416166503 836022104 206856203 712643977 451375875 502610939 581272735 269203304 934909700 1242457196 366814133 651412856 324927778 743852145 189064834 697467054 201990046 205419987 778619461 639230434 226509360 262560572 741203415 404375856 1147634060 918858325 1081660678 485992015 170351724 579289600 734675615 800090097 541227686 928022575 855932776 336516307 834521927 467875285 184929681 609858496 603024642 914423613 1188483850 494537403 333807334 596086631 576029263 652186673 970280273 1101787912 126200123 455582345 1138240968 342877718 213217580 282306518 685586522 188611215 966575302 927767870 291230051 849695003 1013156519 1000619546 640955566 926671911 55867815 768929457 607137791 1217634372 811384619 418054875 808923898 1188355797 396174757 813010500 506213412 374033692 900704971 513121529 505058499 180978563 698794115 244600765 152928735 610573266 598178296 552746291 1551785626 16017781 460629091 994176453 367449468 1081404248 332710552 524931219 749987524 303238241 119724221 179787518 1188422393 708520698 609289182 394530895 651626964 181889365 835205879 1210188785 852872001 295572184 437058563 509603244 111053576 267073981 475659287 825052956 864348957 669738536 665186794 747786741 480223565 859522145 105383319 831886049 939827348 572117775 592112636 485716605 366548024 1051031880 899664565 269611844 297292834 114751345 128880429 881763716 570600087 666347892 546230090 780899791 88778096 279351556 802237520 515341813 468743498 101522284 393434596 139373246 273244132 145331121 448538111 954851018 680938343 1294395336 427650634 833836405 632494169 249981331 1119905269 714354634 696494047 127359362 227038477 591933020 809049282 1037068859 644314780 871898936 475073400 260261352 640990315 545005680 1126794235 9259428 619631177 474655125 768369729 93394098 668809103 801401262 146438320 357428978 482975437 377152909 533436785 390731347 485581733 252683442 749446205 913585643 182192031 141313942 71529120 189844332 1442301054 118206313 499381988 961346136 384390789 586262932 568353006 301298296 805057561 168459361 591747067 387998571 484053612 70041290 246225253 535056587 595058980 741754906 841750007 743196023 761310172 415920286 651532243 441354085 472892681 904292919 187405461 847530378 99847366 109258781 753201586 527061489 582111012 748013183 292872031 674806939 715733430 555505658 444612987 490197138 389205678 877151444 1724096781 418042664 423282498 1246162415 326277980 210857477 609085781 717314904 265954014 435000943 147176601 981303289 601546491 534388511 558892858 914677653 727961384 662159926 876703629 574505747 469495329 608409760 264548226 695245414 296685583 809282656 981940061 824402169 1467901682 204701022 368266372 219820782 447433163 639616251 713285120 562038003 793909859 603633787 1213020827 935487887 740203492 441468538 462440469 779660497 518876946 537451942 120666396 708004030 237823012 228885762 1289828332 240176695 459040158 901075019 814845376 946903115 248999954 1880539665 896133713 275070595 572155022 146152953 801687709 445294611 1622314472 252406683 847056169 694027869 212123377 75700235 770240518 993940980 738139617 370769137 269869314 1102346280 535042319 179743793 683682977 864112013 1177250415 909055665 1043722522 428588742 290066373 1165810291 579618922 775242383 206994974 140026950 1081928652 884178669 1053055634 493430051 678668569 757572569 1150582530 1237312028 1170896783 331020898 54552658 437088174 389935445 486089418 1193675188 546701010 709470194 451017430 743637793 913786851 938913355 558977541 516623874 1049506784 518908029 814385871 674749458 1012268482 951098368 730829922 609472695 214287885 1299126049 874378481 1625348662 540387152 565296507 214085832 852425126 808097252 406753497 395734848 266620727 294061595 567011874 420719605 632888112 572010360 492610759 363953327 369785435 557007322 302239050 605941108 236558220 1128592277 368526772 636719702 742816675 803330397 1044505821 1251702878 382665554 1055916330 445143955 1291543933 358155561 646084618 328955700 804063692 802649584 465720188 1258503734 188260234 1120790683 1233092324 714891183 48135417 727960389 107213559 576525320 853660660 226548740 802101546 674075349 259381206 1057737753 922333697 158857788 665560803 615818429 275427152 581137962 597029574 385826293 275356764 169930948 1124099535 693680577 542343672 792383285 1321888114 593995767 300859059 685656079 743577445 586743726 592144105 344234272 283174689 1146570169 1117328510 309691527 1008409522 129704209 398638970 674677583 990264598 447218133 325142743 289986085 560144219 345377574 754447177 352566253 560886292 711820298 1150300992 961289368 1261347950 416748537 270152169 774781345 460913611 880152535 949464665 659033304 413276118 771278730 1112626903 365256052 558483561 1158897036 764508325 1093364813 486442048 568113039 351340944 432436052 553888170 379652904 671724820 282920736 683624077 132477273 689514177 1336138780 554134311 599393154 407551328 564709750 70674629 1020762850 1134289678 367260221 64550576 138381084 698219687 159107165 558122503 907696127 1374222258 280164975 404493830 306498277 349077676 714807921 305173868 794349074 205292147 332139995 963869050 757032500 826831014 446437928 199534857 501891221 1005382742 684766469 448190118 113440452 585094569 130862452 236466587 542271464 303563844 213046145 125577685 412377471 360201651 280136495 304036367 699443904 287913519 358320907 808318474 610822363 386507924 449431912 297637215 357896019 407992585 1392486357 631841662 1129689230 798028741 469618263 673154339 711224439 478645911 898791084 746998911 668098464 540313093 462497544 231948383 397400731 1602770896 516239327 537949031 454302070 289926459 928729587 331514843 870888608 547698447 538717516 631104714 961631149 571174328 423759533 883779434 1014552849 790939123 353049674 488419813 767909689 851101921 425282367 462008969 511062335 508843526 492418272 432322326 640707428 518733053 341955152 436065876 193751261 317346457 813692542 298192775 843856707 94352360 39389292 371615603 1062673035 720496588 795205736 728914118 198410339 1275233546 756111459 1060362739 577716901 823606490 1564905859 993926182 494633781 821166517 929052329 362241194 788370104 313112735 1049095295 375273320 482184953 565612855 647265876 513377678 724126070 516299664 859864601 834340354 291082203 649094568 598449194 254096711 374019624 1149553219 111711447 227541272 692561847 68273651 374147360 749383435 732988748 146592820 102524037 472733587 637703357 830481771 307161128 312107600 1112478891 1309217664 960365575 627281676 1018759008 345430055 686212976 487164112 107329214 298331867 507680581 86158317 492326014 700819617 498636868 481448964 162346824 115998406 1280953820 669142985 983896529 902398319 606919526 955640518 570905265 944424147 366424630 416790700 791450112 847089636 439079705 567800203 288812539 658160850 1062198621 494410254 587353536 84098338 1091468162 1210888472 1191859030 813926061 591726354 1294715159 908296288 767884760 1717806430 296132951 325397992 510173808 121579294 1216336856 400562422 850989409 162934922 320002178 355682681 819845192 685428529 122376547 638293703 158037884 486830254 692471376 595332657 694827826 287661411 602694698 49451998 415419040 308587819 373215836 454723821 326325670 660448957 331519519 269716577 793185162 555321537 217180202 666843105 1265459956 40173645 940605937 262568994 352292886 133254752 407873452 278249885 802092624 129774582 293217951 414624863 769304627 722714831 205693915 413096683 1112625261 111334078 796832839 1163143698 658224628 288237985 572561499 1137050450 1024783880 1102165389 312317633 481823259 1159719758 665412785 479019859 496726307 921115738 821070914 341076761 740672144 996769863 916667551 569511596 280419939 1269778271 123179811 1361377349 661422781 956768751 1116370070 1153265210 441790181 764378068 939030553 305956251 950396367 878309428 536828985 472836671 320220954 193587282 967687786 630585308 1003431311 1001080169 238082040 769475949 283562336 711266781 333463875 253546491 309784821 567371816 417038868 184445287 670981384 121813179 921846857 1094306136 410124860 72666947 654053573 41466238 227537230 1107844516 713295469 750249740 749867061 1017514243 696893584 1461537544 355160564 266955360 943491478 215612392 714173738 718043557 662102081 521327517 366915242 93624814 726544384 509952763 133652197 864076497 553246419 253695561 1455888402 729635345 1260080804 620590147 358397566 487889347 887788300 260905812 934720216 107263708 257472210 815393131 1100200355 890535654 815908163 562157032 770588704 1097009368 841033344 669512495 252069036 990769964 460627342 738778168 357840815 295244842 459791676 954233056 827197811 350713776 457744671 622338953 589528842 860833823 955047594 833310940 766929359 480189951 557457760 80083435 893666342 690551405 472540851 772926258 155276812 779539753 1018781404 459170540 225429927 644167384 464949745 851200466 760909859 1405409876 363859124 290187273 483547121 212900355 1455031125 646635154 822434613 1187379841 844516041 153769115 1171047698 533962451 731672927 422212521 621867215 58611012 510688912 499714578 472106571 309331415 23503699 1163818804 1312704483 485326668 1350516854 460409056 522619301 593150818 930825966 977593552 527621768 519831536 705083430 441971743 466040624 320243059 161318623 763316633 1440999065 499349578 519349011 334564011 441220791 374099685 240423137 417864633 142069044 759842097 213834302 330377387 227323557 498147052 597184624 690459991 163473195 735373179 376475780 987817975 315220378 1153311702 210334581 492672344 709100890 468357827 657257696 580532208 421873645 1597718542 408539846 710108656 649044805 405929719 616137081 359701729 516983073 146905820 840759237 834113254 881649996 1188761171 567786676 332955441 1004861594 807309169 1316463139 451644576 94037594 387762633 451151680 457164471 1171609855 810843886 372821012 118414596 834758965 253200418 455386561 446227303 1043244654 1090246992 287530985 672596036 314353349 1348089879 227403366 409003687 190335097 1211995609 488191578 496676183 375786077 385796348 1151711530 731206533 519716776 607428045 1102840461 355470622 797500506 638251430 796985172 363313466 434294414 690329385 518820331 404204290 71001156 622212680 642719130 341227831 1539068657 737145476 320441596 600062033 541301117 799309153 223567515 858437383 135647302 393795858 682509751 1254503846 630364017 1005363107 351465638 688650241 1002072224 208792813 549799263 55063586 399334514 369827523 332698986 195522230 225764573 638739419 847933006 464109391 99004077 322887446 1117116103 1125991473 595819130 727811378 459148104 432288342 670683048 487152942 683450005 1370843854 229423442 278651734 271143084 531371173 929505775 282441078 238095581 808036489 207450779 560184063 525814658 427294113 397598908 597953921 601193990 746022023 1209397460 454269651 630295270 337779734 975079328 939497072 638195447 374111825 425247040 700643339 1080592042 374083237 99367829 561327583 885802119 710849258 196480349 1022937652 416582639 516683735 742972895 370790124 468028036 1095051536 346632199 480329925 927127647 576108485 614580945 356947468 534343893 533218704 734569220 489108784 1547709073 179031477 1246249955 601353952 509331561 1053290468 1100152014 1084824614 556940548 1046335545 1147581456 379956401 723462865 552865502 724970906 208234907 486119295 291293761 540094392 326543030 1053544932 524030626 874602098 275793858 846688680 1210949912 538479991 1050391548 376265646 234340189 1034571310 1380450562 848479887 303463073 690348362 606240931 1428635782 85013189 1011715462 787074724 340330908 393481834 638098889 405309908 703420314 558001694 542077780 726886727 937685657 717729656 612098923 193276299 800931389 151774254 631242967 728266355 524506779 800959908 998551322 723085298 798257132 456603344 528011988 1146076715 911353538 517037305 308726598 604650957 563966756 310035147 809304584 34221552 825637556 36932083 1008692855 606052681 647638122 224968290 321403554 505053606 495736462 256703907 822903569 412299118 1122418891 114286193 162112018 338970093 520415329 1515925252 979848134 1265275989 299019556 803934524 1027119281 343720870 899952709 758729478 475866908 348496102 805586981 719544418 221955650 205115093 848257413 474270124 479755543 150908458 92000479 250389829 1392102169 802782094 238008323 1015794992 542727694 457711682 267736470 557870659 1132837390 495599024 793283455 762077202 664774048 303943544 420795089 219182052 423363030 249484142 886262725 1280146885 846786299 229251110 210388243 356150821 101327404 703059745 429489689 179492763 594648306 620219232 1105948631 245628706 267542811 1212127239 246032378 435433843 264494023 926906135 394767758 861223982 583437427 835990956 1114194234 529002618 820289444 820508899 496988120 494384584 526162088 388509523 753241831 698847125 1117156869 1427266493 486106938 326344738 415404744 558534298 303252449 501921573 647747155 1076555722 845310475 406513901 1063105911 491217037 930761088 1161065888 528479931 989744866 454753237 849108945 553445618 355720709 159010249 375299853 796234118 741189403 180528593 399365416 559657169 162803299 203327294 369487858 563766805 1010826481 212783473 203801622 1398226369 411590433 1112027591 799215303 466460769 1079663492 253871190 473976423 520807083 729953468 435602903 148686126 67059429 981465792 874459794 592405554 387572842 714579169 533505102 1189450328 518618304 1137932697 707979804 1512544588 626548587 916265519 1069781691 143867428 303159531 747042560 1415079874 1085431999 300859351 1114501484 1017015003 614175918 90019391 614877523 1124909271 653054476 163475233 665760160 400990711 295342060 745254293 573610489 138097373 592653158 205505753 1477511448 1039843399 531479333 642668657 265184958 1418540471 121788307 809433145 719766214 403962142 635971854 440958902 1007615980 441562148 374638134 186564143 919023551 144176281 630434628 228443382 507379530 852236669 967195121 759541204 741242939 686827430 925115671 277215625 202265895 1115924203 294732222 485155023 1051476519 620902409 209147317 228612029 328080308 123990554 428095821 847466975 1213366311 717307278 274673938 407073388 462418156 117402031 775889543 308329914 838896090 992865944 319613367 585829155 588559101 890087680 801091346 871502870 726454820 332650638 381576042 544259508 447570595 1195888677 71313688 991103148 534376834 387808176 166288862 1360254721 774809511 182310469 689705534 502938996 461804689 941775928 958481035 650990402 1264342453 629645990 852386002 551021685 563090994 857704819 1111201989 859234773 954777179 30611090 724512041 840238733 360651831 493700490 602566105 1044933344 241423117 673028828 1261564873 255810224 1170076016 529218285 268384023 722632922 480805078 294607110 210093872 527325740 214048610 350423970 178159656 658578810 336119187 591761943 936100819 527391878 1085722100 267669416 466797406 716952306 881169749 281315442 811768934 264045251 559461087 1322312617 467598903 524242130 906102374 850765912 364954970 1179795433 302190418 248700689 696566216 565793946 339322346 98447359 275625248 392094503 304034563 384713460 750724831 914053765 368005380 495118205 732672343 310723901 523945938 412244113 440030249 496102308 1581239132 472004936 67226157 392553083 997333108 728807655 530899718 504359946 560460292 641262620 566231446 366977586 724741180 296140846 133001404 1057007890 1073200576 335984873 495438142 970449788 682884131 1206607701 931364234 346025251 129702242 210081592 430297977 1528792058 963591315 395800245 963040518 464490200 419930120 481304382 398106225 767537328 374337600 359241557 176218963 68866058 674961795 964611771 212570566 136180386 203496634 864575873 786912381 233238298 757937261 664255809 473286529 785629382 73697627 558967442 339743021 826254416 610132159 1001301540 823512393 1526255483 1044383499 917493136 495463628 165568724 389798584 41554837 638874806 706506510 1002179735 342486961 1532838414 196087627 379316429 256731974 88007383 921123546 316651232 882992894 629589925 1207165139 650996205 843602717 100907985 262219082 623662166 307267973 756718955 466761845 560378416 350872600 370460130 1204805523 256687144 775251180 797252256 564799653 920805487 1332975789 873988976 1079605466 762000052 1101365854 229507021 524249225 694531214 1347725142 199482616 682805985 740908450 257148570 651744307 258090366 1362178443 403876012 235032663 235762099 255912591 299821774 499599334 671300598 555712219 492851865 1188411024 1054449493 162449638 731582508 549623594 110521358 751578472 641581112 666258785 873449159 203380109 1150677613 346758291 916887466 1089516449 412547539 670681667 745426221 955415633 984079122 700596045 580317605 105442270 190339795 198983922 741178503 521313560 208385540 677381597 350837388 237793932 396918401 1026322761 668809861 755060343 351959996 291397807 216066941 259648768 892936478 171381917 1086491625 1026584015 625733828 1030767011 1025134304 676507505 139233144 946267211 782346033 473679950 592432413 941752065 324976551 594230019 539036865 536047361 1187258458 124192640 860580742 267630385 269853390 1025783821 405076466 1345583569 542464340 554575253 1007139545 380746220 484295772 131420589 53469095 837149184 581434558 759705464 543954661 729520365 659980276 372419455 480413184 1037840522 759583925 99713103 294439072 1000772209 1243794650 123504159 400765450 354922983 384207742 131923233 593174688 708580792 996835697 778916145 853576011 670157458 733407628 1567439673 300150955 192938683 621844004 171312365 805529722 1204406940 909877201 216224552 875276353 645014139 417583651 956187333 82031785 1314537662 508164873 876687984 297339137 126614479 375147069 319685807 1101348195 1200732203 684380623 382688314 608402002 596895826 272381702 623156801 904351105 675229480 907774054 444448129 1012696781 881258772 1091829758 173956750 676165681 498123856 711730526 391847332 893715186 723843368 908142090 1071600635 1099008807 788936997 699820533 1258178998 567188079 707170387 694822236 977753256 645428888 365385933 61106143 526048108 1078696922 1054670971 1110290919 920030273 725532834 420072055 717743011 445488712 995764001 520644516 257326109 656217266 907876946 1070987234 329803061 841054476 497836801 1307021020 587062807 130482763 245636418 986206520 927970359 255610400 1054241856 1110834279 232239951 175501411 110534921 815110982 688486856 918191021 1062665064 1162177906 233452303 639385071 196074173 590260809 1154552802 952795731 494122935 94065581 976666570 442838876 705979320 27507743 361613347 1085394676 332245368 407843905 934224742 913521777 492055189 986954599 711055176 672837896 537146905 394252635 777517057 640645624 442593905 508284476 174209429 860969406 430620353 1024915940 463769595 796900310 120536564 653616611 757945516 705464588 441368937 1187061912 104272681 486965789 729033178 411840137 376247296 251188565 177639404 442679048 457561562 1156583870 1181680371 884403629 337033888 1461784673 538759114 665517595 213247562 1045037726 1081825708 735255176 672123568 1056663723 1082388881 929805320 511991469 749824509 337722114 565947884 262513839 218934792 1007248961 216472986 505707046 363106952 361179965 781639461 859548102 229335936 674385220 705632956 726308736 812370411 339568202 737028515 349032077 777645254 346237902 496774709 556477289 889650888 788853622 349329074 872490545 465157167 559547424 614744673 455939043 379202762 784869057 302306969 387506521 549945705 128293174 502291765 588789357 645044412 662377704 146912037 294594125 1228288237 246275594 629236944 419178086 178206962 516482798 781575718 210740885 1197424249 96627516 570885827 494449972 704876166 374343651 1090749543 516184702 327342396 471127646 411096615 918782998 1067698347 938906152 46691449 922202168 308921898 896606905 483860263 730101912 523885324 1261519656 1211552891 565520111 247618696 971924545 495423355 76605307 570349530 651145050 405040783 474107438 924277475 787800406 1234320512 793604897 385780656 444653533 467296487 286244446 221962010 242950994 672732088 487919145 722690134 654589561 321800824 825102239 313610126 1096073287 291442469 163397291 755705450 597091116 705106369 315304249 396556922 570774146 357053115 717372348 572898163 403417329 749769463 878049019 386789795 814650558 513740368 320047976 482409381 295335733 553639257 365393094 333789471 335069394 987079600 413821222 411091412 837657007 394650372 959200455 327069805 760350897 829903098 1027341867 766435036 945203538 953401029 387147466 506845856 685255874 740925371 501330666 363368351 377324053 382355737 258996271 1319656036 40133535 575791703 410943337 649383097 553939712 635779586 494801277 549795472 380354120 537303326 1194718898 788922274 785743513 1281575454 492467317 724546015 639657601 793380705 389451952 817179424 326253868 365302426 416176364 339179499 586324289 178484161 197437564 470606662 531789181 203424759 694680652 668305751 524812805 331537522 286330211 461351977 527138930 375980219 494454742 829762006 1145384557 219598784 568919284 141769933 893130741 526404467 829865521 263256432 1058733043 1109487256 593467155 400149807 414477937 42628350 1071026864 542806793 326891791 247004316 591409924 598783458 533973007 638848409 947167051 300025792 811639212 965373349 572471213 524867394 682629793 804917954 1074213250 1161637494 821767124 586653078 635335003 1674563528 510703882 619963168 163856534 523318503 506660642 220413784 639883315 515098235 804047936 809628965 317670726 377687456 517830296 196673936 427764798 327874028 623969226 506521601 54498789 505665511 905794830 301875046 1237425793 541719688 1160490651 305642749 945081069 596108796 196632690 81965663 467606257 683721459 761900086 714836891 381659179 680064673 686685908 1032193169 257655027 369710177 295062826 853246421 1123730322 225936194 193508928 540086846 1043455207 969977950 455448419 168027500 1139710700 226985470 665141691 954556585 596630244 232713062 961584436 364493138 1036515083 331732770 898173857 1098947231 1107612741 625239118 502231661 758599741 243969033 398317125 835575855 670362843 695348740 620132887 328271516 622409159 190357289 648531327 811431774 876034260 471297822 445643929 190806701 393754274 209170856 915080684 940586901 1013074816 279805503 147561252 403675944 827407701 1386276076 1065843997 198518017 408844566 1248409171 779556886 363153853 885738339 722763158 78877125 846299428 1026322581 275336382 566919262 221762577 429187357 217090899 1016542323 1232962922 861243676 612271772 680226706 163258112 167179119 664135373 578085741 615730105 999680886 463989178 315653066 729764370 614748620 1671772335 522871726 863986982 198470902 69213514 116882827 403054695 1049934138 460067656 65221320 276391774 816938968 294249884 905947630 915575562 635592416 658752402 242875611 794049829 898636257 276033628 643178966 540803779 425031757 414307864 649544782 266603630 618829008 136746347 677694929 612583499 316759600 753191436 545499488 1034895521 249881159 563391424 971761438 119402701 917391603 373658230 650246122 361224239 1193157985 187145117 386890772 127901185 309336557 395552460 1058538592 1457393618 1066838247 340532770 1218736143 305145191 728805843 533179762 565829741 476734929 675310742 441724727 705382736 297139156 283476603 581640790 598994263 449368665 712542402 544580314 566011315 309536018 739881112 214285829 195769095 857597983 557008711 1010202027 533379017 223259307 734369045 457708186 86432775 937821171 749987113 738872447 598621059 399310023 922496380 1266241987 475887804 1268654136 415875494 777905935 891024498 615716036 27493940 320955973 1028460494 133723140 1001425395 524160374 120331428 597859932 107844198 206251575 697026867 302323049 898786016 103528015 938328414 642084090 606922638 738577240 405950346 109724093 941853750 233913742 390633421 200498417 294412575 1218868366 164275882 489428229 270919358 527151181 572773642 527831600 957983421 923975336 1024616028 719341917 314739807 1314709560 896106330 431867498 1186773874 756681601 410649656 781082295 1377465524 891228822 427892435 1002645825 682417916 359066570 892082512 118215816 1107990916 500899471 486425476 960917641 817971242 712377252 321097559 413836571 825728359 355802895 1134827193 756003153 385868236 481317101 234083132 693240161 849636493 765473585 986674035 871163482 991155877 440103057 732395587 1260789192 220791519 251592630 267119775 1265410384 1098319582 776867431 455983617 914836619 1075016602 551270663 711107785 745975053 729732924 229573332 476244638 502547107 993977628 300060051 325651509 327907096 632402424 406599899 347640899 379258877 447183529 632017688 972839450 393801422 518724313 1156385801 375276334 95517783 1052958588 739604974 855516540 538975984 271367616 513472997 758467265 369684858 765156302 487246716 888258794 620986808 738304483 1104412921 824718344 145140926 264775712 323143533 480004281 262157958 336940054 507879056 588148170 347418242 1173195630 694927427 597901310 644445830 854674519 517736464 1086824387 267319543 577363938 700247218 826583197 512354384 785000952 266356207 300210526 452246240 151811525 1446616175 697358744 508963588 1007990122 1163185167 453196318 437053184 627256292 243116141 224302204 320328863 839720245 572184194 811599379 196723674 840017374 803203216 607694329 1039955252 380720037 619473250 437521505 795681612 1076043392 279289554 844076906 412149292 445987827 123442569 107757460 953901772 1040588359 430112780 1110345611 835950731 721368943 333948501 629136534 337423448 492170100 471846275 519531604 455154550 197971040 425105720 875826772 425305235 357353757 1159956951 1347369855 485354485 494112579 202733168 1073700016 490239851 444843926 1476668112 615318956 336733170 511362259 521084617 353716879 213733077 968234377 792169514 118494815 350238351 304429528 583636132 1205464138 287553997 322329453 1273811006 226787444 734336099 297213289 1006859667 150212026 1205661188 740563712 572167855 334769328 898922633 196961576 1009308643 294835207 1168003752 1099028247 608614023 200682652 409774209 420340572 211062865 972203813 1076221020 557204513 886785088 222535639 467698556 1107780264 412103207 153501341 1600195547 1055470107 1301206078 671823993 263755805 430578967 375009426 555140733 817435607 382984051 755092758 518598567 583047120 481337846 996394777 769900327 1313071668 787623361 683303360 555866004 995515689 620675135 187367518 175075977 552683999 54122361 37218846 374120342 793380362 682131491 554070897 572694965 301301747 426975486 344444082 403579014 825468967 271331751 448807345 1272443186 170638052 318646158 566933533 569588777 295735706 514178204 111528961 845841541 918336860 426956501 513274710 813680315 315418750 493536823 540773310 624421357 179303039 882988794 507021011 655557032 360798488 189618630 532746410 724144308 578262630 783688262 761486272 844669058 480189687 511734327 692890404 442960573 657066281 693719694 186652708 825112350 633678829 1274627673 686567479 784959866 327462178 586454945 565576428 812148470 937085209 341730190 155107605 1149781679 486104592 201494192 400314033 798259254 1067836202 1377020938 644211915 898983836 328671530 481232990 692122100 179399015 435486006 434891334 501143907 600806717 488924789 798213810 154872791 605590483 1379046227 557221170 558807389 676778614 234631929 362399185 879947817 488099186 55481449 1488445884 744296146 531672163 582577556 376119826 874222582 220481540 890208066 294818838 969588938 402170634 755949762 326136439 440431357 671675101 585115393 318416834 238813071 489687309 822803731 248847199 236698216 901190437 1083661088 581081350 229932895 170377830 315853319 425911156 304660036 339199518 434148535 118400275 1001701519 321660298 849418123 531123533 1385576573 17272559 863234539 898888006 391627715 1110404482 56464870 1020956497 526831805 426381781 546764733 60097985 353171897 468203637 560905661 557266908 1113820439 511852010 1064741968 437430646 1138007249 262277303 511712628 479880920 1130977964 708768643 362138772 551510982 419844531 439573307 441101978 565507162 400936614 621015511 628195870 867751425 470007389 274898665 768568929 214271763 1597355798 480124596 1037628405 220483902 198917129 281928820 627551335 760857190 1253006298 17070326 974237510 796172248 896000042 454858163 1091699255 629814638 472952117 764111606 48528141 554382878 448507723 298644260 690115820 507346441 1025142055 375200304 947424041 237786122 941485911 656659608 509193401 408798135 681960562 1508570218 506428182 922816930 517514672 487743126 455097066 326232036 248718082 206467183 1040705230 485598864 245143186 995581891 373896478 717171731 920265056 850529646 372531201 371387430 393317017 342858530 59876237 1075530676 893162023 383237391 391311358 484448654 904279148 719026962 376282572 241052028 650425276 1065355292 432439314 586102415 285099543 563673169 110134040 359806935 594019084 522477982 184887464 533117311 1044382002 633375117 661836338 99593109 603880855 626351834 155658532 1340485770 742059648 1498542314 805211896 1246322473 665470663 490096166 709098683 1026545807 1191658922 673974020 771590358 1445531953 1017192203 458991286 57489843 236411434 247533700 954723209 686211277 529447627 624514362 1051612643 390951304 934426645 173692343 582284617 366450410 1268894029 1006054953 693614422 481274963 689731581 1407484901 1040731725 982623631 1248619536 842067290 774200873 829193906 219753482 422891880 357492381 247758767 598549703 184937232 609619320 558880001 709793683 378182690 610559226 490260826 326033881 475631819 268946513 581175961 861772688 297681846 447245748 870092139 640545054 540851475 402837425 726305597 879451278 156247508 542259926 269720726 515182943 628387965 855269513 1002958984 877128945 597689133 299236251 136000242 762985493 925726181 853280079 292604547 331611359 456716420 1072839025 206733068 421385188 1038002027 988804032 1210693158 732686718 194097867 882257953 867117757 361776761 846146771 692319407 313824916 757134054 615498885 527055728 398846694 248692256 535121292 19494787 930586143 307667806 321998079 551856765 581002945 358429499 414912412 341585417 682657196 488110634 765185315 727393354 451399403 717298102 706062119 459314416 377353949 446978382 641061440 642952541 133418778 964430788 706083407 600192942 128769855 594873307 1161432636 86805217 389137058 1074595199 413260158 916285739 428897862 927656187 353162889 728881451 564818289 481871495 1099243026 370820533 163083549 942967890 1397626256 792585007 1391012710 545641431 408020058 1593178534 1222074045 524891829 464426113 1557034160 434056614 531711505 523821334 434896964 556573676 591534057 689538436 747843605 458053839 716433977 436616772 857229266 766554155 910604354 1071886778 597800977 511633244 843986930 465197066 122191277 316865474 154949663 721567729 98167308 538728401 620746941 547346803 815721935 925475746 741862222 351378502 693674249 797947102 333843320 112575733 744375613 489137799 1033370582 575308375 1006429912 461943541 907584991 413562381 232453685 480128419 450635338 258482178 412739629 55836738 320502984 529025642 308774345 1207560635 762320932 94411081 392313411 571052027 433446495 696623206 283558378 836392645 560344845 372553533 1272723186 1029722032 395493347 193020243 505761306 744350147 298857501 1034829492 540353603 760602647 396222290 657947183 782167203 342430198 556594097 760307323 1189433280 378138688 624443740 1052126145 572206424 284459975 79230904 580906340 532683195 492780158 950819705 1276700957 757857300 1040923866 339674049 326045286 283782937 890647452 48341355 501824894 705851541 442933619 671258185 255662200 308497009 348079807 347750483 95935048 559372441 298060099 188448852 747148299 664505395 643514001 408714185 604737687 443619725 637729399 862798066 772061201 429140748 281516916 973548982 1229123760 151712323 961246030 22467358 1340296618 193417882 543902271 731458521 1586945755 593567681 74381807 745155434 712546707 827700851 946874340 475139943 193725738 364180936 674183068 1563120499 583221496 785957070 191159860 246957333 1245247499 328822295 701544199 412433831 207447666 237997811 225776502 213232520 156543352 1089024098 986844147 748613623 324282937 456822395 1415794986 646175190 518646119 643145547 510286223 696935206 586664924 673935254 331335372 163168034 79129106 757000209 134638568 538482657 402468991 1265964661 424308706 910848353 394246027 298375070 854183493 403734211 443173307 797876312 532712261 992080813 891640893 800397535 387922425 318523153 1331775006 543348968 220846357 1289930337 380076739 479193508 269355537 903522161 622923307 807798010 770177563 868200433 643981502 357315979 345403224 379741825 795673496 1068712042 1200294786 252797922 627096963 932657311 538069374 554070944 1571350500 150270423 886409062 687894526 481992586 578231917 1480441434 81265128 565772979 664262969 93713746 329012162 175082628 908675264 541475835 288630714 388552945 673875731 203658610 472227880 354187961 238043170 415896883 361396498 180132443 975568452 933552546 774845691 406941159 260303672 386038557 352361651 1224494980 556040133 746456699 556773072 1362952262 783531375 441667344 295212330 632650407 527704594 919055614 411445463 1258025189 735893620 457547369 395416309 730937135 577215757 201243236 799453478 779313718 845364190 930220717 402225421 1182219637 251684358 1054908739 631505232 197515468 964568503 180450535 729835183 736774514 630689319 587122105 874354820 222921761 128709507 780435178 960746528 236715952 181183103 349752752 65844778 199484867 115690617 717577130 569704636 730637075 910981589 976402112 1036939535 107586800 619396305 902001370 842735612 627482055 838893561 602503580 891298659 545918076 814425613 341846994 136724295 1015652380 1047395877 593895845 1164153127 520014478 1357696508 596382992 1527281097 504984333 416210983 840678674 801605026 555258328 539003886 1114204091 800372184 868930874 48399408 286672835 265751606 190082420 700245009 486392143 786395015 77077059 456857976 429802201 1030376540 589356257 666021187 475986122 51216811 628796811 633606345 469535758 1304687389 1378581443 486296580 398325628 709414001 472969425 239961198 202827597 453470515 148301504 667709374 730938150 274916380 423065730 1072647398 762102608 530855311 517896733 445811856 240333203 722939720 561171656 895562941 848946754 68835581 188493458 159053617 1085596855 446253699 533410917 938441653 56862817 395427753 796172698 957867955 163947944 372331844 251371952 488711967 535216431 719690885 398952995 1017960866 905275541 921331046 568043723 732804058 902256428 771322723 347766832 765355204 445679604 829265779 1176912057 953566111 778753429 551958953 941047359 826225303 936002039 433431233 678675792 199544699 197204745 118110887 1027391843 526372514 1475398255 1097341009 893145559 732518131 504926114 797333134 495389493 447864132 165041115 103069215 905646543 589253246 783842534 893555607 296219507 407106333 420177881 386904513 621007427 321406955 592689297 319315054 447686690 900008658 567471143 524804657 772133873 632612513 867109433 853256314 496943516 102776059 72006856 359120964 779529860 488477888 518508272 518758743 706961384 734971618 640602225 753548412 491587431 444792834 592473312 923564474 651532085 533179791 555919996 655140760 958616794 1141633529 230867890 649139652 711158195 703153432 1021512027 985529689 342557339 109210287 619472211 606689962 710850875 393740666 199503343 1198910299 962916680 282148859 608071233 273454372 568559886 817708639 1374368066 301716881 187738349 608106248 313810383 595737795 716003581 465518024 706141986 429503640 786476896 1130569547 1089023946 499227040 457971732 639198691 1406871320 327915281 227491006 412564498 181580665 385067196 887181520 626008146 999211745 647345731 1016948192 662706064 465418480 616139934 176480204 671114747 727113595 317091589 511213275 559673742 701766036 174793067 714343309 842660210 515037542 289015082 647768720 628300569 802287858 440653959 746902431 279647137 346194447 308388801 1482253390 860624786 175246480 646856564 858576087 376711460 571089395 298915442 274584071 718997768 221064597 993725528 1189640286 618353012 932140841 229247956 767953656 498476010 965903134 660261115 971161635 304203578 1445837849 806242224 472021181 439575628 330170356 346347197 299787175 452205060 701750615 26766546 891704898 838441293 1389054411 272413286 678538178 814317610 562515151 946156498 276791895 287639368 947937288 795905531 693958169 886553200 964614358 103079591 1133689361 253583076 589084368 700147501 523532704 676095225 618018500 504917495 681242291 380914861 129371565 851026565 576719868 1212877303 390136003 471382429 1458111828 409112612 805019980 582880037 1073072699 357884003 268577761 1638507260 210034510 1028190612 626080614 722677940 148436599 660266757 408364026 240136315 167144256 892698120 798013383 198530960 372970673 1188817839 227377004 663352560 1250101296 505328040 778709764 73529768 443028727 121553810 410317723 849268869 670728806 560832797 616180389 129230499 1198754411 351457845 905736539 492074519 314228591 354637803 134354391 653046224 455972806 667023275 479340465 825189859 661019258 1096883571 895194474 256939875 212780994 703057899 742150430 1372682012 325313675 85024941 480555765 266004565 17192557 1233173429 251539890 340734440 827579836 167172482 499547183 1049063340 784318400 453974204 305364143 381415816 524856503 408317577 292969035 150555350 153141650 393058187 384158683 730615638 540884247 293759572 89339539 981629400 1393471670 315235996 244654717 129951171 476921451 948115803 621207980 412343246 272128912 971056617 435723764 304233349 369936893 585448443 684391836 621078535 591775207 324222247 487276908 1167706187 880341293 756818970 1038389862 186324614 727155906 170952876 351748725 794698304 489904708 204524688 582331972 1030736726 611523350 550519012 105473283 878593992 820229158 584254381 629846587 460472820 1011144100 527888126 681213113 346386333 1268488714 921602224 829502161 242703607 272822566 1287772829 257841010 714863062 200345316 405674280 504264143 294112497 219519854 311573378 468398968 102742701 464510904 206109097 620926339 326469695 947886251 811923311 1070180981 97937926 527596065 1057338069 533293130 867951799 477593189 464347694 1002695557 783066217 230109942 469742346 538230013 361097236 1397770481 301813172 431689989 299784463 684297312 398804925 217999048 444554715 954357132 564578724 83992502 256746514 803093327 743682154 813746822 446355662 619986051 569811084 380441288 981221081 492510762 728028020 511604038 804343084 591470183 613350163 1155579808 269772325 664906163 270055524 340862174 201830918 421669259 62726023 1103050225 314674146 145502393 349190320 664102977 556938273 397528058 967368327 460512457 595133957 564772270 154894882 755526310 798492526 295573748 300798835 540279385 666054077 302700678 20730620 421577343 1193922126 1159915270 1204242650 556005907 778811797 817006579 885360433 578677866 845880582 577554244 260815194 645642666 1167256009 383437402 124345815 90977776 634495588 158840169 309224036 877778208 103579000 739232371 571740183 70134699 439532343 1268337464 583594829 492165679 876414749 192490510 696401689 369692446 772165050 1147131842 394275890 473390765 616021556 858210359 416851279 764638340 251101200 339655914 1086491596 321867802 270203168 500879958 1094913259 371562493 1246640011 600300926 326784131 249780676 743964169 346542453 113165776 473012427 678205328 523086039 1201280946 778996608 659284239 399920683 973777649 207696908 1098831503 267528612 268909035 662659689 304801310 507570840 230563395 97539334 966600853 491895270 149561846 381839180 668522559 453871618 199485509 1201115046 365970391 350820114 308854422 607421842 545076963 451432636 1388904482 582457795 251248152 105214299 136692515 696990708 287128877 1538719317 223780175 856567138 628541322 652051009 251414714 709526000 836250306 477339654 201036975 351204989 319721658 742580793 222260187 209955784 495145860 608243816 782388995 1177147006 254858355 672080597 140941722 706419183 558189554 467406969 570455099 516002970 657794916 928784264 639712972 149243723 563358892 665928574 182937867 645692406 339117276 525374843 662366843 725350141 768565718 432073767 526709716 668264394 503522169 541401921 277634821 305780024 576232896 713802674 367216412 400391636 220589887 348743959 143486507 45287134 326715601 819562471 533218947 743196431 615824425 674687469 933963229 656420892 878607287 616208018 515595281 857406468 444194846 397614747 307569098 455702223 99115564 721228525 294170142 425720839 90222586 779450464 493998927 860146253 1372923210 793694785 1259623156 755073822 535211917 1122705045 445792660 704322486 210956446 867577244 1240302214 557369688 1021023891 171269954 636664081 489590968 375509492 1306551731 615590769 950843867 442089878 1043036660 452436490 340511873 316511912 1290480332 824570898 654461906 440478476 51722026 982640962 170353334 461465934 227417043 239678188 340615981 601857725 696687365 1368439972 430922332 723712843 1135227161 1336392822 528362128 900779065 60544707 693275702 496281324 998809968 196031557 991883458 300226221 1087474415 463313618 592503836 507347832 963429682 280443657 535374141 391855433 99362581 1097967991 463934838 704948039 706792029 1015431522 491215341 1014984607 420683134 1407976614 437187013 159650633 335181681 238565386 446152769 139193843 123815319 1536687244 889760824 209740497 1133659826 703563562 822294653 452061342 540069556 468867626 15480998 711536794 788457466 318261637 524576601 281921752 748059328 865175260 212561191 314023887 51205375 490522816 764170831 780008825 334948197 320033721 218235619 63776262 818192154 1422484362 571751191 1187010053 864637353 408498882 1064716186 916644790 338868105 761832906 881611289 447442660 916087666 660894160 256911916 839208299 558512483 469679260 303185341 547352212 349834187 615529586 804906517 1167421176 258079415 497084816 724218853 271791626 379119282 645361259 374957299 351478020 786747657 44616935 394986185 215824367 818971204 659818620 417420507 370930234 887935710 646721421 499844431 444338013 491077763 499853150 650988380 812145672 117577211 832876833 971264297 217568514 294401105 529402350 656414433 821317413 550478656 605767301 262486510 1334123147 483899512 178187159 1365205034 895268959 1051604960 486176623 597660812 1143362092 683831760 347643922 212206456 1269790940 346033994 418455309 742040403 460156714 232615643 254913181 682938668 451249968 612514827 340587100 86566895 249988995 781112352 721850465 957795414 766076837 886985175 717668148 457913149 1172328919 644089228 620197523 56038514 560408419 984910942 526714738 634622066 118638393 502929927 709370415 289435301 796410684 587685534 850166239 866745820 121917123 556346212 1146458264 472132159 583678434 374174338 1064795844 947150955 405169454 335177853 136243175 652370429 799850540 531897089 1438726970 348970259 282677701 522937479 730575288 409632740 478644437 885611013 963562992 801029133 1008241813 586971841 885680563 195951440 627911520 1555390215 44406822 316772177 718529329 1347300575 758470789 284423967 592284535 360812722 348665556 383569025 606088927 536864116 363627562 222294925 611727020 371571682 788131693 433349095 608842477 593661116 273975877 706910771 334880825 102982004 364873470 214386182 1237163807 167092219 1216453230 663451876 336266443 635564777 215049117 742724510 515318166 400517022 491605806 418309257 610791964 254055299 382837277 904776215 179529199 435471254 22214054 1049530172 776759886 1344188890 526680781 1001885695 692360909 248168628 227804304 716849878 541519142 396166386 954771899 117784610 1035565012 879158407 877958067 366371160 351654668 488522255 379635861 467262714 947933567 146904554 604057456 354180995 417745902 664403705 526470483 770476946 383489654 483480032 227733709 758259222 273896598 770230900 283723996 692281706 833452989 696009014 363434291 636508948 508636346 716016035 155595963 699705489 186686072 883664956 368781520 309731209 1011712745 720861761 913559452 970697632 193670123 728592138 427461171 277070037 168744940 775379832 682086637 991748854 474286953 266798526 320559426 463281200 60017414 1136807176 160076888 569812105 484404546 458317587 352621902 206037064 848775603 741716341 595288004 314011845 679355219 434392358 918701254 653754373 957870243 861442509 393929932 847015988 1077426596 577757786 393513388 924009239 325990032 1379677786 573090751 549222156 1191516023 209211692 280355541 310152028 750745557 334589466 483023169 716005772 406022344 443177714 492088778 419714009 863042618 250405093 856328201 553380629 637328762 234119500 817897340 548415046 652741303 296742783 528940026 200355668 938602566 267112894 844793722 483085453 529962435 1297227612 345912763 175007318 657122618 815141354 731038105 395658687 380209137 350237040 203184837 1478435728 838368044 700659349 668878346 405649734 822412089 397568471 1050894922 477603463 600258931 701186304 490670788 391040047 366984812 319987183 1224706623 234262472 782057809 402679714 95326883 722572543 31083568 707964905 281305587 665537427 887602781 859035899 430947916 443189455 559805711 233716981 210664793 372584721 234655460 1258356600 695937378 432810668 505118856 1118447172 962878526 455739597 267704967 996289694 1012736341 820292564 122155407 965776415 735681787 604595926 738588018 100408426 1634814614 807453845 773238694 516830257 97312469 48422743 1624993156 232861244 421523527 704659412 795071132 280758168 838017794 544290668 363775681 324864621 192781369 536009568 93424509 452559299 897649345 662614402 591679856 277128276 1378697920 314658507 560504152 491218667 723011807 782563779 985827534 604780883 860412098 213894455 83894487 742949649 428417478 623442327 378788383 1051425212 797891593 425793030 143195627 287497778 159679928 758686631 171309042 697111197 457274106 1460227555 557485078 423656975 656139850 1040926478 497348622 686457684 1286033167 175190169 510655824 914813251 395847070 964318806 571327457 367796643 901155625 1160919533 334045497 487872109 790582346 454287746 827784813 397540736 385968326 550428317 413055588 132079724 583689101 851231124 617914230 892671360 624145057 448670712 940391274 795469702 149194621 605801482 929789909 435396682 119803124 194057488 483288890 378325564 614915702 1309397194 562882674 592605177 264980800 92583701 333826069 960800854 724216316 740755309 897277962 665024191 219097402 352255995 627932129 180836337 750898263 749942692 1002611379 383901564 1000873409 530582075 905146485 421934916 780552851 609147012 929329380 97346143 891278765 415653360 862553343 852647339 340348114 248458919 710965165 786481520 1301264831 712755669 466054151 519470187 889391813 511081140 270162352 399863866 727817490 441313031 669681197 556145239 539836663 644367459 488596300 126773888 278563223 282104199 313082472 612459248 619427050 682713120 212402702 673899608 54700543 314414574 1132432571 730415736 1154301554 527401292 1379391305 967557493 943798927 231037588 523286350 481840105 845651362 780888632 127425925 194242439 150364189 591028437 352656794 544914625 336540145 900782902 864972298 798857870 560381586 414660234 558266944 1064575100 914472525 411875839 996751551 323010038 588742249 1037156874 1288126992 289183657 485459342 894675474 973489731 1103167861 524065458 447505734 243724722 378860687 1061738132 234151503 1164109337 230182725 220820427 416334869 370897142 450510147 468893340 374981977 171026696 992698625 672677040 1136184299 387628137 789840351 306718127 53532464 374293688 512389969 555402930 1129675508 331282725 92371591 577648370 823573209 216473320 1286013707 115837143 35838445 319417718 662166072 825880281 641668587 382642686 650780425 729361361 959399361 215885340 400306998 229102425 990896186 290627410 1452048815 931565071 205743649 419267798 441840034 513347044 846478697 292006149 995790180 404181884 194758470 694926455 487128048 1091874329 313453225 755816124 441621396 484472750 872834010 750337859 396541415 536270391 765393404 1078205902 1059144101 708478320 952864548 1356144316 291420332 1294176359 242149330 331771937 151535299 443264449 504169484 893485584 894123482 88565624 975466639 867390398 511388169 443488896 1012050072 732581007 781399460 1149768593 246835343 428660423 691742181 466410416 393489308 341410072 1276959031 126454373 1482875573 704219038 465944617 1466306527 814454462 210528106 807571052 288901009 404312250 506157953 440605802 583746397 91594317 457048537 1435050433 581049906 957143756 327401879 1122852164 1089943590 809059623 150076862 804753002 778167223 975144677 365219696 593027506 1459894154 841623325 1101510531 387603952 782915021 481935170 333573073 420350728 1084372375 778402548 48944597 979348876 412138751 919108606 458838393 125379073 396867362 295776436 377083359 523237243 533974513 1465643764 329049486 227286680 469184684 983498063 184480203 1161189299 1070243956 1080777241 1002411461 440137125 1023416426 868686625 1535215720 1239049675 311535710 578382971 1056885731 649488710 371662380 323639627 319929410 268625135 784980292 86411291 379950289 941392214 670708696 133880876 240463810 1093626261 1044976072 644115687 513032481 441810638 302815607 120052517 203695826 599866719 914972191 775653927 238620847 287616027 369737875 330056536 659564566 211405536 218871327 310839460 1299289410 911281576 570576592 842810849 171362436 335600000 723781075 902026698 268018343 522803919 239468165 622340324 300002774 817186936 625896263 292639835 360333307 407646374 67234374 664612256 1201146627 878717916 959647263 491443493 441682345 652448995 779072800 214454589 924349573 643756762 298248505 246112263 1006417457 378793072 525069008 108679044 303257765 741972958 264707034 348193430 799533972 632035911 1083971858 979077737 634931428 512707051 382246194 310901673 954587814 758137284 1010056319 545487158 322834594 618244946 415443559 1168380422 863306405 265931005 794241831 431798852 407446776 161035955 785852931 672137713 334725099 268695405 296244043 741306118 941744851 334449921 219775682 773910815 578882804 239926299 386555010 1129657482 277090434 672210866 741521888 168924977 285278587 928034518 1022860474 450319679 248176813 1083800163 408447938 819932018 567011958 1106115096 771590350 480089699 1050610291 888082517 599428276 611916433 217808822 879956987 506413211 702897200 482541604 628700383 1031516380 1101738387 480777939 491644437 934359970 549252851 303242670 524035100 463150625 966410668 1285502539 946553759 940970080 1164631868 575658836 1095849047 575171176 342050206 274608957 974047132 511808957 442798857 624169393 159894079 387379152 1403409387 31235176 449305383 226959713 361380402 1100103125 501841443 906994170 809530269 363752353 1148802118 1034370354 171089227 305478579 1173682260 179494340 782161012 120630105 322819321 401034899 976386919 514878050 450207723 690282833 318374001 371980365 735831217 492229366 393703624 241289961 627737958 876355143 439918187 794458312 545474608 711797669 537089920 495892317 1460443721 251507769 1005780437 444249719 621767160 565332673 560431835 641501739 1140405250 967544761 373413211 612999082 739273350 892036479 212876896 1060915994 70452944 530220585 192259962 941186605 698057003 142204668 479614172 300273148 1065999778 402464410 845539775 546440694 269037611 415202642 1029380530 422859873 1045534284 243526745 660662821 934167929 264710795 346437775 550749797 167358151 311449865 620470402 275736431 93421948 827814793 208196667 423997596 127318468 871551388 612734727 698794332 574525024 652991453 1183439187 943069181 167391814 745756317 780260691 171368445 1276846485 501258651 251943877 353612257 361960401 501221458 91983801 1169530071 418525807 545737830 557377264 935381245 172311191 755800863 818623741 610626194 373129796 638649870 276173974 367198203 875854933 655775370 118895672 1006566737 207334109 871209373 162199773 529831400 251340257 769647595 347049151 1000223711 675879527 806418796 664173414 862610590 195013839 541000964 341895905 981499748 502480366 126533748 548294320 1412926395 1518100350 899409315 1256233980 533041944 847955361 469713263 17513038 750526085 426816370 273231244 172878835 889356987 198037358 1526437358 583088302 1227754499 828904965 388143497 60295582 758644601 208451906 239706381 764602948 316050506 1194203832 670523004 649077381 995188515 913950420 363897853 468283525 264385669 670762809 589374981 333114769 937876149 336994035 254024557 1187694502 763070353 417428209 1038730960 538879105 371376154 539340895 434341681 221696225 1534528635 295788830 907788867 556144212 1357264172 774797753 597627015 371908317 237925288 445988195 1056880515 596823608 920553945 231532524 552488462 174555037 756552158 342878628 1362554970 485183690 282605703 358577236 185105352 596771075 749261260 887639119 1411974341 765737950 938153717 1456478807 272981096 670154041 407166575 422352063 137958549 589620472 696735802 254902400 993468528 389619409 1078070460 1314187603 916605760 1259547461 451460544 612424562 1038736780 565518346 148389153 628076341 989923896 411630506 572426297 1044119313 297259913 711958766 520645089 281791324 637890388 646892048 505796078 428652089 348143562 1346544447 269088834 1132429122 776928049 444465120 630230631 157898887 612800319 375489524 619577492 894656321 596522338 247731129 579198651 600257819 509608474 354433910 598016365 684205570 380644484 917399093 712519358 1012116740 573540824 711220320 631046162 669789409 309575910 299258025 588907343 248153507 977191619 869555483 592727163 327259115 471380833 552519028 241217395 247947348 344137258 1114031781 973913629 200777636 243982703 1232183755 1642088345 277931274 694793579 851823992 416195342 381452325 437487547 518462844 254673331 315918550 263615131 1006690187 932836052 576084125 117023845 636045025 463784868 506511354 926864271 662383440 542651057 292380997 811985584 368368192 719346486 494955077 860914051 429129312 566381743 664173410 83651593 1115088675 323866028 454252450 334397144 286497342 556467010 912215954 946856462 745241509 433509361 344940213 458296631 807117454 608046685 103927040 926533730 852619008 452202282 138892176 264659624 447969274 1219858824 510755754 615477316 387129143 417819984 892960977 311328526 635368700 586812207 873782084 764215947 854671915 1110320353 519026431 940641260 398220393 442499984 973485131 802393896 819547088 243963291 372211982 584538994 656759624 505217622 937782235 515767315 383164247 35975017 1099813241 366643178 951274437 857108012 851762381 902217847 703461850 429821759 1086519427 789943496 892640292 812380907 560399064 739671714 1407664636 1091626362 1331426748 451508859 174889310 1346925871 360370562 342280468 997380507 910781419 669889962 435804339 209379445 620805790 556978428 300411404 725489116 703626102 189617663 636448346 253902092 1004664229 183621266 947356582 661467830 173647621 433913040 1340089341 344055525 288102652 1030875009 358718743 837445936 983518623 564230385 466933858 1304096770 537223061 355107050 495069400 1551335698 694734460 1016149252 864435144 1527504106 402768948 485358326 194467609 804430750 756514086 393539685 817105677 174333616 496435210 1163132672 700597636 641070360 594024804 1417760457 511248616 828583940 663097964 396677199 590408175 499091759 897592857 135299689 181641920 681925419 62513197 156280510 1470717165 587668810 519172072 626609627 1045746963 256655251 1375962007 915619195 707447342 157097440 947736639 586842081 488957434 532876748 1180884229 519428153 590765890 1146516414 268879800 1285304783 1149741379 219182117 489233916 1061992565 237549700 784066096 850050644 675705589 630547435 893421118 698382483 401977713 1289928407 71571547 715434177 836758244 148265574 233859671 683529936 281567088 868034952 1236191080 456539531 492947126 280225363 500868121 591908995 785148292 822955857 247484148 617984068 731704358 65922659 371888061 983318441 453607601 330307021 516534749 737385296 75225564 130567767 609223759 551871505 739652532 713639107 325623059 373107403 265229609 290382177 929034670 467893979 501367700 1327336794 482503698 1046542243 583046470 341241515 517849910 761696574 742218772 710324890 1189311104 591752424 586509709 329220903 579323204 135395648 1128682775 884949738 1218565167 1007390772 60766014 482279407 696679565 372913580 1383084395 331611144 1203789482 488900068 368280951 521030070 495875032 436153164 428965417 300621445 413626196 449713205 971527253 1176105519 548314135 32106491 1100057331 716709507 1034932916 958813314 613931757 490312599 481453926 729210110 158454946 1026637521 780986785 373382167 426309707 373476174 708129230 339527303 534263267 326322081 719608844 722878877 659642963 865608656 956879582 63995990 391178188 748577433 235247506 562028516 734907574 970519837 322912908 732036751 659236772 388392313 459244148 552738603 327530121 859401492 413186545 443587415 916386562 90363633 1014025442 1200334533 577856478 737615121 579332633 512614976 496894335 1094978741 619411538 700065856 458871301 358611106 304981706 230720815 400039558 1245964662 341435287 1089929801 545203543 501030201 655977957 673362880 636075902 666791898 661700563 528873990 565298187 405002895 321456347 671129832 100988165 579963920 1154279984 304422153 534685128 1389505136 954749692 994319738 552418719 1261659014 1152956805 567916326 523887283 652042956 447335421 740542964 1604160873 822944132 956465489 326128120 207763218 383407825 856080004 661893773 852743838 1404735131 854635725 700095493 558794990 546371191 701728363 944615152 615038724 1365613461 462425657 121806509 733771399 377347821 85968211 382772446 1692117087 660115013 130417148 238830619 224380977 140708031 193991726 539055026 206799123 702748614 934347875 202187069 1136902422 647472146 269777061 494276212 1222259811 513616461 611163632 1058882283 292026713 372156687 630666967 1176769389 574812486 433266545 454598725 58342013 455181130 947564649 652078552 617484692 1227501208 749036902 351569828 1157247155 1123502596 764683254 187871025 791864000 263681154 523427651 309484535 277788108 90457751 1348361389 1615811921 613121967 606908123 1189960603 708851488 985249147 445969404 543195753 231484668 913951631 594429335 850131666 234148180 295036751 1074280585 305987158 1030736907 429307169 410353429 179265184 699207812 432239655 464347497 403173787 519187794 862558300 733505711 699465004 962988682 818574313 429489090 181172962 640089167 855721480 766179293 819986918 902862237 163300906 626281780 906286103 927256736 966939426 1488566247 838112648 259282348 309048251 1014891304 1352149130 149988542 338033422 1091686139 175523983 625435429 1075778723 244706225 793974759 775698452 97201273 369713815 294529066 660559452 892964646 328223955 387395376 1183323961 987808595 550890063 954414721 439234308 561224208 545744553 665428631 214662778 457707847 518919847 178082982 591998984 205671782 679809845 563316859 943344180 135580773 555969224 693818086 223782284 385531537 781052207 250148861 808666064 557034553 397270964 907744722 895627584 337651615 474512248 525073444 331810309 495765406 949569143 421798073 682151633 347947259 506740180 334352417 84972435 901030963 1177638794 1407267664 372871803 1104088233 467999560 364396314 719456512 486320873 253270046 650983280 1491490814 1039587495 126472231 879697630 16265486 484178391 951184321 775502732 746246797 239893395 286598119 363992269 513513267 702730585 1116391597 157726073 86333597 484804564 1107535126 928177036 678646708 852342373 251703308 406844696 624334642 974369502 88265354 538125352 844134825 698391921 271494086 53815538 234917580 594875172 1172916091 429281972 362298524 206153173 231739228 578036252 387085874 417566001 108444982 1142222288 369908944 18475441 273115263 1038591361 525859062 1542438268 1068004354 838642247 406464140 443471551 799529465 906082440 535258261 659237681 341709141 360732028 301486585 329700628 1116192746 318554808 228407135 169077542 523720820 451026856 734945706 354994046 262745832 913049334 279220753 593144895 923835289 744512403 1452376602 1014242150 720266061 402364534 614494237 452445867 429929364 314152022 533627625 445266320 253638027 711964503 621762111 283912471 820330976 515930354 465852632 99323271 418963943 668734276 750759006 224104107 273908897 1011982828 575768485 1071707282 161913922 299218905 196845704 749719290 1258623162 291812233 644715381 571345625 603270024 1032305266 517611163 722219537 596735193 323465426 1084972956 977896189 581288621 618071504 314466487 1224475014 510315797 949406884 631124493 439208421 852341649 197896751 104172474 645227123 543912004 463715824 891000896 497818150 212134611 882393166 131935234 335820406 236440341 466719410 1430555643 483974847 488663187 1312106584 597447781 725150322 602410296 905778086 968617336 359938523 495142225 1120961391 232790548 821632757 612662639 572586336 530268332 260705069 944451835 301822272 896693670 1144914760 1011766611 549525859 884380009 804466561 708544244 321809405 876662372 1318613972 910889426 1006367786 271814547 369039287 543467058 1049967565 188055718 354947924 669966981 1053509603 855731727 896797115 689965764 499159870 302766874 673869512 1354676265 642567211 320544056 554428374 131597481 614408282 36670194 668764422 198160159 486577230 645156528 1196881962 425009012 868354254 844871684 606541951 1501437010 864530649 1036771292 1355705355 577445433 631201050 583786270 1147186022 1194689425 567024121 752566222 295642343 528164157 419663896 111309615 221592764 470988162 423097561 321785280 92649108 613121175 336817525 224617279 679747393 635913505 608401279 590463506 659190859 1268076998 931557240 837849722 1731610362 224441567 320330634 504773872 1061227958 998119969 1008336930 120147758 311287909 367511096 424268477 1240977513 713372919 848486031 1389059692 359593512 106032938 1114965633 907325301 712193078 712505495 1456735559 121855947 469297926 1673655753 462793762 437466441 458281444 514687369 155583645 1080311537 329537035 554706553 517118169 264671351 191659009 989870629 1372005585 1233487633 277119858 625151550 618201313 620968615 330503276 358895980 883862181 531590362 907041067 451225704 231577470 551260532 318519091 365310822 431923631 578496197 693546378 478873949 584290507 251944943 1009171021 678481688 1123685511 1011229007 1313108818 381226942 366249909 271438649 1031630209 838261655 1293992157 1076752449 258157489 318419751 523448229 485112714 352800050 1133163146 223273411 84620519 622113391 403793148 615050395 245650306 395661211 335154953 1192513063 299408196 1180162560 336286579 556203587 542196530 529623315 156006475 732694392 825260831 661218143 275920776 607143289 895227068 653220867 329115425 253928521 1043445340 189043826 1351999582 578291551 783577649 688342543 1203652623 701946578 512857611 429783461 1144860139 430688564 650868559 570993172 338819521 588612088 543919900 346858913 291681055 533259548 406365369 449193216 933254395 378104846 1041029574 704212172 116691382 554400223 411111052 711190949 886528093 770649864 538870198 408194554 372391324 480533120 208730282 954753263 245703004 894360833 210085996 88783721 827629310 1037967229 566607827 1369651181 1611617737 631655558 616628350 363511238 269431303 639950829 234213300 68758896 465436798 554960729 526714584 531592733 679241921 992373150 300505348 262299820 900943841 251030809 576995045 663240053 417777567 1538505519 183833700 588767597 535726942 333302085 340037947 327720887 1134119793 694445125 104120908 295410881 593682245 294942177 406477737 571179707 1269074943 533830818 902649982 819451819 166035528 326180947 348571804 647317704 372330393 425895284 666820599 561418531 384294029 661544753 26961880 777571789 620525872 519105233 305180278 1457785027 442474236 1000862596 528834460 617851071 783226763 749371486 657194927 776829940 346082294 564880884 457095557 213943547 434384940 322864506 331680832 98909010 642016105 1052704946 336905090 451305920 549726603 388280877 814979525 111808592 700292798 1078542437 984420496 845635066 1306425551 59379054 187171312 578215407 458367452 565454303 978545176