7000 714066300 996579058 993079229 633061938 245399556 288628512 296228920 585558436 149534948 877404680 738100856 615298836 214409798 527908237 79897166 202338205 457178513 333325795 206153733 148150155 564888279 70882135 797023954 122798619 640098514 725971220 430254160 660543973 301476654 779637809 528928029 91990003 734970867 873951770 730519946 644227475 266049009 710222262 401075641 51880090 847926503 938267349 867410604 136013712 601657991 242061339 384497152 804816443 589763884 814910529 611416279 107480928 683816902 139619688 590508786 931086887 853311396 821069603 623492640 508358790 49258625 55360753 840317758 755613824 484319883 976549130 950001274 5375419 986149295 766094879 501279204 330630061 211375094 634053943 246126062 707716982 397630560 557349153 112831141 179913821 499682590 271475393 325364009 442452656 38751619 477476003 6872737 58301133 834850505 186572920 487322167 90925282 740934128 281105751 309656389 131352295 615286199 9933581 971889268 252044540 366969007 127461486 625291518 928774054 848444079 137399818 596420165 894866425 781104950 778795415 526134517 847589715 670662128 490534694 28247764 167828686 521808693 131714997 614638765 453230541 25617874 341250195 190244447 952600501 897670077 182899995 492106606 683453206 349831657 204651220 453509376 715154023 410590635 419961404 67951447 962222484 921352448 399397438 96655925 261657534 348435207 84680317 757879051 587796830 155039296 12871227 965394376 960531808 913920295 142736199 581022247 554236387 108784217 227261788 412851283 511127406 52806730 577985601 137371069 658209669 294165234 328824315 215811304 51597702 848449129 509900274 50438408 744535459 464504143 110923073 676617295 499527770 38234167 666229418 309572353 808740885 598422034 156950028 543917122 332145611 207975467 186205527 488783376 93357103 729801629 598266240 176217603 126557615 626877946 790606745 558157361 232624162 400672159 624276636 230740705 73143595 789235437 420468894 67422671 526756652 78979569 960778551 916071196 277193202 316028469 356506528 149494452 140941811 586384108 985003612 969719379 105277568 690325128 145364138 571619857 221226921 422050905 774054090 516661684 301577867 270993352 876852145 736636221 795026096 566506400 806053562 592353448 644154137 265393029 240202163 388890164 761507233 494877890 905577862 799897455 145457358 571052438 960138771 912967954 957194532 906398433 390402240 106658779 662891595 304697342 823602479 628044341 665499233 308235839 830712986 638385704 582276566 142067708 497730605 36320397 843757482 663002824 452500648 28181272 37111588 892797725 342020327 187778808 642472652 263271160 673718341 328103281 298431420 279094909 769350003 510531062 557697215 114317444 448866742 30172555 706511503 394857717 812518735 607493018 935063470 860947802 83089736 765689287 19367690 943261735 75432248 785414151 86155377 754993710 421081497 67242267 13617137 964180922 17465336 950057016 487715887 21777494 61578400 822160141 575598840 134742668 436615172 45798310 558076852 115721000 616402588 216363066 325510605 222857093 383407447 117473338 895095793 781329228 741712356 456274852 707672210 397325027 372577372 130496673 133638104 609999145 145121222 572483030 570766867 129816111 824780167 628797582 932243018 854902614 886328413 759208343 626977433 236725395 669317354 317081580 37207723 891878372 455564202 21383179 427220005 58502975 525570406 76524037 350448045 165423837 25576935 923195661 942620275 876187563 341070730 191203480 248985341 372130715 875865930 734294604 509603064 50107101 705330735 393735355 134387532 608540302 594016029 166078499 49765622 853494939 799025476 575880270 987679871 973735651 656359742 291424148 151846695 555258751 478679671 9533439 123284797 637656742 340701361 191791867 811623499 605979658 283457437 306911425 684312977 353256068 57959815 835243251 924111662 838371815 314891448 245421791 518953668 64449818 487362310 21141395 527214337 79505915 786026777 544577842 211446577 441916395 944047254 878912527 128223412 622850682 982290885 963297926 961100987 916248869 520583616 67863805 585740626 150192821 744427011 463829373 206783811 449804058 190074512 481439586 479518173 11405467 274753824 318224373 138687652 592959758 439199187 43614736 602727283 185642664 554839117 110505928 93148176 730957507 410620080 81929021 128850410 621074462 842735339 660698265 285061770 305340107 505872470 46352340 5299829 986565433 602066211 183052230 948553203 888910246 379973098 122832949 149588721 560465442 291055258 290891312 135334438 606009228 913489007 816131506 190141130 481103591 35077670 899357471 947242555 886875283 357082482 147826197 20182306 941190809 438444449 44500733 188166130 485605406 279943754 310307980 350222490 165558033 729652261 434263228 859647521 692098195 225623273 414937640 845775681 667106554 961564430 919093692 571176229 130475461 390271993 106777090 465869985 5123539 20257224 940462132 952372098 896770619 452598080 27449636 323251931 229760021 452209579 28816213 63235630 817963688 69483024 800425912 888888059 768110559 766347410 502130893 980275631 958055781 232792322 400386272 597183714 172874524 850736682 675527545 692561764 368408287 18991117 945125016 958761865 910448892 33328877 903281859 292535851 286042584 748224260 469700771 395573029 102153849 999007309 998362893 541643390 94802233 138617786 593077611 124657900 633468034 654683165 288289120 500965892 40076582 233493138 398335839 584620746 146974359 505258304 45874819 854264102 682450859 227693569 411377101 517153606 61520907 76214613 783675640 852818939 678266964 479078143 10750986 677307444 336306649 369185960 133233007 106809236 684722523 613383899 210709334 351702189 163538952 682912527 348903148 959252820 911726411 851139666 676926750 536104005 88750411 136588099 600301906 405753169 89377992 16009205 956666679 972560303 938062481 64198765 813986453 623950533 230304697 368250280 134660138 432801129 51210564 128275939 622623985 845334063 666264309 551399302 105473174 495834398 33903809 898709279 787601462 259423838 353201042 413836783 77583824 579006743 138205234 876338536 735742535 804748159 588937574 30553220 911093133 69585133 800343573 634925719 247546848 936644695 864867822 825798169 631462650 740732229 453689230 992803310 984833572 945903772 882692105 623498923 229625924 594327364 166193253 193815635 474347086 799206870 578035612 166801396 526432518 418986852 69117833 740923490 455209678 777619859 522526710 742359431 458696433 551641967 106151309 339565116 192618588 548784998 100966309 174322062 512890463 679685440 341515615 705404957 393914738 966899216 929972987 92278331 734197095 531543641 83612212 735946708 445917533 347532230 172842905 880652649 746720245 677943568 339309975 315643354 244948355 133840192 609443610 472347630 1251451 674037271 328540974 658266418 295308841 396449115 100187277 533710736 86073258 644676773 266495543 392369869 103204661 385191462 114523104 377313682 125127219 271644234 324746767 19086921 944863331 725337979 428455396 64454540 813001029 134681168 607540320 727315211 431676105 835413858 649180389 200693351 459189401 139023636 592344259 915052406 818886913 818810495 619687878 759509051 491034586 658476081 297441760 519219031 64656665 746395146 467266615 100700857 706042477 978397357 954322603 237584489 394645614 689355358 363747213 243039688 383705281 81242380 770620527 321866786 231594079 766359356 502310009 627533043 238311352 543643723 97160793 634282666 246647675 398481831 97871545 561042153 119081026 698660555 382866240 395625943 101192052 722598327 422791934 52955419 844473684 940060922 871178977 818273480 617532858 197478833 467591358 137136587 598493387 550265341 102943326 878111984 740751291 779595127 528598148 318872122 240079682 673022102 324774638 889556113 769020288 870094581 720390678 34993262 899534643 596438661 169770688 995890548 990642403 704449535 392862342 182990160 492026879 785520561 542960650 200570638 459829778 488936747 23992492 38582664 887420095 765506088 499839176 140343420 588471378 294595492 283419334 247579010 376087711 969350816 934667920 460345092 12751468 210692137 443297082 254252568 363672207 860588745 694309900 996145385 991438633 685898091 356403528 182451709 493692164 673051093 325252064 126677331 626742397 290878711 291910341 889868432 769277361 762066456 495780486 15586692 958149280 221427596 421426885 940856679 873560303 131969849 613491029 328784690 216168687 796103155 568872828 68762709 803376619 307746434 258846765 884849999 756130493 89263590 744367423 965428532 925603407 714523866 409109536 761370157 494455271 121084656 646161460 571692581 130807120 359939462 143723153 656453190 291879135 732409348 439148270 270478136 328619393 106420278 688010406 19308367 944144167 698992893 384028475 157749069 541946363 881875284 750560033 35390737 897692173 706655485 395991349 925716312 842268409 873217169 727019102 431250652 54196928 481559141 12995251 640589384 259329102 328041330 217143328 834536125 644649592 518059160 62466504 605121043 192248409 640259529 258512030 664530696 307190139 18416340 946462894 262709690 346219310 302155175 270250523 370360521 132342792 441276076 42053242 1960591 997058698 798844161 575090428 385292648 114395588 40576048 879328126 530134538 81977241 695799187 376752775 904920169 797793434 481077713 12936372 59323838 829058158 238174677 392796555 409485398 83599823 601289450 181335125 947593149 887496683 473736648 2667318 924986127 840283089 895139814 781798338 305567383 264114892 557419072 113755700 521422439 68514758 225952261 414415004 597005486 172790693 18496440 945961243 583724642 144668212 374805767 127890881 255959099 360225293 322305768 230804378 174906601 512143199 864052458 701507694 478287705 8194744 502618734 43122248 26695714 920738176 169739998 520562721 308959382 256063431 28812065 913161206 260158864 349775119 601797425 182567998 124166914 633982546 945160314 881350052 783859763 539006542 315329793 245374705 639044296 256469709 443582277 37867528 544201768 97521638 683771620 350680825 16618266 953197443 368933491 134176945 121169821 645263563 581696379 141221024 564397315 123183223 960487120 913485717 123875222 635341858 100259429 708287303 94332886 724634592 478675660 9156595 578347489 137668151 32800047 906102938 846488258 668313359 129424988 619247441 850942162 676676505 545569663 99459761 5711263 984820572 344914600 181160451 728924155 433070691 78029211 780490597 747760215 469651814 255958480 360404588 77165644 782356415 973797972 943468563 700869607 386073601 991577380 981298855 664340458 306866160 804390655 588452681 791721003 561293726 60701596 825739181 810384922 603676913 148387538 563556111 569285189 128282051 473206428 2273112 295208295 282015618 459829460 13262797 293604865 284100355 166520124 526984527 705266010 393389129 693661496 369694178 459636630 13578657 951852561 896427135 324749955 226641359 587209992 153240789 967924940 932908331 274285920 319204615 179556342 499846362 170675562 517803134 550640881 103197134 505786709 46202621 577025167 136855554 287100235 301105536 804738455 588797263 571364482 130571978 871074800 721663097 614741651 212618973 233390776 398555637 36787808 894554996 551884142 106217986 782289715 536382898 944359487 879407952 888177420 766802246 375847219 127193327 166921609 526202351 406195074 89277044 526924100 79411268 161807423 536476373 658772033 299398960 861901626 696874396 803575957 587343991 321859975 231718847 237107208 396061755 57713457 835948512 180348980 497316579 504729610 45622394 646710439 271165092 286909813 301369290 528088070 80148020 710599112 401805024 620441173 223700455 101229216 704736168 912790066 813837194 708854855 398492865 396108298 100570230 879140441 743570606 788938561 554795236 457928142 17343010 122002767 642937842 702998314 389857035 472290374 987147 926502927 843324294 942484618 875525982 568224045 126758998 579940649 138773150 13707887 963863875 867817052 717484483 235556185 397588790 540634506 94315160 967770171 931615677 698209615 382153837 414679788 76763304 772202101 514852822 753568552 480816373 197350246 468269307 720884673 419830910 520485254 67421675 272937013 321333097 343300739 183788696 793995565 564927055 876333094 735550131 712682535 405132701 606821189 195288881 370780255 131781522 379003189 123767137 865014895 705443958 962983933 921553654 208872337 446614969 4735369 988387218 312569976 248658258 241560161 386310341 751026535 476986614 165808244 528928860 145941635 569807750 919409631 829318939 36809555 894180391 870773552 721124380 733820601 440601808 81668695 769791966 669206202 317005881 493042199 29816020 7938827 974853886 411475412 81262954 38047480 889425931 261385382 348736742 413480864 78259147 343493214 183042694 79693070 776537465 9303066 972908372 438238361 44615054 168936668 521649492 239574005 391314673 310312366 252439420 554485886 109574826 5690660 985220257 66428102 808997757 511496101 53883621 149146389 561001845 322129355 231140401 218470786 426993318 926371624 842376751 961227015 917496339 740098692 452127497 796878411 570931707 241752567 385508624 112230762 673632083 983868130 967239164 78211742 779361271 153830163 550625524 447841291 31621866 381724972 119775171 561478225 119097776 855130801 683142744 115942061 662920670 758815066 489679454 518811454 63821625 216647661 432018781 4215273 989774468 528105028 80541883 69960838 799705523 186560173 487767304 975902247 948195589 95832210 720658718 118925447 652643144 780515680 530274975 263732395 343687970 211841100 440717394 310990753 250792677 791485702 560716799 98336436 715125413 909333610 806725962 19973618 941194558 700984017 386637366 82848264 766113624 618558504 220732815 227162628 413028513 102364372 699130744 508915061 49635423 951001490 893622174 170438459 518081203 441776880 41036651 463262039 9843979 156037556 545875115 804086668 587838957 850804918 676316244 413986272 77375578 795386289 567254637 133773889 609861828 819098680 620907761 279568692 311409438 497948265 36835243 271515602 324855770 684342684 353935079 325338497 223716789 442099501 40454677 327382327 218705361 287228406 300539825 426467583 59816657 878436339 742150938 637825510 252470348 181803240 495472468 264278468 342153518 348245139 172069005 281356051 309515007 723077903 423374755 119689273 649915782 857288965 689000535 212172875 439758623 61528763 822383465 174168485 513142751 139353818 591515519 964173043 923811725 343568793 181815856 951184946 895173576 163955526 533031864 606156442 194093684 722714742 423004719 801105731 581250217 532135100 85286206 464095388 7951544 26948438 919116225 313717247 246735739 694362831 371963688 412598989 79705993 16313736 955171568 837859938 653297359 742441305 460148406 976940078 951210419 919773438 830941959 746611957 467599461 994088220 986163431 471924607 763279 341705384 189343204 659765235 300638126 787146253 548410689 119360758 650849845 292436502 286817735 823357792 627243800 550194564 102758906 648893667 276083785 677323059 336406135 255783296 360536809 402421739 94358698 106780789 685151893 382476757 118407857 1555385 998112709 462135016 11051389 429081844 56609595 530539501 82397939 502352790 43072634 197920398 466249050 238144410 392887330 310438226 251984839 240572474 388542574 503305665 43836976 976014586 948334660 573456829 131817511 887321838 763199882 703379108 391328501 634806388 247351189 24054348 927160128 303544313 268696204 804769541 589363971 765253496 498972996 146749303 567360885 770114629 512331611 650139411 279787442 524408110 74615196 912625540 812643211 344520257 181702151 291733941 289207205 329547933 213667040 452283976 28495510 550846293 103289726 382444182 118753935 749961197 472937424 959135672 911211390 56861164 836731429 298996720 276323117 494973082 32632765 881433690 749685022 277231879 315502237 73722201 788578845 489830773 25887107 935898381 862514756 763049916 496282448 268099257 333730965 538965678 92639148 141314488 585489581 112391584 672800145 432193015 52374247 151196660 555557069 108042316 682635068 882003167 751836838 407015577 88198586 64091043 814518530 542193509 95737672 217847038 428716879 281815491 308266152 224736991 417970764 167795723 522299994 843298693 662764520 227569555 411938568 20594262 938239628 21651244 934384773 791657585 560970189 590879541 161469551 374793142 127931559 506087925 47063843 18770662 945290776 869084226 719542615 933000527 856590317 209059345 446025397 4000878 990613372 803163575 586428688 725642105 429404451 217347696 429952806 349566041 166645729 637604304 252177844 909777695 808335277 740845459 454623914 840536053 656029179 160202557 538783370 847152608 669291978 834743414 645540656 997674048 995726686 721078700 420396599 218616529 426652726 484011546 15616991 926403801 842676457 138073398 594675163 143647823 576631854 560215426 118146047 483036682 14645738 389413529 107674623 94000644 726271142 418855776 69848518 842464393 659857384 919157810 826741304 926967878 843957395 708297174 398251464 312201443 249246918 504701154 45164854 824331756 628248924 846089847 667515041 131502491 614976904 676017983 332278973 103313386 695638365 654746695 288540792 346093615 176621007 605616995 193030857 964913989 925244690 606149498 194060218 443818088 37745920 743667728 461772623 467773851 3059919 614891810 213315802 270932586 327957318 299090696 276021353 278510664 312101345 853005330 679003053 402651927 93968874 275427016 317453521 747283936 469092289 167563411 523380164 374336559 128730259 766119027 501352427 672618610 322285808 737306355 447654283 244997759 380890929 444905064 35934752 856275605 686528473 604244066 190823920 568772873 127743568 372292416 130769788 928420984 846351334 309368456 254899625 123056178 638437951 550853122 103358798 205197453 452453124 316172772 244287037 968395819 933045480 716717008 414611664 590812709 161317389 26798804 920453103 24645766 925638490 213617610 438476649 349559131 166874934 653894211 285621611 264449575 341638968 10312715 970662551 995188251 988403824 717549077 416074095 12117055 967595522 58954819 832335895 305280421 265076814 80827798 773014196 410054532 82728120 607706580 196938329 404318554 90950933 238649283 392171008 20883700 937184246 386390161 111897256 132416391 611766356 88390427 747705465 781752765 535309147 290049526 293302265 87770258 749696217 182474469 492840000 338957183 194088757 684945893 355132646 125603749 631344724 436495655 46119920 799221581 578154006 714497997 408603213 553864508 108048844 318158470 241402330 965472536 925685064 790944923 559257522 123449152 637028675 229070315 408133687 792095693 561418303 257465344 357757817 189326308 481745063 91307131 739162396 937211381 866060536 987628649 973571821 71053053 796393838 886380623 759678574 946083460 883882509 65696074 809692215 59014037 831610059 101463019 703919840 498879183 37359210 852202731 677859900 701646281 387673484 521572292 68530505 92504409 733790998 358843894 145080545 673864974 328344121 664861239 307335245 93278728 730400136 211950341 440461461 132963608 610915492 452261674 28604144 66637500 808159695 952395850 897426150 49320353 855129286 717961099 417361987 574503989 132788895 449260116 30160087 576863167 136480062 830795815 638928664 485241118 18311453 593287722 165100679 251339978 368032181 356058229 150958720 386173509 112421956 179185182 501375053 67601965 805740966 18188019 947617848 178653647 501816484 19313660 943476066 506978713 48035533 531752922 84190044 682934934 349285386 926462079 843092438 699905983 384574099 708919975 398676763 72389117 791012725 997863263 996295324 568239879 127174616 987498945 973113933 134841180 606674177 354348578 154881524 521665426 69088902 857304438 689047710 581849115 141399434 380372509 122333825 21041472 936858180 425579636 60422940 663603505 306376409 912858559 814273974 495248783 33364395 138162592 594241906 525742647 77074123 149577587 560742763 342913029 185763089 894487120 779210495 845611507 666865981 152543531 554405539 88731288 746095837 742389775 459264520 35884083 896762218 94257762 725718761 772261183 515072513 352748139 161013635 200006904 461692613 300201165 274312430 414734571 76498143 945111998 880310337 564447376 123935632 7463595 978051569 665539494 308852335 721877813 421258529 80884458 772602366 563231389 120853635 771819928 514303629 116124600 662371055 309797027 254256195 387564290 110718089 769820460 511341280 452062567 29080624 85453666 755610067 887457467 763800750 912838687 814120171 399298964 96860642 150955618 556611892 585434173 149391909 283517851 306857412 246806802 377619724 584375184 146305823 908384969 804471873 503804857 44120497 638763358 254625372 389128257 108269623 496430255 35110163 553506987 107471468 211201083 442801203 703058088 390134578 3576788 991337831 525766375 77152440 677098327 335577214 98923900 713825347 132744974 611217016 230791848 404358355 842254008 658425939 505230022 45783703 418714023 71453660 100044090 709753492 896306536 783895537 595919715 168283727 486383184 20137540 804850997 590235335 488051981 22113312 4616903 988867399 825316457 630190289 604276424 191240266 117570502 658153857 120663901 646381529 94776930 721589076 811913393 606699500 60161457 826639391 376328731 126388791 414474215 76915111 813383244 608719237 409114586 84182611 956231003 905128339 13323029 964686892 853768799 680720523 372482429 130622571 407757102 87246522 914760404 818359814 408319396 86125303 770085622 512047987 454916888 21999736 985121251 969876269 118769685 653414696 225545006 415765589 779145929 526381657 560788396 118497274 367005711 136014263 254623100 362473522 747506425 469329220 41322295 877262369 180228021 498208827 381127379 121198113 59192511 830097210 464016402 8382640 864172041 702063549 853408138 680197642 906926828 802204375 241490288 386698676 689238167 363209015 917612244 825962295 786023452 543750254 564178529 122845538 534349012 87528625 142516916 581982440 737501419 448553068 821412717 624249867 543202225 96645626 810483582 604447861 543429398 96812101 780318250 530138612 933306942 856982313 282065614 307552711 5804274 984512594 756090648 485915371 40976470 878571983 740744803 454117731 554354790 109185981 54930149 841661829 261807085 348225651 279060380 311879305 89021942 745153785 47946537 859579736 62530757 820479891 808526353 598170785 644619158 266225031 299149248 275729136 243698640 382280268 541713524 94928920 285554874 304503133 954011738 900211158 205786941 451935981 492204820 29486023 371808700 130902778 829114700 636432302 521587966 68745372 519115409 64558081 398352584 98265822 903770567 796527885 189200742 482349482 695958509 377998961 982086948 962420359 436365327 46344640 372997071 130099974 597284863 173096505 930275412 851132510 218495948 426858569 230048864 406454255 312242429 249201455 850328096 675104160 755608852 484011440 988885425 976108670 443848116 37590082 632098006 244439458 478942945 10289375 104308765 692254000 15223927 959353758 895623374 782742206 159758779 539614750 668529420 314719395 544338162 97853495 34292653 900755411 20795044 937302925 758187966 488927244 650225191 280318889 460341382 12872094 112119562 673900375 282279651 307425547 968112674 933028793 9936160 971646339 826312902 632416856 400911199 95641396 878135997 740962743 951569959 895757603 811313161 605142148 598180843 176139188 351248694 163902995 375369216 127432495 916663514 823936651 942003531 875232469 869141548 719865878 46251277 864976732 75428779 786207894 361254780 142060261 370435166 132191240 92626775 733000361 26453781 921229596 981363174 960881667 90485670 741663367 118453893 654633169 531637642 83761908 201861966 457431209 881290711 749273818 366691311 136926976 743337069 461457804 680052661 342273141 950339231 891750127 835111831 646781292 62557613 820038944 524042424 74321687 582666041 142916783 596397742 169070794 379401496 123164931 126147838 628488637 617060592 217159944 130781439 616346160 596465261 169997271 684628131 354580248 441764980 41214726 974305022 944638556 635034305 247667410 714221984 406756609 671918394 319654694 676022063 332433421 858348845 689876901 479399882 11243636 895591169 782308194 247393228 376136617 732030431 438174457 373054524 130052401 797690396 573381708 897613911 785939708 877434250 739144580 25336743 923849434 918816254 826681903 989482382 977532541 309647000 254442947 636800340 250314946 685750283 356397695 419424875 68489541 905572190 799553081 412553597 79726639 360091172 143429275 746657703 468036181 528169619 80688173 940469669 873147162 967858761 932151569 104271123 692279632 867634336 716347258 351993226 162966783 522279822 70119834 149885028 559015880 820982452 623238138 626925765 236527663 875374962 733461968 657036751 292644029 604078641 189246079 672540172 321854911 216198280 433675693 106733033 686436340 364736395 138158851 811292705 604983000 330375772 211448408 82782834 766448980 871967529 723099021 20252150 941071956 905604690 800030014 404526073 90724938 938155325 866791923 966329880 927680818 286259450 302446959 647050455 272029742 510208499 52303833 367183357 135696081 925660746 842040456 53791094 843697903 238004728 393323034 765533824 499921553 128717921 621584705 654451624 287607515 645784597 269568281 362211177 141881725 487013716 20936379 741384964 455388879 51330675 849484634 779825973 528981773 883025976 754178676 442896829 38355275 62027652 821655300 469847191 1412381 16001310 956935365 796222058 569306629 451720647 29265230 676898709 333669015 72221680 791877903 105323513 689687539 125874995 630180565 795454705 568386034 721995329 421874543 219498488 423938300 620302760 222864080 832263620 640762639 28212071 913829764 154208221 548437659 101782177 702724001 47897608 859828832 50256829 852853037 148429861 562696897 765700084 500657224 296417604 279698212 907135752 803376799 794604278 565859335 524661812 74890010 268552528 333202658 693948710 369962451 517270716 61721383 806296893 592495229 73325384 789156049 1850973 997277895 14316068 961677815 253807569 364101602 426198899 59907721 7834779 974937575 893042538 775182406 373676322 128981966 909089732 806197324 538922721 92367552 76063786 783988834 891229355 771561894 991909913 982153456 788736164 553958154 703209753 390591965 42368413 873544631 750005213 474282554 94065728 726088539 37427407 891574175 808361821 596886560 320202400 236893512 501120325 41166480 228352088 410071353 627423901 237114377 795421629 567938373 689148794 362847481 296081691 280235627 57079246 836623185 780910800 531118741 861540105 695896740 777255900 521934174 512666390 55408951 990587202 979746162 698117275 381373209 817629682 616029290 447406988 31689030 88417802 747217375 226579715 413096932 144604766 573907023 188437799 483993944 626002811 234990263 613611015 211339069 203493764 454859583 682099734 347985279 963701354 923163469 828251143 635309652 999857428 999940678 203429167 455262909 798524753 574037859 320811403 235406175 163782715 533302409 583484132 144486980 865526611 705905309 500227353 39073908 777614867 522387724 247363479 376303467 921105098 834935713 251817404 367327428 492608396 29708295 621224553 226888700 443228111 38190813 821817196 625523748 779389165 526777695 135336151 605652231 64361666 813606766 843233055 662495372 225480709 417114234 812242657 607076639 929080049 848758381 127692302 623831702 917344204 825698010 780825610 530807135 944845209 880114920 953778336 900006323 39218220 883865688 213435363 438485850 76857831 783122486 443381408 38062328 30525293 911378635 501184498 41265826 493682201 30625599 256065827 359831350 706966450 396391121 511227246 53514291 728202828 432210300 874193605 730786728 896341779 784244706 825133148 630064325 113998786 668565630 305547917 264722337 476002114 5582083 554666360 110008196 972699630 938486193 512256385 54873403 459147444 14657099 508772373 49291617 344874737 181164711 321206678 234014260 840369642 655633503 609386363 200208808 92562468 733582515 73961438 788202506 200740449 458659134 696693177 379782425 855939219 684619468 423267792 64524785 452904313 25939742 444737097 36897730 946045113 883297518 909967744 808578243 836268004 650506394 792934976 562829412 526166860 77387080 509133953 49644097 369086847 134030520 638208330 253057941 936047744 864194651 323542736 229146316 67724663 805151556 118477415 654096104 600299108 180010918 904352058 797011601 865765876 707307931 903220820 795238125 216934927 431166245 973622536 943420507 419145425 68592519 770456249 513120949 597794938 175612011 85381915 755973228 158469737 540200925 73605885 788948791 688019003 360523507 639454746 256919393 307798066 258568470 753855359 481262071 102843571 697151641 104660095 691104718 68458866 803449916 864611912 703975226 564404078 123604108 45101369 867367134 576457869 136358723 433202113 50099173 105949822 688981932 417543217 72954522 549617527 102232214 176723393 507252181 512044248 54697897 920871698 834819878 647306502 273178815 847464759 670597803 217328185 430134725 882184503 752657495 172604176 514929813 103605462 694160672 916732167 824535532 3524735 991511063 262001380 347844129 30982139 909359062 622379649 228206583 290099884 293052208 914089523 817627160 140406677 588222324 83350214 764986748 551168733 104077727 721114997 420913794 383302609 117590782 397189776 99375882 652685868 283955499 23104099 929626357 236805570 396517086 10248640 971091149 307269292 260105734 68793411 802822502 915436410 820647922 138176320 593992211 168855519 521677195 11791046 967926610 116393999 661393976 568491514 127403096 733631475 440291135 916322022 822897082 173008583 514699852 94381116 724579514 673009726 324524656 308511807 256712233 644833221 267853208 544712973 98429213 22077295 932527523 103815885 693748896 140992803 586156866 610128259 203744419 463432032 9679218 69879360 799956465 88218518 748344360 715993328 413112901 541120435 94406635 50634336 851664820 75540768 785141412 680561811 343915045 186676391 487187206 121149575 645343272 265716729 339531343 199828381 461891522 619691350 221717081 208956445 446272059 181309454 496414558 228999169 408637226 746330200 466417085 473184956 2119750 378356256 123918374 300697508 273154078 984312311 968590197 777159298 521783101 572917719 131561753 59751520 827500494 798901481 575530684 935849290 861785656 544254621 97570765 698485291 382842291 427469355 57938190 723190265 423755664 477735084 7384868 666671829 309611015 109296014 679556178 802325252 583156752 475784355 5536685 7756579 976107586 164741106 530284403 858958635 691145293 49320020 855520634 136776679 599595253 252814349 365448906 825308324 630172128 107633659 683426170 742309673 458514064 799878460 578727378 989668046 977791696 229772026 406858347 121954574 643410266 819223397 621384547 204131092 454312436 378198497 124012518 803659955 587702815 360155788 143050369 47673097 860467436 792658687 562525146 226130935 413883106 744380767 463453349 512705852 55619132 640588216 258923408 5664211 985267320 798768753 574761142 920037692 831652271 21606352 934845917 525301771 76190179 108122334 682340031 107845765 682990857 390864530 104887195 157557377 542483770 894115671 777038950 17406963 950417366 729852775 435656284 277463637 314231423 792386123 561777134 954087 998416695 772821707 516065564 61263826 823055087 620763801 225104543 816682878 615288093 583413823 144354299 58331704 834470243 89988028 742203613 189255259 482179309 879662872 745216996 535590108 88643668 801877904 582644250 273540479 319974496 316078494 244627247 855789832 683968838 704453555 393209737 991393165 980901220 90057203 742098771 809888777 601589572 21750076 934123027 873245908 727238992 270044637 330835934 867799063 716979836 961175723 917150682 865982172 708221478 104465039 691461775 700664178 385383578 304964394 265886583 783143697 538304617 544589480 98256161 996056979 990883187 254504402 363310592 475702427 5093392 477593656 7203999 84337524 758883544 515811183 60091628 504603476 44920894 909165516 806393315 175957761 510816803 246239226 379332562 410360380 82183776 200982412 458459182 565020966 124045839 945851273 882370381 600029170 178926604 553815301 107742731 219207209 424359284 697119154 380142915 788703697 553211820 882435328 753158522 530062366 81736318 55022708 840710669 65255171 810611161 768365702 507941048 141626655 583270561 924398767 839163352 181702442 495779037 274921738 317595680 75617202 784531794 632827011 244663985 454252569 23233206 258322124 355905106 395606966 101904517 72349094 791712902 81241996 770886842 668729364 315699650 137482413 596138571 6543003 981252182 493706682 31093343 356038789 151226945 110965674 676313980 736944904 447481730 471667636 676376 792423972 562212490 264143908 343097269 890380611 770492249 314881297 245680633 771970343 514581466 27190623 917879062 236157663 397386954 698118012 381807201 63663627 816298948 519308020 65003248 258437050 355344217 899074089 787854003 117631807 657567066 790626945 558547435 837839481 653189613 67525848 805870962 970815397 936888599 97635978 717221818 243789479 382035515 795875999 568453337 469884901 1098077 657429888 293268603 103765509 693860706 786259461 546318195 428966339 56765641 668579466 315217723 299466029 275464569 722041629 421926525 872886925 726043320 386155776 112536414 58967456 831692426 842920795 662162603 496129631 34407164 19859803 942653820 123269523 638328004 230780011 404426589 715436562 411775965 881665917 749729055 120624884 646973516 695466015 376120623 848753992 673661110 387760164 110141129 331964103 208217130 983681569 966579083 598485691 176614662 607794874 197768737 782633081 537172181 878367642 741704077 923468284 837688779 947345767 887377406 759990194 492344844 586514699 150984140 667495475 310953865 549620205 102246681 835566258 649660743 634267819 246450743 555954582 110971825 522859564 71274181 128138937 623474121 712440064 404635895 647533858 273588472 788947579 555064714 454217482 23755257 823311589 626889767 79856007 775913655 308789753 256532094 649795926 279110467 596850333 172455970 148197398 564430296 862978749 698560585 694441897 373895904 165337002 529934568 574015850 132413666 24100450 926508367 631380859 243763522 988062581 974780470 354362802 154539771 306848132 261371159 457358037 18038274 715130356 410478358 994379182 988123209 157954620 541587897 597455048 174143466 938525594 868512018 906404044 800924983 532555399 85610651 90338854 741704616 857823255 689397186 390404406 106332742 649883418 279452424 122258623 641588273 687572465 359138062 973466897 943220393 986765202 972368644 127410065 625566972 250765142 369711263 473548180 2385042 820185477 622350183 963478962 922256236 943151767 877820869 871738368 721801305 46224819 865350594 305889557 263650169 867176233 714365366 122316092 641263560 448424848 30867258 197255068 469129115 61039858 824757003 538430472 91514234 409459116 83709067 558636883 116731573 117050294 659944641 430932343 54665732 24758211 925533844 628610426 240524688 353008530 160903710 588264639 156602442 879556932 745124680 193950401 474180342 364016750 138690372 283536329 306713029 147928721 565639286 590003589 160964065 484114033 16014588 865873265 707606373 268571503 332892163 314434672 245983048 946025866 882822766 14131223 962491501 781676863 534679048 870947371 721427522 531973402 84841902 575109904 134218222 781419355 533053660 67197487 806582719 30748633 911015026 839589113 655521283 145168539 572063078 939601360 870653834 738556722 450007997 511775298 54534024 220014964 423636617 708151808 398037013 613237734 209271220 819086790 620424498 53455955 843741057 241113051 386831794 96456458 719949874 166813015 526356081 610542193 204894728 912371689 812036531 967510041 930711808 987919552 974690706 436692467 45766495 621317589 226990610 763607548 496635942 2238608 995450886 241170251 386771015 915760136 820985787 84060787 760656034 318562098 240402257 375008776 127654455 619632170 221612878 491584243 28826778 2062102 996906247 925580220 841825226 30081550 911682964 386838283 111481062 421960170 65551091 874277392 731021554 374469273 128505081 956112599 905119632 16943337 952359915 347797329 172626656 779590616 528519610 487737442 21976929 362415165 141282577 997002379 995239715 91004190 739765860 857569142 689282148 150654539 557851509 454545840 22198867 885402049 757656151 950483881 892200904 446835225 32838675 681594428 345923941 532478399 85583845 77324886 781740105 120358732 648858811 547940926 100590823 860787229 694459068 328109877 216971331 17643762 948910101 702307292 388665699 712223586 404364853 759880186 492086041 391301331 104053345 259440412 352489971 582767454 143140900 650370203 281189946 96142714 720491721 934104379 859111983 587756520 154563426 658758268 299092543 864926302 704839528 136824164 599374388 11541762 968751003 835078225 646338149 743677970 462435059 354382626 153951505 396236762 100225555 212094848 440047753 388693090 108817403 134729317 607185143 65100197 811111372 946563212 885458993 144650270 573062865 446499303 33755468 646216303 270034991 230525842 405478321 164629175 530904548 896194749 783595902 79211087 777517047 946977602 886301938 397827664 98527426 91980117 735427431 515669690 59854121 106545711 687518936 316392055 243882812 966574658 928640465 890642502 771152534 429844297 55367008 835529608 649426000 296687854 279688919 70291166 798347088 108216530 681818091 738049448 448998683 848146919 672746643 908379850 804452947 36157876 895332788 231157039 404083001 328465482 216621596 248164917 374572387 17043493 952122485 306883207 261011198 822143573 625646795 137942982 595416296 114252044 667744782 140497391 587573748 133995604 608990467 533879566 86184720 677862701 338665540 755227762 482673185 139388247 591033673 615903822 215646516 369681340 132835223 796937611 571107780 14872100 960077705 542315347 96290737 673250368 326475084 595284918 167320194 610007823 201975554 488815991 23890552 345605898 178850636 288126263 298905148 22309132 931442244 103526172 694315119 548042883 100815849 909454725 807350917 75564927 784996702 5260691 986848599 624125006 230615103 6906791 980152599 757884595 487779143 900175512 789189509 519663524 66236187 134676294 607630756 23319694 928635427 563735981 122328956 107518658 683714403 596807297 171553290 123356222 637282873 939234069 870053739 816179652 614878816 774623988 517857188 922097332 836920173 971902004 937655460 733242588 439731436 660136632 301310028 807923225 595770812 889177279 768852503 74373413 787346363 834631856 645162957 950010835 890935752 637263926 251232781 694320413 371622614 453842509 23993392 127561467 624323140 900521564 789343855 120226122 649198144 319500861 238677666 968462693 933220841 878181435 741086167 292529749 286231494 25929356 922330168 664926674 307408477 844285122 664959681 809499315 600524463 126568406 626789911 2291594 995105288 750583821 475850760 573943181 132247464 84340238 758604018 720600006 419479585 864913224 704544067 160410172 538264034 21473286 935564452 550977579 103523220 609095858 199535026 339106839 193608421 624907438 231627237 822678772 626111941 548917279 101048968 985818555 971373131 617905442 218837728 873630738 729562167 465795969 5547969 89896462 742327628 331695908 208942110 563724821 121792798 512231488 54852955 339288381 193468516 38366733 888424270 341055084 191242635 465043693 6648105 707546446 396996796 152462218 554594786 591402232 163027061 398652917 97263162 294053194 283781265 260872004 349640834 902420893 792496180 431787272 53850843 265119148 340956991 681733170 346691911 818484999 617811353 360343838 142365517 368554826 134393374 485319936 18585687 534656594 87771093 167212192 525755857 706280609 394741520 386951439 110937569 872159648 723422586 433748620 49598190 929576280 849848786 102589187 697946463 254644853 362215327 171415746 516114275 117759135 657405064 305557771 264683470 637036301 250576438 960852970 916169439 604991724 191814335 976587247 950401976 951394405 895292863 885051882 757057489 717055219 415067559 408333848 85800295 994937221 988333072 66853492 807338809 627435977 237676849 363986934 138754104 37821946 890717208 212081218 440253387 119797310 649426383 318314195 241151043 663532857 306276884 742012805 458179593 6446421 981348024 86647007 754015580 389767811 107541557 571675506 130761386 760370380 492911533 356587194 148975509 26859332 919935424 34065146 901749799 493644690 30258843 8235398 974712576 441592380 41892681 385636191 113936307 461208160 12008250 651123090 281994602 468077193 2426588 835284688 648553500 200559533 460162546 301604637 270810628 743135376 460509028 365689969 137582779 118214523 655562900 325725524 222481639 542864782 96391143 86905730 752976307 765602282 500047073 307585549 259347964 865326863 705768708 335108736 202047239 909473170 807502370 353519118 157567247 86452242 754619057 795389682 567377280 742055463 458398282 390596714 105886853 295237277 281935626 102010115 701841500 351217607 164090039 805760681 591670714 507973059 49025730 259561826 351900279 932423906 855153266 130137095 617384687 782569490 537020771 677253141 335879435 464241108 7742037 111233696 675487454 218224912 427755794 920492904 833157740 432294651 52008774 114196496 668074590 134662191 607920023 572626654 131133878 105087778 690469355 338186440 194538743 100241722 708817935 805505000 591087244 103436989 694632585 408179114 86325793 153020066 552709734 117384151 658447466 565949037 124985290 892681896 774552777 414946995 76221685 602243637 183837305 866193973 708396930 810156312 603117632 24240263 926222102 345363466 179443329 121890963 643601511 334365552 204089031 964270589 924667822 452404122 28284743 529297895 81283851 310102697 253477278 297432101 279211549 576312817 135812154 877496108 739789517 859984588 693083219 32097343 907445723 944182278 879257033 444895518 36382877 140458356 587758535 363942763 138814066 872255233 724235891 602567728 184383750 909666781 808166957 263497150 343857860 457247120 18492785 955278077 902495825 796374448 570107426 768365522 507605676 887144368 762423747 441542850 41928036 267961524 334942062 814580380 610642065 272138798 324092404 216932305 431448066 818793947 619439283 112377529 673052178 93393731 729523110 302452928 269951483 667933687 312912896 79800797 776403351 569183562 128232751 559032630 117789744 321115127 234873706 440831885 42249742 213684786 438395333 855838035 684015660 901796310 791813831 647058098 272259176 596722866 170842120 253330097 364495369 242909045 383835573 411909326 80769450 184874959 490453727 873191542 726614259 768136444 507234419 8981170 973551317 125988754 629949486 503343360 44019103 787132926 548157374 756139777 486004865 436469981 46185293 605352232 192394974 965642884 926318485 37004795 893200261 788830772 554467746 141346496 585015575 54944249 841455949 570991674 130096374 507068712 48107114 94693163 721716079 149621826 560065356 608317286 198216822 960161640 913044808 387057053 110913517 366989392 136397073 178094317 504230360 186684807 487115441 395578304 102104361 610076116 202876142 180425434 497175880 777040672 521552022 786139725 545254911 820211508 622557227 787880567 550530626 878647332 742397810 349298329 167533276 712193980 404102925 600866555 181161104 822672244 625790104 503870054 44413616 141364676 584086289 797233033 571350726 486864481 20402006 655881454 290399439 321136617 234662332 690473684 365200646 858604665 690421239 297104322 279276863 348362466 171184943 721403589 421108239 149319398 560945989 145428811 571176645 348857542 168791425 640517773 258737502 357047740 148454259 64131445 814160745 664166157 306856164 105589946 689047524 900032456 789032848 927265295 844070347 5910485 984223653 26198873 921869417 787994595 551228482 38431161 887982524 731064509 437329978 42271795 874445184 316815582 243492520 509980693 50623058 625227481 232322115 494758095 31676793 714762397 409433157 557803749 114370175 118530292 653892902 963755081 923270073 218137176 428302384 34688018 900071867 138064344 594738115 63171838 818571666 848125468 671688108 810089584 602878627 76136894 783798125 495750929 33546246 809787572 601392003 965822803 927090700 709047864 399305134 894794453 780369913 257606386 357430221 967347387 930302930 872396753 724623369 653200335 285128363 126705016 625988951 325759941 221886752 48629591 856920932 681652703 346295891 174583692 512302184 707511441 396753056 126358149 627541140 734695685 442655033 692791432 369059022 263299388 344367608 550589652 103082889 648197250 275490632 393908722 102980764 339522811 193091408 800984229 581177716 386335146 112211386 49738547 853532197 408621795 85610237 930628389 852580557 558980579 117508833 27445038 916092849 751471236 477606421 583309117 144081396 107990313 682760523 307050193 260456898 134692895 607428831 133065424 610678238 246552370 378903468 678047605 339387769 269132256 331782116 200258960 460646886 877739543 740474294 48490555 857250657 958891777 910691109 838763020 654595695 17473679 949998404 743694010 462586383 45024775 867526790 291136744 290768505 409588985 83370312 403621509 91492101 312499383 249035831 121130730 645454438 375423394 127283693 18117819 948102306 345040963 180719260 758904967 490278961 545481653 99103372 621170628 226766128 790544711 557871163 456356570 19692210 770031202 511577368 943317706 877925761 581552037 141121981 975131000 946442842 88190539 748564889 638232681 253479738 285835858 303548622 839484533 655229628 121103845 645665563 71259689 795504009 25070657 924150525 511129162 52876602 285388905 304895165 234573494 397999421 367606928 135444894 78103751 780185007 360125495 143327231 808149392 596133636 324044383 228160803 732299994 438410995 734714589 442852990 819009587 619899234 596749441 171315223 472692663 1648440 955223362 902013278 146264986 568744825 867110899 713996523 292043244 288866253 95281417 720748118 35238228 899210735 359703653 144406024 720511992 419331948 555765341 110916354 678110274 339691292 969215221 934306946 155391475 546482642 554145684 108276959 64924193 811958840 563332003 120971937 875867677 734572103 93247080 730643773 789163385 556359425 750911185 476257101 629071201 241883966 982347637 963372091 649651240 277872698 320636928 236677591 517883788 62260070 600658178 180808976 768526730 508631929 750285939 475168381 97994067 715969604 970155733 936334240 50697091 851256746 443410558 37983884 443883920 37552803 691031814 366026793 893692855 776551342 54180749 842747228 2925849 993239041 154919838 547115325 938165725 866965381 644211885 266028545 861765185 696092562 277516843 313566967 158373746 540875386 963017083 921896964 188676992 483711009 125453940 632310742 670507426 317573915 602180555 183170258 680535077 343795861 633262876 245605436 672486318 321186706 147998667 564983528 618577760 220991906 459354813 14244924 471211340 719530 424643460 62009714 898641262 786973564 951675153 895821992 63181574 818364172 69367900 800691034 459329091 14587250 315996220 244769239 556618774 112128831 255448625 361096039 356034633 151669266 200686865 459643818 196407530 469695329 115191678 665384533 262130552 347258503 734894784 443266229 215245104 436231298 343538915 182515349 556302696 111593594 2149041 996189565 156076165 545152088 602247363 184117299 334077050 205038155 580572605 139387019 407179592 87330531 551259175 104653651 3054204 992140348 700688266 385545431 306196021 262740707 703434029 392104505 407140729 87594696 56114660 837887392 137238882 597319322 503861618 44216173 173535489 513906827 974944443 946048371 357414289 146934944 91588884 736955260 659497823 300135864 887765928 765788969 760013 998494343 26371699 921437657 514324336 57506186 170034125 519368116 978191563 953907300 840357172 655574230 999567608 998929883 478096133 7661984 160320253 538684038 831885581 639874676 842259222 658516043 613374180 210154179 100206000 709449617 645563000 268942464 715507851 413027156 357651189 146642258 665396617 307566882 370582339 131836346 59322139 829424270 884665076 755828147 717702778 417201372 813618708 609514517 229998333 406693305 253903200 364006398 336166119 200167828 582557178 142541117 866872324 712980168 330215758 211974093 725263397 428116445 504233493 44624331 21221550 936352297 429138989 56542113 395281515 102207544 622632484 228611021 768072435 506371030 40998084 878151276 878866854 743243449 388569418 109002075 141668492 583094643 365964641 137513787 452656855 27283370 635296385 249234462 237804542 393752387 453423173 25384070 740204360 452270329 639479138 257205143 487367087 21379054 357105031 147717938 93913603 727144141 982020594 962264743 99352062 712505120 688686692 361794705 767800050 505597807 973392078 941191273 940120375 871632195 973607609 943257168 377817524 124057299 542989839 96583430 138973487 592368277 518528798 62988966 359852251 143790066 52712834 845080344 745490017 464781545 158363392 541074411 22017619 932695008 802646343 585301217 170726537 516365590 298785130 277618059 413019448 79489001 288162420 298473188 732959385 439544542 606850063 196236164 613433020 211030304 841543070 658089901 808832200 598700870 230340948 405844397 973418452 941400223 64874828 812239194 181448623 496250800 815110230 612096222 391085129 104644123 103213501 696439334 256542894 359204923 973023373 938984714 962728677 921423858 860001218 693637024 473207636 2306533 767835507 505852947 988734272 974967562 310726092 251260705 66639519 807354592 17184207 950704801 768501067 508069600 627670887 239659722 797349521 573049456 50848458 850534118 270945014 327521020 37152389 892624432 967904974 932545295 153861099 550098558 546670229 99859179 683889809 351200970 348742309 169367248 240581415 387798718 466816198 3833919 136202005 601095034 210587055 443607564 351784318 163276379 900998531 790486129 826169368 632135205 465616244 5671396 589433277 157862511 736047087 446070227 377010464 125862781 991536777 981154452 755456834 483969449 836879872 651598295 242000832 384852126 679979165 341824694 809970912 602000779 574781142 133008327 191091016 480529273 128835441 621267488 604099109 189871413 973930868 944011030 704144175 392690167 959634683 912238919 292573032 285878577 81906356 769162635 407823995 86965447 766584205 503365496 681932300 347681683 525132610 75572109 291854611 289070193 994172047 986799658 164514815 531379098 236423980 396952845 484447323 16423603 425025329 61091939 7671687 976768539 27279875 916892557 515688751 60024704 292946307 285193560 697678918 380822354 970189954 936824679 427356188 58108308 814376501 610171111 622258744 227856213 834929516 646278614 734693315 442207888 781566760 533480280 596955933 172721450 878266142 741642578 274469456 319081336 134585306 608343688 615638910 215178350 204161453 454003944 848102838 671539334 355130335 152776584 320011408 237564938 854834695 682964634 615035997 214149653 558262846 116274049 534903201 88477487 888437287 767535298 150827716 557543112 179397815 500625750 12238362 966432269 920610079 834224831 716279708 413661182 192351176 478564524 450566887 29518557 983339081 965402483 784211563 541043838 72847310 790082173 39687974 882646216 10452106 970179224 922058285 836721278 59816813 826713944 601430837 181523782 239564002 391401378 29956405 911762207 683363953 349783965 353744084 157402278 482154590 13705651 197737443 466375526 442288859 39950724 198194115 465112192 609975035 201682228 279749225 310986087 232226585 401863174 139756406 589112317 138222614 593473107 79614878 776765980 612658777 208147156 31262744 908468562 846358871 668210136 380436596 122143637 37905838 890351185 520164857 66981859 591602888 163107711 214850441 437047992 862635546 698062135 882714417 753948554 322539879 230368523 675852889 331836634 553999728 108208382 688528109 361609561 23672222 927713995 290613616 292392504 117057973 659879240 738975555 451691302 887076813 761196986 118162171 655675430 886021703 758489163 819729523 621971083 120626453 646864495 760825755 493022115 63210678 818269652 955466032 902984097 785992520 543618779 984518334 969130523 736797087 446692738 238177500 392661539 710689508 401872651 182139082 494752066 953717280 899534001 145474080 570798718 499471308 38103276 86896873 753237443 761585213 495195520 731031700 436981263 482589506 13999147 450071649 29744883 480353389 12170182 352280967 162330327 783864750 539461336 979465150 956791484 781639903 533922903 261174761 348938149 281107058 309604693 183693979 491052122 600246069 179568754 16604683 953747780 915219179 819786423 207751221 447787938 438715983 44398813 160577557 537433463 127530522 624661713 868547443 719399250 834214904 643850515 475202044 4390146 743856211 463257583 193033031 476667313 182471502 493020235 107727004 683251737 62368236 820957602 833267494 641703147 251161028 368390526 116744696 660092618 735117942 443323053 135748692 602937294 771774868 513921054 258060725 357015736 322441173 230600757 427817832 57748804 252176826 365682224 570943906 129917490 91363733 739066934 256657309 359119985 20335420 938895482 746998626 468670294 218269541 427112265 254532805 362792770 523931888 74024915 622953510 229383061 33487397 902755844 334758910 203369260 315630469 245136698 493753474 31392667 763989868 497613894 557473959 113906682 459774246 13487650 949772672 889927001 686553374 357473923 259353481 353869374 982368934 963998404 544589579 98367408 220182350 423082646 651184280 282312135 143112365 579460494 874974119 732117782 86632752 754554080 583106453 143763853 458639184 15864753 68030686 804456184 724771817 428058685 674313511 329194467 324256286 227645510 50034151 853173572 441938394 40824336 848288967 672814582 519410393 65538089 431960479 52813155 43386032 871011095 763535433 496538739 262814009 345755618 121030892 646283593 791133081 559658936 430008286 55068812 644025195 265124975 113230568 670708319 578845554 138134918 716315860 413914870 770895167 513510302 500023567 38750333 979962418 957729138 932703070 855590342 518784756 63736194 679021325 339892828 880458031 746594759 69282520 800952041 539066426 93021924 703268987 390780279 219474129 423970938 707708854 397580855 51986898 847450888 673083912 326242388 165457119 529499282 280056926 309876079 652751214 284451439 947932822 887929552 811680301 606023766 364292314 138542641 121597182 644168382 785622568 543369303 237984613 393428012 146133768 569158942 93135578 731033099 610417736 204486567 488087912 22448501 290232372 292908299 27242735 917365384 176910283 507032641 62706850 819883920 5033996 987302212 325595752 222761699 518148234 62876773 536925044 89511300 612823070 209213333 268180495 333527863 563721013 121704741 855972402 685047970 435075269 47544284 510281691 52367448 182430282 494068180 653366014 285206976 224386639 418444339 83422370 764329132 531136998 83342102 765449642 499588445 192936661 477049223 789340724 556886889 284145765 306020220 736396876 446433929 964085863 923612466 833505274 642150461 928304140 845896910 160357348 538569759 817383949 615948311 544026747 97447127 410003145 83048745 702192233 388601232 954852329 900893898 175029489 511549214 949970225 890504775 534179520 87075216 205945669 450875266 597675821 175367849 446840188 32589533 247651121 374743447 390456871 106167912 685406931 356200931 879476134 745063709 461788640 11301170 858349861 690287069 71868383 794233315 58825081 832874971 842709280 660381347 77849771 781275645 379979241 122564166 795118260 566693142 35792600 897200814 328346864 216753551 780107525 529300270 212140140 439961970 924915596 840146556 477220588 6427681 441648404 41289960 766208811 501758692 867323763 714913923 280583044 309802529 679304534 341004385 42339136 873781339 162903703 533546196 355048992 153065408 74059303 787963871 483427973 15097222 37538500 891101260 791298518 559960240 818817844 619736713 765261571 499020557 998266622 997266612 113943750 668830937 941152898 874429174 456247133 19942867 793092445 564032336 453528620 24656004 356126109 150660523 916299655 822518838 778512378 524386637 593649527 165538619 819217142 621142540 467346994 3150903 851316238 677426000 830125011 637058255 88318077 748138225 74677655 786734470 564235919 122959789 125037692 632762420 402808602 93054768 938272119 867619513 18530681 945609695 588870723 157566292 725979887 430540698 655663284 290302749 596547111 170484651 397051116 99506396 250447359 370764475 424556018 62246939 806773786 593158455 606618726 194719970 487486002 21570361 515352093 58897158 264158831 342499961 121201427 644861006 383802126 116682580 733602246 440108891 780577662 530534956 480782577 12760961 899639235 788934004 987159522 972949576 475080014 3977839 978022379 952669974 117203373 659222473 301075811 272535087 208997761 446078052 572303386 131014260 786570440 547016883 616866516 216645475 630330069 243516815 478445110 8672049 850778050 675924651 531797882 84347157 43792382 869723194 533947247 86518540 442620195 38546318 606082988 193191547 727188596 431524598 59147266 831017546 85737969 755207182 560985667 118757895 989043480 976851294 29702289 912262061 137230834 598272882 680615852 344314280 916801138 824746881 481695991 13206537 571060508 130205403 597465299 174307767 788996184 555302800 112636422 671937515 811990078 606981502 17702901 948820176 531108379 83206435 539656307 93191346 445823986 34501804 880957221 747800909 114333011 667020210 296077477 281089265 322911610 229913964 471443604 81864 966776168 928733840 746084976 466313999 587415209 154508573 6300534 982182143 81207902 771391104 44320084 868530539 45378483 866376833 86760863 753908245 136004425 602012283 718111307 417830268 285755157 303972166 878469943 742196231 462190378 10812363 582986396 143435960 237480783 394661116 695031565 374621245 33541672 902651592 783875733 539510237 189190864 483156065 237662519 393978785 412734161 79567219 348951224 168217157 262191506 346411983 336739329 199009896 983358256 965645619 251262523 368155672 222517683 419657898 884288715 755418700 833264946 641477307 17906000 948411958 80830047 772801610 804373640 588153315 287898174 299160761 580693045 139581096 160492004 537607756 210261940 444560978 740322841 452963061 528719620 81130104 413737016 78169350 336366776 199824699 249391695 371780121 211105533 442965971 121445501 644580480 791599243 560921936 197016007 469345125 314567371 245858379 429329310 55944520 143583348 578140061 96898989 718924846 526332608 78061019 654017499 286152030 91377181 737994996 5424295 985996391 384716397 115668971 890272558 769776687 50846520 850732155 346511794 175954359 984213166 968134147 589784764 158975802 395000726 102282986 779409768 527516202 138062830 595063811 401693474 95076647 146188626 568902937 345625053 177442365 338109798 195847044 503103938 43406912 821480372 624410932 744456623 464078957 611357326 205565876 271125268 327444077 109136399 680239854 591026891 162755981 88555680 746587715 98792650 713954031 502889793 43245094 59979774 826661699 36416788 895195433 631199295 243614988 709683145 400455034 340846722 191586897 496284741 34647788 478020729 7542660 506478496 47905103 658685313 298299411 875497643 733706994 658354967 295400351 522941397 71528804 274140095 319341832 510152456 51446400 866899696 713081729 554193505 108530918 100535244 708228973 304752099 266081470 515587105 59740915 4316968 989287670 969352659 935039351 346702958 175828800 769756253 470722159 802248934 582916247 28029560 914834089 185288661 489770174 324609839 226912365 42517213 873285092 354128603 156481430 899289642 788506805 982255141 962758055 602628969 185402676 815651920 613231351 854219649 682199425 434153588 48951445 219097919 424741209 324065453 228019294 265060062 341393314 421799754 65864623 2540213 994363634 123785118 635622198 957199351 906514072 992076099 982343608 997448165 995450128 195654451 470520925 82994074 765858425 551120579 103912796 246305174 379141887 194231276 472805704 770626983 513443352 127537795 624534839 478767176 9842451 54588949 842216846 31145410 908723964 81435812 769999000 262179834 346697311 292523214 286461300 514213734 57345758 490161842 27448715 735144081 443473832 806919489 593287864 362946550 139849572 181938228 494854428 250546685 370604435 672756876 323458707 992233786 982924180 565929677 124873019 91792702 736075416 891170598 771439502 337977431 196695348 81174834 771486778 289666528 293815946 42154784 874969982 787573862 548844012 919190563 827750585 56416987 837440680 625318284 233260133 418494309 71813752 600456234 180488862 186944615 486976172 955980828 904950506 151460933 555322035 418875233 69376556 622112844 227249353 329307475 214160721 200085825 461151829 593090039 164766884 138573805 593203809 82235948 768132425 672703994 322931213 216235184 433494952 711656866 403329672 191113265 480387931 272843361 322930911 304872563 266041021 125677095 630433197 975890614 947827804 511746875 54272572 188269171 484884051 168784210 521745069 397274937 98991713 919461321 829463687 118443936 655205736 140744452 586966655 778026801 523512165 803379414 586780911 491906663 29431068 7132610 979418485 921384674 835698363 221988560 420666530 951496937 895545056 577577282 137093542 754336920 481467364 191231044 480305981 524353131 74608337 715436780 412292809 536565115 88881092 193306322 475227184 981634391 961753604 570155746 129240576 217524576 429770841 6302655 982073300 418978596 69190191 87400166 751373559 973437532 942334109 632993216 245180571 496626958 35350319 649965392 279690249 16698032 952626048 221684893 421120659 701398184 386745086 688178704 360628280 997943419 996804558 671568073 319090195 99193671 713041623 484629516 17190637 345046455 180516484 836861643 651297653 396018235 100611643 965018800 925497499 270428829 329052286 955347084 902744388 381663079 120184781 894220622 778294424 938977758 869417835 519610294 65579501 36120256 895731412 428617413 57157232 374546180 128238352 581194255 139942154 556722708 112217244 325781493 221652811 772740056 515396107 208213023 447433556 243560142 382375668 526339422 78250318 102198389 699795901 146271180 568528699 373846420 128914162 303680917 267213962 921570739 836204448 198180791 465339841 343443626 183079927 917360580 825815108 101362330 704044523 799195950 576483585 51517479 848864550 13844972 963421486 853811856 681373794 584646165 147293015 318101262 241854240 448097744 31248096 635058920 248965182 45280858 866846389 913480795 815369942 622346961 228058279 913097521 814561332 240736583 387298896 739490534 452021582 104517129 691217424 723729940 425101560 897087196 784798679 789075854 555660380 421332283 66461541 9668820 972588418 5930441 983976382 260129798 350415174 55700925 838503833 77224629 781915496 396488921 99699969 123748270 636570494 83603569 763419452 513759010 55836224 866790647 712154798 6708894 980623778 9701537 972389810 501867484 42255108 821352852 624086375 929159603 849176568 460548355 12584553 450369235 29645757 978027606 953146124 175984357 510583361 137360553 596658316 454930178 21896324 101702601 702857104 946672840 885552700 984144289 967687457 907857241 804080918 568175772 126490961 596823121 172257138 31142636 909030880 966348597 927751001 521751469 69176466 647107895 272868573 169002772 521279720 394730998 102304669 349474127 167278711 709539513 400413947 842784355 661316836 221410509 421951598 647843033 274741381 431021273 54478372 717169190 415421290 270323803 329910249 335054232 202750124 917662566 826098149 781682112 534718524 44065963 869247756 43273531 871810108 649148246 277088616 838558949 654052593 729485679 433572968 939347559 870266107 286357953 301667238 838500858 653741963 695088805 374743885 627558256 239215549 464662576 7267462 667497451 311354337 712961218 405415868 334724432 203913996 489083347 24229537 586587030 151475598 120241482 649125523 327617091 218264460 982368588 963757775 457174957 18622519 859856076 692456403 360321609 142598379 568588913 127511803 517735521 62195659 43013333 872767272 239799549 390592069 240303535 388662128 932206045 854740087 44150903 868607261 680786052 344749408 718737300 418500242 391875063 103442229 536679191 89426137 620284031 222810441 513942333 56819406 983113129 964965567 680253445 343532153 444817845 36651613 250700941 369957780 173599070 513690832 38833884 885880461 116483234 660976089 167433236 524567483 912488034 812141154 729196344 433451718 964622243 925100529 173667857 513621972 186266897 488202207 213410114 438852113 360265827 142915546 368078410 135066493 117489345 658416903 674507910 329441044 812966206 607680987 243523297 382401289 171947829 515131686 586436942 150927364 276182976 317060423 22303882 931844634 788540263 552144509 96631210 719476019 889854948 769052547 741905267 457221699 396013347 100845616 36084128 896030646 111418131 675286643 446838986 32661584 468980129 2015316 291372544 290145528 402711256 93689522 553195573 107395269 540226909 93947131 283054983 307023695 353278639 157985911 608201104 198044308 242008288 384627316 26000384 922250855 842947898 662329084 963606889 922746596 469724045 1539412 441639992 41604723 248524837 374031467 129368580 619646544 126352918 627958414 122971463 638982740 54804843 841940867 850604764 675248928 506278231 47470410 920171549 832852388 109525236 678479806 455741992 20994180 265320068 340353425 445104772 35396714 916530209 823515190 900982898 790347129 445218083 34945476 110986636 675818007 498924942 37538322 931092633 853516549 863451906 700008470 135600059 604485971 235274144 397799175 348372206 170496202 618329598 220195521 683572294 350525956 486177318 20019900 978943226 955268237 545429369 98692305 142877848 579840911 587822855 155387930 938796909 868867940 956275867 905333821 641735535 261810158 321226341 233668856 814815534 611053134 185670754 488936382 414377485 77155792 801371700 582021369 595768961 167581536 250800347 369456642 796546632 570176213 957420741 907402973 165508322 529338314 249726850 371171748 34360973 900561180 406548680 88690414 385177622 114641727 47455272 860992663 78308951 779077633 391910654 103331283 261699344 348287196 97951122 716628333 484452913 16506068 462899588 10427995 401970784 94687168 237248606 395050937 44529783 867624227 61111120 824704028 667713972 311962634 416311636 74553562 232025811 402181306 100693024 707330942 996948411 994979606 995464840 989686252 711360216 402902417 585021907 148062032 136580909 600565992 904872348 797541144 369716329 132777626 388061818 109698993 916014954 821786942 667860118 312298922 21508080 935099714 270326609 329424125 961999947 919915602 484507055 16980335 497938203 36569667 568328467 127297678 417200521 73557274 688827283 361892951 668809823 316074644 186983742 486790990 41243256 877618314 83939799 763079022 833516032 642594999 796740937 570643055 865793821 707413362 94527582 724250860 951184214 895111753 358127196 146289128 130973576 615924076 828092134 635188796 996592165 993610575 21712160 934207562 740783790 454451087 421672653 66269681 669638789 317115812 179346095 501057136 855340892 683394957 848338876 673243216 798094780 573773105 132025241 613184348 357368840 147223646 906664765 801117427 446808581 32903616 403566673 91534506 112348419 673399128 228865120 409250066 514092329 57101281 100871729 705373407 14773976 960869057 137930468 595584814 865959327 707807305 584208252 146262036 996863445 994705070 433926521 49263269 54192886 842478860 83973214 761696102 723697930 424773414 738414697 449961765 480374319 12349739 118181285 655615125 858667663 690587174 84322412 759167331 314207927 246296327 959773735 912709793 435350961 46814503 228802476 409855451 786835271 547136967 740462545 453529100 763982843 497206249 802502695 583422678 687610651 359501087 43137987 872180935 333885952 205252180 20290155 939619915 551561197 106022603 360659632 142097256 818769537 619168290 7418232 978352068 596424937 169373586 359833283 144081426 457006704 18786031 859950187 692504448 348934550 168502836 758852976 489763829 537967735 91272337 176701668 507620831 853960673 681655808 635100013 249052066 224454628 418358633 905487995 799248155 215099432 436594502 581924814 141889063 46872545 863723637 425593805 60063592 301543555 271397039 989865177 978066574 282913645 307215137 621541309 227080197 7655272 976861799 471492064 165956 999009946 998432980 303616157 268490572 125553088 631666729 802655465 585614843 174076223 513306556 289309137 294256387 640659873 259610070 445278725 34869987 406675423 88642747 515681606 59963609 770473802 513188813 411330662 81461064 912281701 811290548 800907867 581007205 584945783 147753570 9843271 972365814 696300632 379027567 100578059 707682448 362754967 140670567 951747765 896072298 884252319 755153034 617795013 218310034 235058324 397969741 996477824 992577757 759635270 491338983 335209161 201788586 757954933 487980456 998655194 997895688 366938408 136655104 746353296 466853609 38321904 889231435 675034045 330596668 511366178 53817753 497415144 35532489 818090813 617275320 893887018 776991211 773976173 516350184 620317335 223325178 214037207 437800430 826393233 633087464 311840974 250074160 343417570 183445024 523820017 73212587 552588389 106738687 421054536 67348353 177449948 506246552 513471101 55816910 864236879 703187965 705772385 394659093 579505869 138612289 598941315 177328323 316627709 243552776 825367659 630964841 976131909 948833630 542182336 95658331 945119926 880650126 368232217 134868064 926651818 843843534 238416347 392385302 171681220 515514862 73007327 789334576 216042336 434006454 162266760 534924326 779557989 527989370 92592132 733455055 783066456 537436961 479037507 10441846 66115642 809378831 723601742 424423068 546526417 99631161 3044131 992422625 705451732 394438535 648028853 275316588 277555119 313453628 783684758 538639729 183082654 491724198 162655377 534104493 333633521 205905374 182656941 492378046 784141252 540550437 999425451 998883492 308836684 256339117 455945025 20100598 970164467 936629917 10770386 969048766 803541119 587080875 856439031 687480075 809765386 601336072 105361907 689348661 113104254 671286139 645937327 269715629 353767650 156507944 680166038 342868066 27073945 918382389 371370540 131357814 308392664 257165470 768030158 506190214 849492580 674359681 525450681 76234809 578800943 137939815 259954616 350569661 471661914 506321 403355876 91863092 656252852 290990463 25486548 923379547 917152276 825097126 243108482 382986623 665533964 308611506 505381757 46162745 633032734 245252638 973334825 939782276 283879275 306216144 376304055 126625773 149050986 561596835 453343944 25508372 115799556 663702800 119390122 650740748 349283746 167613919 275772222 317359233 732580243 439415778 670159575 317380559 102545440 698069491 51723114 848175900 660805129 301666218 288210630 298240029 718384239 418426909 415965256 74691428 827360970 634139528 634385284 246740673 582966340 143358743 142298438 582487224 676990075 333938294 846100891 667814884 854508539 682846200 957490194 907746823 468127775 2342070 687635645 359767684 781283548 532504022 210161966 445329539 355368604 152332114 119608935 650304887 232224757 401950603 61007693 824913659 945129310 880754587 648201840 275936701 848411146 673623353 415034129 76127566 157156973 543728894 198264470 464716417 166797272 526663004 124047483 634248408 55519046 839124379 511724863 54174837 657085608 292857978 131882030 614288199 128810146 621461490 646812178 271437189 928738604 847978435 431819435 53560930 412364417 80084172 814933756 611505539 794777497 566143872 852694486 678004046 122854137 639213113 407931492 86583051 488104579 23221568 471432649 404069 400643594 96087203 996474478 992158097 22460470 930714022 106651663 686732178 902782228 793643982 544445511 98182081 931699665 854602437 84933008 757857644 965792711 926439687 736339090 446122436 123644897 636725500 745569130 465179348 124787543 633330080 980805994 958840880 609718205 200953118 13860308 963371475 222873300 419144943 517512757 62006127 297485819 279180688 169941495 520226716 111929826 674397297 618326743 219645797 916186187 822151090 874597260 731292839 68284393 803774140 126333878 628084841 26387014 921374399 484977139 17574709 47118200 862589992 114307805 667251807 135449802 605209105 357139846 147679047 781663499 534245573 232544671 401082883 260958994 349326469 233034798 399254429 839072409 654698166 43386741 870737517 682261591 348259537 960355070 913359466 36619230 894635345 288656668 295826736 358269575 146171045 978578064 954533680 834378255 644557913 515443528 59311906 337914747 197114333 584803813 147681146 293632810 283847125 2326280 994706577 660069692 300792550 943978335 878752511 143012933 579585365 549585473 102185937 24129052 926336785 909423223 807278776 770087737 512246611 402799683 93254809 930429180 851653195 317019546 242485576 73876529 788506290 609101373 199796574 466526172 4372540 693974000 370367597 106931217 684167093 852167969 677745889 255348877 361168486 88908664 745276898 68854232 801682280 144266932 575020185 593760560 165720741 192858786 477451460 440398824 43080140 645031014 268190248 192688718 478270258 760140316 492755819 10110674 971198668 953401677 899072675 551352061 105115930 18473114 946147228 61970423 821819115 424967536 61611827 715294134 411367206 983440216 966025665 492523827 29655730 46102637 865522523 140299738 588932302 125664462 631306780 868120443 717696911 456638241 18878029 524927385 75066465 106052883 688597225 23242501 928683567 466745163 4106499 373113500 129846981 494798583 32161237 347060462 174222066 336806292 198110214 513864466 56545748 516169301 60579571 179096988 501611106 128923967 620029558 935898666 862972550 688324915 361164688 48835452 856308201 397353198 98726429 251777722 367392770 65429919 809975485 395926020 101048486 402858074 92863096 381475909 120961525 586874805 152446132 444383638 37011852 97230624 717733208 703717227 392450090 102706105 697476014 10762846 969288719 27912828 915616626 374541825 128346644 55437348 839953508 710906714 402214668 915641364 820806824 60651058 826063111 835245764 647160652 291724783 289249728 886262888 759165975 159720201 539641714 644192613 265507711 824792979 629168765 440813370 42448878 925324694 840625205 813450533 609225114 106051781 688932351 185507568 489683264 148277564 564213807 752125118 479535044 600191422 179459219 663399675 306085953 654920222 289024879 437104120 45202230 841126122 657250408 32964621 905961722 304649256 266542751 146130408 569600646 813226922 608385379 637419934 251369046 240922904 387274340 325063148 225122820 110343098 677804180 755350642 483332980 482718134 14312877 408944371 84279609 841080815 656697800 263079099 345247546 949290561 889194823 93878303 727240384 490107920 26826854 129518869 618399265 412162704 80150278 343002447 185579318 166158483 528391807 171947 999006493 133830406 609743285 597328424 173198570 241667441 385547983 67511524 806328525 576190747 135694487 490432669 28094848 452752054 26985318 398967412 96976549 351784593 163109199 633642635 245745692 578266270 137568814 90681754 741123072 453558422 24554091 817811527 616616684 554636033 109902465 167534857 523617175 137517806 596079692 733873680 440745781 46997 999785575 334118960 204904130 784342969 541297816 136444138 600624062 198830157 463410082 36856522 893239616 937093935 865462788 231956922 402263619 432276114 52307030 526063488 77229489 801544207 582247780 471346561 578447 74858234 786313460 776644032 520588704 563540111 121146844 652037305 283447445 478452567 8876479 344609543 181501465 659196159 299897551 434028072 49251493 953819798 900077168 336784820 198506727 106121629 688225870 47717418 859985048 294809279 283057442 869216506 720221625 67571035 805850146 945456987 881560550 2954680 992913009 917926617 826497732 221452589 421234447 177955192 505283452 172955737 514853105 405417312 89478862 381214261 121158324 70201192 799078326 558231721 116118317 849354094 673910868 452752547 26649354 523171958 71933872 569784986 128555685 298806987 276735809 579276790 138324453 92217086 734332693 493370874 30160116 748840783 471038919 215433127 435422581 398630025 97566696 670961737 319076121 875099432 732184316 762263380 496208034 176363545 509820447 847936246 671002446 259615491 351279065 454501104 22633671 206262227 450696901 400694434 95889705 890406475 770799350 412147447 80653628 663201526 305495137 971221007 937251450 269910181 331485194 601939986 182872140 356516240 149317510 166895762 526333121 197416593 468028329 642094020 262720849 714224309 406918204 879769092 745305081 232263823 401267320 438186293 44658298 331164189 209576169 337930566 196847411 403635951 91367847 759104015 490564952 873619470 729245601 89871156 743131661 895964564 783194180 769906144 511482767 63295911 817757592 705593692 394640213 212219708 439697319 72873221 789833292 906111548 800661772 400859563 95673857 32455391 906395381 673624098 327623147 485346880 18779243 117062657 659410306 706548242 395233020 312055189 249371367 287747787 299468436 761407650 494810105 202620982 455894091 601516314 181740842 82403143 767603285 303262049 269087431 85102514 756355332 797012558 571180995 620088595 222173730 834216815 644167681 830243168 637386194 555413915 110900861 61260893 823918199 921206626 835180552 164580896 531129986 827604418 634651627 541139860 94562864 15977457 957067239 367752461 135299033 753130202 480543451 117997852 655852217 538812735 91948299 574075618 132541465 386699242 111600186 150833554 556941285 130361801 617076986 927751467 844560866 770202889 513072239 534268235 87308383 950595523 893102662 844845125 665292626 160747542 537351639 362560195 141178397 70094905 799504429 534886529 88451457 840419249 655719209 427131929 59140495 34120506 901474700 784074729 539738894 288541810 297242844 20277219 940112230 746806666 468147474 71531635 794327679 903810977 796646108 625486707 234251446 862408701 697834905 248715965 373303184 205215845 452196285 435957081 46352697 49500969 854622650 47040659 863297775 72195599 792164357 181011733 496795900 25397513 923576983 465137780 6427009 318481002 240598015 697425692 380400238 387204379 110848841 180027291 499028071 528180940 80814633 681320037 345800523 455762261 20731391 270086317 330281090 589450385 158135421 817238954 615875433 231619187 403036743 771254581 513864331 807704846 595373137 103840758 693394422 694275170 371366673 433905594 49516745 599434268 177419341 562471160 119926069 93541696 728487544 868471692 719274429 903024397 795002613 694786206 374520365 85878749 755094271 409387216 84030928 64948683 811702572 758113550 488265085 834871930 645926664 523470864 72614134 448245641 31049480 346844528 175506943 638932777 255102069 802762895 586381688 950011264 891304407 924269651 838781592 573787685 131916772 981290787 960242499 89603014 743519446 981110332 960034047 896228792 783759442 154518770 548344087 415371246 75550882 465402870 6088704 388130149 109549981 966900883 930082162 336585656 199484181 488056202 22194626 266761602 337500212 302811131 269609096 523431424 72346726 836719133 651110976 176452896 508972816 318948546 239647435 6408348 981770845 716136923 413294501 353071549 158902834 914502938 817924046 266262203 337704316 942489046 875688982 382841795 118077321 649789971 278563909 809513203 600592565 489889859 25974458 115208573 664980311 508143173 49073891 985715894 971096867 894625847 779845463 870881377 721292112 220453006 422858535 164953435 530249269 157484057 543367198 12135817 967252756 88168213 749058444 766175685 501443422 467007086 3289928 312741669 247602612 707588426 397181784 15107462 960009822 151047454 556362463 713630381 406344859 198675891 463950778 298831359 276506488 46443895 864463387 666702361 309775700 86329521 754757648 70822168 797314325 473427998 2318204 585138389 148407311 844093523 663505107 38885314 885479777 222676953 419379496 997865561 996525411 321094384 235024691 413836407 78038110 274061838 319556455 921681306 836601375 743754033 462988221 28612730 913425820 40309196 879723113 84166978 759972197 377198944 125514026 144635580 573676725 960692648 915177984 432730558 51381652 780956736 531223235 677022191 335402711 60974687 825146539 694247439 370802677 492229187 29627782 266932748 336324228 973344147 941005073 741736252 457125400 439067643 44167867 665133995 307501999 892247576 773547718 663037584 304817368 979106291 955946096 618137208 219407421 41888193 876066156 856213678 685748900 197597725 467164319 609009534 199153081 458455284 16239465 787745725 549719688 658476342 297647150 800755956 580873548 583416605 144397654 944707413 879940686 739266025 451871174 996612366 993742567 675381224 330897274 262765932 345909593 370897596 131663125 495176966 32921545 709435381 399728540 592185753 163888519 931611952 853623372 863110449 699075240 742429582 459729994 20300917 939008967 6251814 983207131 615981889 216169337 642944884 264468869 821722343 625238388 814786377 610823749 672872926 324285984 568932852 127939008 404041934 91151619 801566162 582554619 125546073 631896392 81880075 769458008 523748465 72931747 628572413 240301523 406817665 88457532 418746241 71176469 199583392 462447296 286768674 301635678 596326527 168886013 232918777 399698811 291539873 289662045 876553859 736151750 867093777 713793796 724311539 426894824 221215301 422436105 387887585 109962996 354142512 156294417 359369888 144716670 429532877 55820848 86957653 752722383 146798901 566923526 894473239 779019192 271443818 326326171 688244383 360910707 209568744 445795973 132256355 611972639 569796661 128787344 230188399 406127398 167715014 522449133 992303764 983584832 793656562 564786699 558011350 115521217 422501269 65054131 237151933 395960536 916254255 822261520 726742837 431422977 527715033 79628752 639038278 256305571 170143501 518654122 154834825 547530124 969646377 935521445 323318533 229587578 193093011 476068074 440441230 42916408 123901064 635260259 488467413 23328412 556495692 111718095 985177109 970313236 459345041 14400805 240044036 389818487 217319098 430448720 105321244 689946599 687300777 358050949 920115225 832314139 870396418 720579732 103299089 695901710 490108100 26998726 658178609 293935062 538671070 91868865 820735414 622975605 937655914 866205133 135699345 604359964 366896902 136744460 684816430 354657260 123408147 637192294 713403478 405948938 807044145 593779929 684106180 352329842 62247833 820993209 664473149 306940828 168958168 521484923 834661800 645340940 626907459 235659316 330282779 211613809 725369507 428726972 574925516 133088518 48189402 858811716 499836402 38373228 652260094 283652908 584189061 145629209 951117108 894458103 51000893 849781020 236836986 396369338 40031743 881381899 165815986 528844373 143240502 578658070 424954482 61786377 475479507 4486168 473966195 3044448 293507116 284674307 228126363 410119997 128605612 622323518 429742452 55747604 104982202 690891500 329599396 213350790 119353770 651163115 934770482 859642414 102166143 700557693 251052339 369289664 121544383 644461216 807830773 595608250 938762401 868537899 431663923 54128564 108808676 680870430 205893448 451744973 472603544 1592462 863492110 700208459 780235006 529581470 292159772 288557955 689613392 363942144 602878964 186425144 667280713 310528715 497499256 35847252 637459682 251527786 835142712 646933441 645274353 268741850 761623050 495445254 961244967 918222443 444259915 37156696 793280780 564263802 30115527 911483463 245292780 380670443 529874741 81603631 175115520 511112100 691950593 367513004 928882682 848485106 908378573 804216135 370345000 132521546 883818210 754996232 493897913 31575308 437796310 44808982 107882333 682936928 49516718 854044811 176270483 510408251 124484283 633891891 243520451 382848480 164731145 530644533 714932383 409871284 841214064 657511629 733912412 441145062 177714097 506157987 469895611 976187 424231138 63114124 45212494 867189932 799393961 578652637 337372451 197693476 520324277 67286106 24789922 925178620 925578015 841628102 287695434 300029629 177242571 506494764 430309721 54867729 125673560 631038286 129981642 617786650 114148728 668259175 614907073 213409990 855462582 683748798 99452926 712083357 456402022 19415331 748665739 469943001 93993962 726917405 960256090 913094592 500993328 40566596 650639358 281523696 382304680 119097709 808102904 596041295 566894400 125805739 358594606 145440035 722147816 422047966 861911714 697160962 343131803 184239223 882498095 753473957 754959254 481856029 853685838 680249026 425987671 59986782 6147908 983825855 91053587 739471623 3638915 991057748 82165138 768904752 69774665 800230906 732347058 438487098 568297405 127210036 30765488 910285150 677299933 335996142 381422016 120985195 401255657 95201998 38335631 889037900 161557756 537016702 617963407 218986513 419121963 69024031 764635226 498260987 757180464 486937629 669141396 316124961 515572678 59697009 382785301 118138288 22478985 930320846 371724847 131066639 718183653 418211594 531358434 83465471 183558790 491392425 698272092 382291233 741580326 455706661 576039837 135384912 832056462 640251120 164082911 532320433 342262839 186500665 501515205 41921975 59498202 828566281 715447428 412694977 117375230 658559294 118452040 654729935 20515647 938719702 284957541 305779942 263229698 345110786 801162389 581813193 211759582 441107205 810068081 602270602 885002499 756179914 934065792 858762234 350888020 164733463 646585305 270931260 545012191 98504937 194136047 473089123 190611703 480811057 954888475 901638297 389024576 108636590 768712422 509280867 902079271 792222242 56111092 837978624 489716344 25522509 27331796 916211172 650801298 281901872 2739963 993700026 854271371 682653513 394657253 102610962 588186848 156503760 282605275 307348982 489664196 25441133 510928935 52440929 107142632 683994341 809352637 599494959 146517838 568357653 133482521 610331791 523851242 73514870 415682484 75012550 16322416 954485333 749986866 474165706 483695790 15337764 864135682 701582051 866594084 709572677 558839468 117392025 752907139 480312410 356243871 150376814 192754363 478057649 455761183 20852911 437284881 44951093 135718470 603230768 352668866 161417881 900658115 789390698 542246021 95961183 135947557 602631746 622772552 229033811 424355192 62520986 194605459 471114065 644754889 267172924 692566411 368673640 689861259 364098826 22017198 932926859 37534748 891430935 21023924 936937464 314353019 246027627 867102880 713930645 45281955 866758173 311671426 250552769 465841054 5220149 248390217 374463545 206332061 450205462 57154654 836575032 310702540 251408838 863077981 698889789 145415637 571193896 116656536 660573837 815508880 612410472 649064721 276703471 953525720 899303905 520442577 67331776 882171820 751864675 258272461 356377682 988394867 974829246 839373954 655101955 21043895 936775832 462456923 10458801 992801043 984728908 71351280 795224461 331784402 208393708 337736513 197344078 174962565 511838222 291045821 291250620 709778587 400874557 937902351 866697187 805661940 591595613 554526349 109852163 116164483 662177867 434679852 48053724 740344667 453388181 905426252 798893563 852835754 678320760 237328302 394790776 381894537 119694477 961863170 919532331 560230529 118335262 634619764 247280798 69857661 800160245 716497688 413946319 594585036 166439971 698395079 382377265 987848626 974166411 524640186 74705746 585331847 148990654 811742714 606622247 55380196 840174833 35317392 898385341 866704764 711137718 856807258 687991529 55547873 838760965 364366236 138466202 103184103 696778517 640254105 257780797 174285534 513106480 782853979 537357737 207474322 448077011 777137104 521716782 323355635 229394070 696636185 379576900 401814577 94817774 910903622 809662874 2074187 996376803 347010030 174667980 200342584 460383340 503166196 43614138 23219405 928836461 777059138 521674356 727365808 432191964 710909757 402342314 305079924 265391346 293481996 285063131 995190848 989005516 614667955 212184878 574948191 133306312 100571593 708073915 833856386 643508602 730507361 436573659 166305765 527732444 266875947 336843533 425006553 61225573 912573385 812487011 197953260 466142455 49072808 855970736 903470168 795813777 141495398 583748261 257295692 357951625 111764590 675012137 988533722 974922882 70946926 796589411 354441292 153573466 38896052 885200470 627147316 237016798 755120756 482318082 304431297 266891382 231870666 402718120 956338252 905973656 181934494 494942359 800094944 579430533 927667106 844458954 360062690 143650634 752086992 478673299 217778093 429278544 309571524 254471760 233109772 398887430 240014849 390101263 381577067 120694325 759785913 491631872 6906977 979536566 813440859 609065810 545468744 98933316 147240705 566251434 973963500 944343322 537929859 91149381 749831217 472879769 909285365 806594596 521418713 68363964 507405910 48302427 555012386 110809518 510151959 51340632 177871741 505571689 940517184 873242366 958651150 910203085 400068976 96397392 439800084 43503962 198190608 465251933 612063246 207972887 301357960 272247414 902949928 794706381 300837237 272846287 251151338 368504049 823310869 626821109 562546253 120240159 993872520 986008032 703473474 392381489 17085733 951633202 913564551 816522558 807267349 594708710 491860077 29082271 677345215 337448279 4602423 989113158 113390966 670637101 118319399 655258727 147248315 566123777 706809402 396249026 295871707 281338852 466277411 4472819 640717955 259886945 65040935 811329917 770186368 512745666 908429030 805145801 26057930 921996557 683192115 349677257 604336013 191652828 173519201 513970425 665435113 307809891 784694463 542127437 675598767 331771692 63590517 816597247 111799957 674607025 515385342 59077408 325390947 223474579 281746106 308765109 301461288 271849924 389952070 107452773 29013694 912996831 431959958 52965786 979477003 957010664 490326137 27515260 38529548 887842854 595775537 167759168 547537491 100350275 278208036 313087053 309333510 254972309 765334912 499120489 55477934 839558275 974649540 945711660 964236397 924161256 526541767 78695670 842603072 659931818 976436558 949848201 217814123 428756239 472028457 865665 959025271 911025200 304663596 266469881 300465704 273181461 755734935 485288459 91377867 737694651 689340550 363322096 42088107 875239161 610073677 202532452 435126817 47441695 570636160 129599828 723298361 424065078 408759659 85317238 291316537 290328184 501360429 41573980 218201280 428066740 87574287 749812388 976121712 948568628 53078121 844367273 151088337 555825020 433136179 50210592 826352747 632691166 823090518 626745529 501843972 42056886 563603816 121180022 134385646 608792683 241757624 385331259 586891624 152974564 421056460 67305215 752951517 480407225 130451844 616911185 589943874 160653022 990170014 979045819 912108522 810829272 554327531 108995284 567418984 126094879 313261780 247318287 881918519 750742690 431877953 53430484 354169748 155487047 835779236 650111578 625383904 233755305 122619024 640749333 570482625 129435461 238311281 392458974 66577887 808425603 620672960 224933175 307979156 257830083 738756829 450305539 985369962 970736055 888831380 767793397 206564258 450004407 864381022 703809998 797250739 571793149 548420745 100849652 130528332 616536571 866733263 711910520 373332861 129620362 163849495 533117222 404128039 91015270 215252461 436159332 181830968 495399022 592261800 163961577 986637520 972153661 21893247 933050544 167670654 523213207 82782115 766926374 665563914 309478843 277303046 315148138 928537380 847682702 564405403 123857031 537620434 90796380 919174099 827242645 850280734 674417490 79273810 777025873 662098052 302492975 152685522 553413860 111724107 675116963 632875010 244797165 647796146 274640547 962195442 921228359 295116521 282659866 148513156 562539500 590952746 162339749 537367353 89844796 472263689 942625 299843301 274975605 103823395 693459663 890302834 769965097 557368755 113344624 406351925 88823260 35249853 898875770 24781955 925466222 353231079 158686097 109568960 678226652 776376180 520263081 42750198 873165875 123408967 637050395 749343604 472456440 205906368 451673970 661354737 301816235 416869098 73879044 478648834 9016617 514361235 57803336 686479991 357319101 614599299 211738479 956976469 906226596 186428441 487780200 349677718 166446937 251084425 368963564 190609075 480970716 952964004 898379669 343535662 182597330 67695125 805464711 306760715 262083134 501844282 42224616 919490879 829828558 866796800 712465305 999361342 998499845 809609598 600661344 623979043 230554120 408861099 84866835 385660630 113826028 779132852 526347353 395941280 100856229 976422339 949636279 100703324 705790807 749202080 471137737 171758669 515335210 373515574 129472638 833675969 642725308 855934651 684350250 671776619 319240129 662491950 303440189 750183212 474525943 380738641 121767091 504070147 44488875 424159215 63651339 644278740 266137080 122149203 641738845 725900455 430110571 452120623 28864651 349881715 166102872 808293449 596232033 893495728 776494488 176407713 509531479 788996759 555406221 580683801 139504861 12477883 965532748 62520563 820710243 842252125 658353010 264389114 341707105 15245813 959262139 638456928 254466450 941460548 874735156 214152938 437538501 735391823 444144247 954758598 900582167 31058524 909213751 396202695 100348814 77654591 781532780 85245984 756144021 604403106 191748414 487545931 21667246 714066299 406614764 99715626 710883642 144472487 574224817 80247005 774489952 757692162 487119692 489029090 24079939 92712394 732176676 135566722 605112586 139327430 591608738 264029779 343593704 417729324 72392006 691045827 366529761 912168471 811049260 456222669 20012317 470646645 818768 18322983 947162091 72179235 792250440 2411074 994584788 6737511 980401512 538909856 92061092 490631860 28391981 35964751 896208749 33250978 905013813 508317663 49197706 318829295 240282175 512419748 55184865 387975574 109856291 991726444 981813503 824097699 628089456 215031331 436920404 903521292 796194652 141160699 585927617 356101432 150819299 489606282 24811124 181450683 496201762 215978344 434889017 766781429 503750860 312046767 249676979 149787732 559570009 743265363 460821998 906816672 801274643 147496183 565889281 100626869 707566736 179917529 499451133 491103309 28749336 695191234 375782350 668428486 314304456 93843896 728035307 267633362 335450537 130040912 617534860 412452534 79955447 109236998 679635701 90493242 741601088 102435490 698905168 523871144 73801793 690437590 364478254 654538950 288084072 91655658 736425637 485567742 19130804 44071363 869102525 579311799 138484036 145049133 572866467 794945133 566460587 155250333 546780746 786948741 547778843 345702112 177372492 33901803 902428833 24033387 927538608 298504257 278027941 695670017 376356879 257063097 358038548 582565895 142851162 991037146 980537169 919794873 831352926 576140796 135490120 291242582 290469431 369467852 133032329 807242849 594481882 908762089 805612546 349799032 166398353 124002643 634487319 46766668 864209797 912787355 813498666 18420415 946237443 723417976 424358778 806627479 593037346 781230359 532176817 331404712 209260178 461244907 11443403 769624432 510779796 950506804 892795928 429798848 55474045 604315258 191329342 398647823 97498148 543550358 96969771 732312317 438482631 411289055 81676336 282050652 307595267 207151719 449330211 120482645 648018702 859750384 692264753 650778557 281744072 139230789 591881117 654934455 289090212 448041129 31485957 210688513 443425334 51554905 848492325 884274756 755235568 434059746 49071982 983192997 965295315 57833385 835496529 153867872 549614623 602792026 185971345 216463756 432234666 434041238 49118534 628567581 240110171 289411467 294076441 124647450 633639903 397819369 98662644 59202211 829826523 265735508 339355082 696429370 379304337 246826180 376523793 460857945 12258410 50905893 850276729 911767987 810527265 992439576 984512498 895096175 781544138 286148433 303018216 886033059 758643635 233702633 398149169 494898342 32529442 282049128 307937062 342083678 187647779 419582868 68316198 10627558 969611637 216355039 432826171 16665250 952868072 246111556 379714420 254692119 361726852 554387406 109418163 475736436 5169869 389312931 108024305 975243995 946829410 94649345 722495699 10290641 970818986 733503480 440035178 776356734 519708652 962181761 920735064 910010484 808909467 292888953 285225430 861865977 696587480 114675946 666607870 950680205 893203776 877494997 739658729 447298544 32378972 549539779 102066860 787063541 547961738 247608912 374804822 530163268 82178010 267203509 336150072 201023310 458252926 327470197 218308522 514576297 58075526 442584215 38745153 195881036 469899686 25063819 924162148 694390239 373103430 120095453 649349920 367539037 135618529 832355241 641240072 805405262 590982865 529455389 81371714 563115917 120637612 526048867 77205292 514545234 57907598 927971570 845237892 733997733 441516943 83966156 762471143 912326243 811794586 173240799 514371926 875564864 733830999 79687252 776569843 439109729 43918412 578567316 137862848 758901402 489807871 673552974 327488366 788630462 552652520 975418594 947263137 795994400 568553934 119113417 651666643 74279828 787789614 982491216 964595313 14015971 962984803 687310737 358411871 722370135 422168036 887589120 763949620 21894379 933039619 306008339 263270198 613772450 211446694 472783212 1963268 250639516 370157680 48353071 857931339 802760704 586026372 623691505 229901430 350222255 165747853 33251474 904799545 143164739 578979823 102113913 701524506 659630697 300530997 379006381 123536088 807540518 594806401 13008376 965134833 965609704 926106993 958326893 909355794 464349528 7611979 225607712 415243342 923469724 837894624 95252888 721109117 45381811 866203482 513815577 56537580 966289720 927470450 340184773 191939583 319615766 237769260 818613140 618692396 254671330 361870236 485087564 17802463 989922285 978383017 670558178 317590760 445191306 35183289 998876013 998064287 193331660 475179585 395657483 101092154 47169058 862026737 514109501 57170563 570513993 129563810 72171659 792380620 864980305 705357077 757868881 487189915 802507999 583986199 946182018 885189942 353067245 159032144 861196948 695171893 389309670 108096501 369097288 133537521 103317285 694913922 39908556 882150023 222286725 420150782 366395522 137114728 773711195 516284633 638901787 254955897 655542080 289346351 416128094 74614001 476754268 6231002 887805119 765935841 607760940 197662663 895605826 782479069 722805384 423205995 608629991 198901489 4824662 988130462 259927702 351177253 15501730 958353185 127882895 623502305 711602729 403039083 581916243 141681117 442294972 39125636 757881815 487506500 108827026 680316526 807092124 594144163 405217788 89991472 338614206 194278140 445984851 34381669 486914722 20739421 2989598 992802057 569773322 128462371 508887519 49552171 990633275 980202765 532006809 84887185 103982800 692808150 306254204 262449330 933135531 856908561 210335398 444195441 817746305 616373382 649562497 277767655 256894844 358339592 674957651 330044560 530082671 81821934 841714514 658188929 481992726 13552503 422526875 64718813 583804553 144812379 52407023 845685336 525181190 75852243 342223108 186784930 270641912 328506413 656064809 290883302 922232150 836990115 458433537 16386517 776772610 521005783 139225207 591921889 52126029 846140388 986754925 972313169 399969582 96583553 463470444 9360730 974401397 945141914 444197035 37492366 56574162 837068082 257715785 357200108 772293068 515179443 891422210 771806600 709209022 399677881 561722465 119724231 475104481 4210635 126794334 625659663 346996107 174928157 606843038 195856345 9883685 972194929 597850604 175716660 754436739 481600289 132192901 612166567 721429859 421223057 385995848 112782746 307716406 259172858 895278984 781881317 72384508 791032547 56199245 837644094 428494764 57296092 10254675 971031278 654168760 286380666 723287266 423966346 713240386 405722101 494258876 31631636 408705765 85399228 463840822 8705306 45420378 866070103 602606363 184977608 733672975 440389864 745854193 466000125 912292065 811497782 574949235 133862066 90003107 742187552 637192039 250998219 384706229 115784551 411564648 80972464 237652830 394476000 8867904 973698354 805175619 590535085 966410273 928444016 825961656 632047930 128481687 622398800 939861512 870959515 305071522 265438157 687824963 359960300 558100326 116061025 374589774 128085432 542136914 95395040 818322013 617712178 696263945 378181251 254002714 363842620 646217131 270621862 118533887 653633678 296235764 279994796 893830891 776811727 463968074 8559861 332205484 207969487 485712907 19508131 730142999 435896929 826923579 633578396 302796976 269863713 326033498 220611010 745812708 465749010 556068307 111372764 553162268 107057352 207357966 448675246 468950345 2267882 180050898 499003914 52805708 844797053 785591993 543120295 986264324 971623060 620662071 224403154 871599157 721691717 325326763 223743988 75803019 784293358 751552865 478264804 958122634 909028996 104395314 692028675 603231049 186661280 63353549 817529201 94316162 725053843 430518735 54714030 672284227 319886492 676351218 333464184 722455026 422446128 149052975 561353147 466058147 4571994 440582898 42690662 942781032 876355180 136137330 601520512 701502278 387292859 912725098 813004838 986934360 972540729 796151136 568950172 40117765 880749991 43512069 870506621 585200075 148457285 413051310 78833158 478444332 8553897 768826528 509725984 60214379 826142655 315550493 245238742 841239959 657901257 452567551 27650940 968851423 934152906 102538665 698227913 702629539 389690313 41456572 876333038 117862620 656900138 650330487 280934028 751029631 477312440 50610944 852648096 173129050 514460412 557846792 114492390 994221431 987034686 21636187 934507822 60166124 826200342 402730093 93488330 198791154 463576689 667593182 311758429 656666263 291918642 308273588 257511394 384733007 115482569 701461083 386986856 680522918 343621031 377142516 125646225 356260175 149899516 549948632 102298904 722538042 422555190 681208642 345714325 935383553 861109003 134743156 606991188 913132428 815051839 423669429 63824782 915011983 818559500 48062713 859365144 266058661 338584967 41104235 877872196 785137041 542338913 485747949 19884311 52475418 845369140 882265573 752920307 377602759 124805464 610147327 204057762 427605858 57843273 370803593 131736113 402228988 94385596 44389933 868179951 229086092 407566308 967674272 930726707 72925916 789497223 131347260 615319314 897293346 785027203 959217928 911448152 153758740 551246829 82078131 769050005 837463767 652951709 725399083 429109529 554726872 110123512 417234255 73293472 672779489 323550991 557993108 115437482 658438809 296702201 398482100 97634816 260150360 349785031 385944306 113147611 220939125 422638768 949663588 889358679 711907905 403633261 874452491 731065588 940679114 873404189 942174200 875392304 989537113 977763146 16380638 954198934 763990937 497982839 715307194 411477292 251607801 367788577 144647034 573307374 390672901 105488003 686484149 357361725 996090594 991169033 292264928 288245499 392860063 103070887 162582688 534690040 534499372 87657179 919239248 828861362 97593430 717500550 82349511 768034743 620247801 222601920 708042108 397820306 325088103 224979364 259062788 354580361 957509087 908633113 557314584 112672955 758209412 489014822 730763587 436598418 636711480 249806246 277419093 314363093 325456543 222941384 92698447 732659421 127632492 624205029 543175701 96608971 873590712 728342073 480449477 12741288 228103254 410506878 953724466 899538348 857054934 688750831 108383727 681638530 205692252 452100152 63943665 814997030 997500281 995540322 197388420 468076511 134787240 606863692 59186477 830767336 959726743 912455880 496387783 34872078 522232034 69957475 242696740 384182776 332901586 206473854 684109102 352584841 786346492 546892824 907334708 803883804 80138285 775106703 64435808 813329615 230646950 404916619 257634361 357328489 766847684 504127598 100959507 705290238 226092424 413942931 144229359 575244991 115898449 663337188 927916536 844998941 139646628 589564038 688945272 362357003 258111171 356580097 190808450 480705538 800460071 579642293 102451394 698616954 857200862 688978638 325839157 221340419 488777684 23760575 897014570 784345291 910285988 809330080 72422685 790499946 522138843 69234189 657635169 293735147 199372295 462666282 285530697 304798585 122038947 642684064 522444461 70424701 207359954 448182282 601545717 182018050 223128198 418976423 252154789 366182685 325249721 224468749 844667501 664995838 486095508 19965484 978068752 953298544 581210034 140195982 838559324 654343397 829031715 635891138 950033942 891522130 386935777 111153818 870096768 720490811 655329953 289212837 17980029 948197612 89335396 744007793 992322552 983892998 774463155 517256733 87079713 752137379 526520107 78442341 577684781 137194759 620481103 223733011 501829529 42021527 150025466 558456727 583967896 145285161 364554794 138300810 520069355 66434214 154538735 548007923 141908258 582697144 660110897 301131450 928360176 846122976 232568447 400992389 330799233 210164042 662188835 302861648 781909851 535605424 863984127 700675431 836284188 650843972 673479136 326768225 98361680 714445343 871820892 722388336 281418541 309273354 843918559 663317834 192083491 478714562 859592404 691992297 905720612 800369311 213893326 438088926 435673001 46686937 286291839 302150353 341710546 188695845 268150050 333653624 692504231 368214110 216604533 432209756 815796710 613602579 735878032 445329705 58166651 835111868 89649913 743238865 457677104 17579368 211587897 441507146 764610219 498138796 783822743 538771768 628944541 241292078 66558505 808645208 679928404 341667223 682569852 348327050 273700639 319750341 860200639 693754106 993060199 985229062 976759589 950732473 405716320 89441230 796294132 569611067 784425986 541434298 9178690 973103994 842632845 660073079 625203828 231870077 932884619 856279448 609870324 201305279 496142462 34574646 870551398 720737868 447170853 32522938 891483590 772601984 670879045 318199440 320100887 237058992 915325645 819911893 834673060 645430872 974486443 945233867 460937359 12072680 270113054 330123258 58728200 833388392 96736729 719350406 37980783 890008340 989976919 978748960 94572168 723431016 943120489 877579485 408418264 85620289 655597077 289677046 835920824 650306910 1618594 997711460 737681026 448712203 603761229 188018779 981602290 961091589 402862094 92481556 935625737 861470977 458283872 16472466 472526327 1470878 875353269 733293112 289268473 295315394 598157409 175848210 731812759 437763425 913729286 816901522 881043992 748891633 772752593 515830562 69353121 800841267 671869809 319510019 887857344 766197279 966466082 928547021 628862206 241147762 384448462 116196236 159323974 540090737 979435836 956406089 643068948 264717608 815543237 612481458 94618732 723311285 917217477 825300418 592780132 164528076 221054009 422502730 405256608 89913071 391635336 103843194 850311616 674844226 621152115 226238408 500306392 39335086 786071239 544990135 653093290 285107297 768131974 506559211 782550268 537010708 545024294 98633734 516930017 61150040 837251874 652618280 152923174 553153123 34890027 900000319 418764187 70265871 117504922 658321218 24281871 925763196 930981692 852704019 980944364 959283525 8534593 974672934 985379520 970844778 715622444 413030988 421328539 66851920 16449169 953924138 534165962 86737933 136762107 599980093 7267948 978425024 692178510 367826973 887755085 765034613 651550936 283186853 514947804 58459051 251085673 368726728 110105651 677938939 860409120 694085875 70902253 796803929 329047108 214735658 935973486 863361994 424027426 63742134 341767520 188032697 759845756 491814162 245308289 380198490 692212605 368095295 418228831 72193817 829146577 636571793 518560282 63434720 323847309 228651164 22495112 930256825 767606082 505522542 131211327 615503681 476637905 5843082 185528683 489152490 518842402 64018167 265900065 339127034 409457538 83796709 880732303 747444293 38827186 886299349 776800513 521383072 265690950 339731313 218800967 426037779 459878687 12973178 90966533 740678378 654421315 286935519 976994352 952066731 327977615 217743331 637585225 251938290 128868810 620809259 522203823 69774905 885250843 757320404 531697967 83995512 24886105 925002719 668162794 313482273 413149211 78389929 537704778 91011918 25880943 923122963 590915464 162165205 865667205 706418201 272315200 323545068 769227611 510163836 19171033 944519163 195847557 469943950 725840555 429928246 153313474 551992986 668171433 313774171 866683968 710049902 779512204 527783028 499188135 37901159 777742689 523267224 72041421 794062201 346338615 176144683 321603625 232724647 145751040 570456536 853408014 679575513 855375021 683700137 459623370 13663640 886875138 760949529 632877495 245104137 342862800 186143918 998023024 996928348 969291700 934423801 324786556 225803947 690596819 365668809 588319884 157272791 816882136 615349359 259219075 354566245 878189171 741554523 414379270 77116727 268925098 332239441 109568924 678277855 778285619 524132592 53127400 844058706 591731409 163277506 995554741 989812680 345807424 177272630 249684558 371383497 938800881 869104548 873910529 730071686 542089481 95177012 737424299 447810388 362234860 141572126 439985589 43204839 982606294 964766792 479599582 12023804 426730473 59678898 620791248 225538064 107334846 683932108 432344259 51598790 398416531 98246256 928027236 845575243 991659504 981487160 306775318 261688722 699195749 384197174 676179893 333155742 213221721 439503639 82623550 767466270 478803676 10035118 63974120 814685613 894232235 778619137 465089249 6484707 314100779 246512009 729735430 435415326 321083699 235343989 187967494 485966703 114095138 668326481 355983608 152285991 383668174 116759659 96502713 719802922 809435331 599637033 955081975 901762394 433348985 49640378 143978917 575647630 193575735 475135853 424273796 62883116 72448446 790435900 879269134 743714792 345092725 180402406 651240323 282999070 468399502 2301226 423372785 64052872 40880321 878794471 802596853 584728141 676474497 333613441 984121236 967558555 382412502 119062306 215434431 435169169 799082045 576179108 118938184 651893408 403175503 92058124 441051619 42194137 180306224 497824730 165660144 529246986 125157700 632529490 648003797 274974955 143783649 575991235 375402792 127369451 849294537 673881200 714437407 407962365 348081449 172431319 184176667 490655197 164084086 532070747 955926588 903502137 751631768 478304947 946790121 885885400 686595050 357764857 335659733 201150615 331780820 208532399 708942292 399034881 49084363 855667331 613322067 209836710 819429117 621490434 194594049 471976626 328974129 215622824 781063639 531846232 867483370 715385227 94545049 724009072 77013980 782529648 4181161 989872843 434347963 48180334 617696857 218280136 781549116 533163062 883281356 754597759 25900527 922934804 679249371 340649207 557949354 114703077 573419244 131779722 356999531 148637526 142844056 580819906 985637828 971078053 932858990 855719008 36092239 895769984 14751020 960895924 477308264 6521663 662859777 304444080 351794827 163046637 962891654 921507116 218925056 425428932 142609454 581730033 962172802 920363105 972789128 938868606 170676597 516916390 136174688 601377613 85075125 757104033 881793136 750004204 7237585 978971150 585748920 150652583 879269180 744102345 796839103 570777572 489615416 25250342 182835384 492282725 527949446 80075052 348271200 171476654 368632135 134352033 92735960 731393839 416552435 74040552 55110862 840538516 721016810 420117962 915190527 819294691 915974158 820997252 639361257 256710262 505946052 46439456 789343606 557185404 549368631 101809424 459004438 15185225 439842515 43379487 330961731 209940503 22407128 930994051 876855954 737422468 885598414 757864260 603413905 187600470 495133897 32855809 59774080 827003160 230526008 405190948 338092868 195928317 817059835 615673419 689110219 362733350 716722314 414848347 29674156 912480602 923809017 838161338 779240089 526601510 453510648 25150183 244783738 381082607 485473932 18933910 12203811 967080802 15458438 959012654 750619699 476055850 278316130 312325946 33167979 905120466 455110847 21600123 868215072 717749575 191703568 478948828 376854492 126315544 16218817 955839168 747121308 468820718 564702022 123987029 109510340 679159564 495092925 32805513 66613369 808293461 25040606 924786079 295614878 281527995 668643644 315428810 878815172 743191622 308360325 257313862 986483996 971886703 894626386 780094953 782521652 536555656 736812621 447212546 385624312 114357502 617638392 218025315 691417319 367329666 40236854 880019713 43546257 870056565 812701263 607556008 501069886 40987308 292313657 287693415 72070809 793078545 277089662 316110048 447732619 31635136 403108868 92254617 629973795 243124054 317889266 242076535 675026352 330172833 554920003 110740788 560211878 118083521 974317052 945076521 889326307 768970803 470154198 924684 666848263 309824704 591609834 163221594 127494403 624874947 145552090 570694910 899258306 788236193 115198344 665082032 330688786 211126061 132703311 611501270 408805100 85069504 119621401 649986087 820503274 622625391 39184210 884264325 735588667 445323783 797295054 572069129 76621854 783408446 902911741 794174238 960702607 915826565 285987320 303407372 161075824 537233071 596189881 168557209 413077106 78515353 830166176 637224756 921318947 835420942 295504952 281779906 390836369 105264576 459876381 12999342 398209769 98368909 353056384 160198150 474035229 3087412 606116262 193474205 348989555 168191548 752553533 479877246 115953782 662522463 668076387 313218058 441992244 40670113 827356590 633974388 547495319 100239107 775370208 518039054 117950815 656684317 119490538 650420594 831001575 639157058 296077666 280401557 498483935 37148386 320768553 236211291 873119779 726150977 292428224 287219946 856892712 688213937 42077351 875418490 78538886 778797511 180213568 498779699 53836503 843556851 629273046 242189242 376087916 126807627 403209419 91878026 422682351 64563958 174384459 512501297 39404231 882946910 841058902 656657729 679027650 340266430 941559920 874886738 132027311 612907701 25386940 923757533 939178125 869613637 54525531 842311381 176442503 509316032 831030524 639599285 835406471 648865724 41571242 876202445 39670271 882700176 666899350 310180266 276248872 316780252 90877274 741059577 897608028 785191494 536627386 89334878 791463707 560444332 387459754 110769047 942618916 876129594 78200044 780012636 642291921 263269943 180305884 498013400 34679556 900200614 686782092 357976292 575782225 134955684 763926445 496864954 348853277 169045579 52064833 846885465 636031948 249273969 100697433 706872786 270761525 328265736 866031922 708236613 738765633 450862335 970936332 937161002 969718326 935907413 800609941 580609144 178431585 503350590 611615675 206104198 255523652 360742670 407056744 87769587 318349116 240699314 118458724 654423255 714820173 409670436 813423183 608916443 929615627 850428466 416412119 74461716 409671229 83211650 491756820 28887554 131143245 615837606 816501135 615161798 35535799 897508877 71481138 794774008 340811121 191708719 69045909 801461826 444955584 35565463 582986543 143689054 445070141 35456459 235409148 397683808 427045528 59336630 516684393 60873590 652968286 285021513 133131878 610557330 894208748 777998511 828782982 635505212 894266126 778830800 585294555 148957331 649799707 279201463 511200853 53073579 457899324 17421070 41360131 876390037 642782005 264081825 114803906 665770140 616904186 217098061 310127100 252965715 576988327 136686062 735427251 444313442 157533097 543101174 8772996 974028572 845240592 665469204 963626752 922979059 733942064 441431701 856935492 688548458 133926257 609120524 143295868 578328818 501051149 40706545 657511757 293335305 384016357 116357157 80934730 772566502 83512967 764035015 995328424 989143722 439077841 44021574 564344296 123069066 37198137 892179894 414217389 77227105 910966114 809823072 761775915 495486955 904806513 797361222 219257465 424341092 162086647 535455992 179343918 501299941 102153657 700769228 267484668 335974195 514981955 58616368 681249435 345750150 3904442 990739040 450328407 29659129 213373339 439308684 363147533 139319081 123763106 636263229 489477262 24609148 575061699 134039331 663118482 305100284 268830134 332729570 373528630 129425999 880064557 745705512 287496123 300170189 934854975 860622388 194152528 472917821 571561377 130650150 446596316 33535523 585772160 150787151 821625581 624585327 756200055 486423424 715348194 411593315 110552056 677663521 67105400 806705451 902923023 794298578 748380313 469859818 675535562 331155227 434171473 48616189 277406997 314605403 52338093 846101713 20603593 937829782 188305448 484205323 827527356 634430942 877488454 739398892 700288287 384748643 65378117 810312846 887217024 763028185 16163444 955983997 265146481 340442511 668453799 314536945 575189907 134382788 99373275 712235950 489343008 24540253 159922476 539044171 181547114 496071509 663278569 305800337 300054762 274853882 980717046 958268111 448533539 30331172 47261540 861732813 823388803 627890498 519341745 65223631 899227578 788154916 301529664 271504772 768857705 509838009 104448419 691738321 228842626 409642690 216694318 431552349 17630509 949816512 119161156 651495860 363358431 139027602 783888862 539622808 502092387 42594086 408912043 84549317 629023505 241608749 53987357 843205672 363084786 139474616 300078489 274665120 984437331 969029882 292292651 287840934 322906893 230184167 95116465 721134949 817676039 616281639 815599404 613076682 136993454 598847312 639021556 255924944 877030910 737917517 90988540 739990715 974949462 946229617 759960585 492128851 525008258 75459824 161622996 536686574 312923758 247420385 327353211 218840219 996544966 992865480 27838545 915898835 859988393 693451209 990425862 979462962 10526048 969806406 146337409 568402674 973089046 939547603 897832944 786303603 753765987 481017374 842299920 659321927 102616713 697719035 267621112 335649692 326249485 219615592 940127693 872055862 77272566 781864153 7590174 977777541 583936080 144993456 70445164 797524443 83538001 763836347 94769747 721673118 825370114 631101915 762156947 496073448 628806868 240627712 641884027 262154898 126011650 629198482 272524143 322992286 389101838 108358331 521084107 68216854 897891594 786567428 113056187 671604817 149755818 559694866 144441601 574693159 936744777 865349005 78740984 778337308 913125649 814797706 457985986 17078482 549027829 101120009 393985161 102877652 629946202 242446279 694088781 370698874 564032123 122380965 587359928 153588805 809176276 599363639 2225914 995546650 729691581 435144303 616814031 216556945 58654673 834020702 227598933 411696085 324335621 227181669 28964029 913070097 580248764 138939535 432896802 50622368 861996517 697528223 540883318 94364336 30934647 910038961 499080851 37682910 674114478 328847984 157481650 543568157 770906789 513672723 303660489 268048441 102196727 700075240 478281556 7917671 677639875 337707497 650215889 280129258 303395965 268835005 901253873 791017660 328769475 216246668 6671242 980847638 121867202 643979428 240698112 387665733 265438135 339838779 598837178 176681813 276014316 317093742 110904554 676779524 819443549 621685933 182317267 494346333 887618251 764614735 814941258 611670257 542260426 96273104 219180079 424430935 740273411 452545490 224767608 417659431 639798460 257412527 786343591 546637260 199190196 463189193 26921634 919765591 388350767 109251669 330697325 210909353 129122455 619797235 14266895 962202526 198087521 465890285 934123177 859304563 18809643 945151206 330461198 211400638 615943302 215924039 633764295 245870869 307457259 259683604 348685146 169894084 995691096 990476985 532654676 85673880 122805827 639739270 875294630 732946851 429158854 56376931 652475453 283822416 309209657 255921082 198374904 464297122 184042805 490780676 918693783 826650271 784104558 540101497 772219043 514912186 940135437 872595625 907230453 803589488 211517244 441762029 13063522 964896055 322365241 230718283 809495804 600003600 292168786 288390317 187348209 486066530 702047603 388045520 744330862 463407628 499208465 38041424 232932158 399544949 290800884 292062882 973351575 941140858 481732071 13363869 822933807 626384264 63521612 816944866 750357363 475219384 146173493 568961582 405300588 89761448 246589911 378034276 611204897 205222460 191276039 479888855 595871454 168205713 19364508 943445938 825768972 631329109 88149989 749617913 89092813 745079452 506019754 46808615 813058445 607996986 731848397 437882677 905686831 800310527 575916761 135138951 432009722 52804583 922294886 837554804 359713790 144374733 142692052 581229159 263392092 344004476 654404562 286631314 737427552 448119812 63785618 815860254 71137933 795954702 967732157 931126470 908828252 805757500 499161362 37780545 236406055 397106068 656016328 290491184 937328000 866202889 379580320 122982645 578223394 137502097 942629174 876206680 847406074 670195476 178483264 502258333 855728168 683862115 208066071 447482454 493697003 30888816 96903601 718402942 538431408 91638678 922273440 837381285 38636050 887110912 964081260 923507772 842882208 661748052 176453316 508512423 908695888 805432450 438688109 44459859 40147021 880128621 167491528 524189427 343086277 184598971 23061622 929993647 925254537 840524383 724205098 426389055 242685201 384338360 490849170 28547124 499029389 37578674 484945831 17498644 198852706 463384240 636290108 249407355 55453166 839813516 348494390 170241913 324774997 226205311 23357260 928546941 413043213 79363750 158103214 541398640 298793502 277305708 153642152 551472380 169972462 519699644 68191803 803892338 79925518 775627478 465955305 4909996 465268301 6243256 996736084 994495562 900736299 789569295 879290600 744655014 161370409 537146531 366049805 137350095 292674821 285533446 169536322 520936049 510198094 51689459 633801065 245918164 691142709 367169262 47354199 861274021 645607347 269266995 194644051 470982111 739728875 452092760 279850441 310915571 331273548 209326063 266168236 338003529 557906038 114584154 750402038 475265214 748795753 510995477 243951928 381268128 347333562 173157706 161821594 536345178 792455055 562347084 494831952 32386797 906926363 801470791 890163177 769703990 433321738 49662951 271208920 326476700 130262319 617331780 775672745 518085405 63891742 815187306 546334190 99532610 662381066 303195354 148573235 562457927 557299470 112505299 204642595 453640758 96333445 720300393 714994908 410081270 156303013 544954075 258215573 356400169 612674670 208380548 670897034 318490874 294166247 283453088 162623602 534476363 427192588 58696333 974552864 945319629 342552984 186342250 98926972 713767445 33022323 905315039 178012641 504776244 866514702 708976542 85704735 755328218 101623671 703785035 277253007 315309536 193305333 475267905 219012545 424867089 945746679 882302055 227647232 411586847 231353496 403357114 988894570 976450769 401820450 94735615 258986786 355101856 256860859 358929624 377497408 124958190 148917219 562103111 924528565 839604424 265395817 340082797 959249334 911532328 21457727 935972294 179499076 499950717 996436163 991969009 573281496 131716537 900929524 789964582 611999858 206644145 55253487 840438443 453919274 23944973 790313463 557686920 621073234 225997460 362783415 140106759 662771941 303685630 881001630 748426485 40084484 881088482 202617715 456735348 126702831 626203786 943085335 876947138 921227647 835276597 885864939 758104181 142433887 582030713 980303192 958201597 698109819 381237899 5435542 985524954 61482868 823034747 468374749 2317043 993793171 985987525 336428033 199591593 934146512 859474146 872293341 724362593 84231372 759288428 8214756 974787872 958286281 909068876 122481012 641128882 993701127 985527406 887596266 764083321 231598234 403240718 170928762 516309998 658646352 298122580 916031810 821847165 378335433 123951146 12328536 965751173 794326128 565576364 217239265 430689617 80333657 774328499 274644808 318773956 49410433 854894940 798600006 574540482 579949209 138848340 485380998 18855780 2428674 994484492 298732333 277862024 915399034 820450517 117955045 656594873 566417739 125417380 776222186 518668712 788494736 551855684 220078497 423231635 507863745 48935475 137934225 595538900 115532994 663863249 734100268 441837483 669808807 317346793 515563107 59581629 915982429 821446500 724520483 427097519 821267697 623815835 497106551 35427149 15708249 957917360 339599880 192392427 38710187 886437721 438139403 44746833 687928181 360368431 50700468 850969978 290854012 291926344 483005662 14540806 5435340 985656539 28101549 914063435 211759054 441377175 356484637 149786387 586653127 152011344 783096281 538128478 269912292 331116094 789328957 556398468 46096289 865798370 420169383 67694070 384596831 116102543 532228069 85355100 7608832 977726335 458925608 15605257 40487903 879578977 858676180 690941178 936383242 864304744 954277942 900518723 225627172 414653946 457699129 17560278 606252505 194334751 345247741 179934888 656684618 291994050 359659341 144643638 475526616 4678428 217939880 428445203 350553923 165006902 147916906 565782778 829874401 637043273 78488897 778986005 399701475 96643016 612015946 207648006 94690018 722259935 934849219 860331045 872460966 724784108 419475556 68343515 553771773 107554866 966882505 929068705 640048320 257663128 603564357 187773232 930263733 850782273 15536009 958248685 39091325 884680519 553065382 106857670 901746658 791721258 32243961 906940505 154957516 546979789 825873517 631763170 7727139 976445080 463765111 8945099 870693742 720925314 106848905 684546732 742831742 460170439 80986343 771780762 426557242 59714929 677566388 337653559 752104871 478867224 215312315 435767191 211291803 442264776 794774725 566028304 638346507 254405438 504408663 44792577 575322514 134511438 626311071 235136294 474947002 3331676 125526198 632121958 552495997 106600740 842267585 658654543 926626736 843724220 730460668 436217304 610102507 203254241 454552109 22134715 67883510 804573723 999833111 999144126 445134256 35378294 226491896 413360229 951142793 894624079 288338642 297707207 919491309 830669428 850727505 675397637 647074829 272589076 352030846 162653734 624832452 231221615 541530413 94695811 767489697 505048481 381643505 120536883 814211834 609936960 609257293 199865840 588165445 155895138 17107904 950853379 853394561 679409460 933330320 857641394 589781546 158837008 274598627 318978369 768791828 509455448 243842695 381411589 453790836 24100862 597611501 174902522 41586224 876152494 917857129 826171027 140439981 587941760 717568275 416890242 626585909 235372968 354304839 155367541 538158654 91489991 826428767 633333816 18189059 947380478 513780018 56162746 364900882 137818588 835677083 649982778 469573045 1605962 624357814 230853790 427866136 57414574 165908392 528556860 723915235 425659312 207175657 448949528 873583274 727813866 656731171 292266145 907119894 803208316 334273582 204621106 268911414 332349740 379940951 122890071 973339190 940202469 631414401 244247011 564090609 122691538 883281522 754734947 114771936 666230064 396538752 99583614 453710937 24526496 70311948 798221857 780185544 529467838 137925309 595671619 693296251 369332893 818069132 616932519 454129424 23857337 479564123 11735105 959394598 911772866 893250241 776258691 584587431 146830970 177836056 505773213 216274754 433095181 286226363 302746175 88856746 745683696 585725056 149830833 330196779 212336635 900504339 789254833 567973680 126329681 872829177 725578979 745871687 466176338 36517846 895140081 759451397 490735283 788356361 551421299 612675834 208447953 612689305 208599789 148637662 562315149 980860328 959131710 89185717 744987743 654796163 288590227 346274315 176532567 724583794 427281107 901208782 790858813 223589033 418793831 135297606 606217580 551444568 105505373 924998015 840325300 321673908 231939255 289795404 293339557 761195753 494185031 366037327 137450085 623360617 229470994 498070982 37002586 446606542 33131839 113497192 670299548 531706132 84165964 222385552 419837404 602197805 183783977 752822013 480046096 977551511 952496358 645179233 268574993 338123099 195213686 126378475 627108161 57876830 835407764 328556627 216519039 677895046 339119122 714320211 407426769 827298315 633918354 653600034 285308931 91802133 735692500 293060009 285127614 106429764 687774653 833772407 643222274 701437291 386784245 872239999 723439800 782109350 536074143 625932896 234726611 771952733 514420748 980959453 959495654 145831699 570113284 385766478 113581698 964310057 924911158 208394011 446871098 88420173 746614769 937131806 865549306 818148371 617383082 582105773 142034046 558385961 116509731 876057220 735100246 359105849 144871421 53339550 843897164 129305724 619697243 683895854 351723131 646101439 269887249 693791071 369929726 288359723 297592664 239041807 392012825 527835448 79720779 992369402 984192444 883289454 754871987 607707757 197246690 499916773 38620340 326044243 219770599 337194428 197958133 520084338 66699569 226542594 413194521 227307499 412414884 550432715 102996070 459458915 13937106 467919140 2518581 782785837 537340251 991350189 980740435 490085048 26504859 694375964 372654364 594867966 166740932 383453280 117193420 670942073 318852812 402154702 94498957 128221222 623166925 599454117 178511217 753161505 480748972 800315839 579581988 32444929 906417784 950414613 892176738 504266572 44715239 812285660 607253336 928439204 847388958 308260838 257686322 998533381 997424021 846859128 668756818 613290354 209565189 419155484 68527158 166235185 527855535 38672050 886749393 929620629 850669588 410827177 81740634 838323937 653445563 157563092 542144717 726659234 430709398 173695871 513506144 48684366 856811582 343020724 185343282 202684037 455643373 694566298 374350877 47634124 860900480 392858777 103152648 417677160 72732414 26279439 921550304 170564620 518027318 66931784 806874156 347372505 172930104 963292721 922192734 788676050 552988440 859500282 691591704 357051438 148198225 347722306 172765776 343278085 183894313 83977435 761009231 784467483 541935291 685170096 355722475 61496402 822873493 372325869 130748067 283583129 306371447 118869502 653074240 929328177 849771883 484894658 17407645 513914643 56700002 579796087 138745811 643462098 265030846 336055573 200412518 353749246 157128836 290232614 292700208 204942465 453054330 738306574 449700028 797611643 573251322 61704861 821981281 916322525 823042031 19894846 941573321 526291721 77715575 829496351 636656251 193114363 475860728 130932842 616017002 859166411 691337865 211978430 440306126 427145418 58943283 844223098 663750921 304689042 266171966 905643221 800167121 185209232 490223622 139511986 590818813 72243431 791806156 953162348 898445118 364798329 137927191 501496218 41658450 699267111 384407790 729502716 433803073 700525526 385017406 397992853 98470679 550167214 102364709 537509378 90548137 10019914 971467625 649810078 279261586 766934584 504435907 118819544 653259336 830584682 638126204 272855901 321860003 687508367 359083484 520539121 67693089 415053635 75794030 68114206 804167909 176302016 510067102 526453722 78342737 698066512 380904168 549574521 102135806 821661377 624733668 40132650 880395832 356007723 152147198 469524188 1941662 400107440 96388050 603895960 188183117 710441042 401116719 48113795 859148108 539720384 93311284 683460 998500227 87474214 750639745 525705323 76831936 474661179 3248820 794581126 565739340 738838381 451025592 455924286 20285436 531079734 82752487 418830113 69975249 6266243 982816610 776235841 519506549 229472280 406976435 140805854 586745855 827156056 633890573 464959355 6905836 913984390 817332189 153132075 552440656 29745164 911881327 657312597 292910655 422183178 65364419 347085089 173687093 167418423 525313591 692755128 368816000 778888149 526311143 254516342 363104706 846784037 668514493 938497365 867994103 880970061 748282775 682628186 348727221 415724004 74839705 484230563 16290479 861004655 694893100 146864533 566526519 467802979 2906089 387766723 110102327 14230540 962265494 382772783 118184951 835483630 649307214 536712955 89464803 911204090 810220841 362139762 141928768 686029759 356852394 681845789 346804185 400254569 96282924 123319158 637520366 920599669 833756319 348699328 169396719 600496050 180702603 934831905 859907035 649340468 277536508 143657629 576466336 19377571 943242764 641726675 261485356 205136554 452687097 938194144 867269181 30764622 910500021 615979 998920535 808349836 596445794 6661401 980966200 588169999 156357916 239981830 390136975 811399061 605387608 924192704 838644865 813984931 609766338 463664294 9065836 640816250 260297915 864213760 702784542 641550990 261065640 933882685 858122556 892458945 774364866 450037927 29789951 81831132 769761206 658404198 296000344 866668290 709838239 248792114 373027537 287060503 301198251 113876795 669709954 140646172 587185226 455053688 21672455 679040091 340427610 181283611 496541031 978395176 954164302 79340477 776883443 232640460 400451740 658720919 298502931 1597732 997968279 345343058 179552051 701523561 387455781 776156164 518471668 695523531 376200195 97174590 717987262 139645050 589814456 130901651 616157089 829777203 636736178 975464004 947578840 540151678 93512151 504218481 44517592 830441434 637644923 458137680 16670935 906222513 800701158 646918376 271692229 191303065 479834732 807740867 595522903 594979541 167078853 390117268 107213100 864187146 702605200 993677939 985377784 428813076 56975324 566469422 125636510 68069445 804309804 346725505 175674059 502289370 42815856 735478637 444672189 834266778 644186471 142842005 580938621 203999654 454551190 23598361 928144803 415471078 75195317 670684717 317851007 274831896 318031264 891554512 772980979 509154914 49914063 373490068 129581302 901837335 791973556 39898985 882317370 2071647 996736004 964197134 924041421 255122484 361413062 154562574 547872574 84540461 758290128 708067934 397995407 493005244 29770769 324698600 226808487 113534283 670149589 40710647 879085780 924887221 839920465 197313124 469001860 161918575 535698375 256184806 359754603 316499571 243655775 275189241 317584512 960595738 914222056 110776119 677190056 487895560 22021072 546886151 100208149 87318441 751852133 909061054 805869043 147073008 566492028 287161998 300715277 79045016 778070574 72945786 789353026 720015889 418994196 482130295 13590965 98443957 714302985 623858895 229955527 880438310 746420059 862813234 698130644 976680656 950470155 70387647 797578459 614372420 211576854 610655394 204997900 225108097 417298315 641033841 260744816 335396384 201340269 648939217 276414280 89442118 743707050 611648348 206198124 84993354 757502560 115909887 663037114 170386205 518248283 56709320 836938084 916965397 824782535 266027441 338952399 902112089 792266161 221831464 420982470 837080283 651860123 137564514 595982875 178304748 503533122 390136148 107042127 159781846 539486644 128700905 621892735 142259181 582640780 302995007 269317130 64920102 812039485 926583718 843695096 176554663 507959862 196026206 469732035 88679753 746219908 112015194 674312026 580321101 139056420 996620961 994441245 434817279 47993205 363404211 138867150 816081875 614323975 99625781 711777524 901511310 791126036 796200341 569018136 205753500 452083034 132499414 611656758 565090116 124559637 644742803 266848913 745782374 465309015 979912793 957109383 602843676 186306030 594782072 166596977 210246359 445154701 228086479 410613572 272025363 324439771 686310424 357108943 325954480 220979068 456577536 19054561 329904648 212838469 42184682 874792968 363036485 139517037 334857133 203000705 878474416 742261322 914537426 818204229 445685003 34594411 96178298 720425302 146539087 567432379 678892427 339797682 681157373 345130871 327333938 219252436 236261711 397201854 904490762 797179083 856568403 687675499 29039470 912953819 104146634 692465603 948061859 888284748 570096217 128946128 171590121 515900212 63113098 819033791 748674270 470214636 100032714 710036690 178160865 504019008 105402576 689190489 352612237 161656102 464398886 7422826 62179242 821388290 616894010 216760662 123981332 634808986 724303256 426796202 262837549 345723805 454679565 22079106 11653468 968339328 410286400 82552280 61142409 824495900 710869107 402040028 245678874 380066394 129507374 619052225 818485332 618377628 313298214 246756088 43361184 871472721 815026273 611969565 944485698 879722342 698984022 383802350 757567103 487002540 80564624 773232102 728781778 432378410 364777308 138044209 925478626 841321918 463130612 10235305 324506042 227047440 733250792 439771559 43830404 869504172 661752846 302262074 805907627 591915643 323918125 228254447 723603312 424582648 878384846 742044053 129539749 617935394 33970851 901915627 703385428 391919000 332541208 206681291 868299428 718689885 60687277 825833734 707956187 397770263 60720004 825334951 688329871 361340794 175087029 511402310 122043478 642578258 725293198 428343657 450805606 29459905 613769009 211384525 653897967 285976838 892169137 773229574 221415130 421897989 807781983 595539785 275975014 317119313 521147479 68337673 150639117 558094232 95091705 721317954 676304875 333272134 986937216 972660584 101996227 702346745 792669568 562540054 287473407 300228461 530735257 82598875 568867965 127916255 317500745 242345699 676129431 332842972 123662967 636591107 2241605 995403242 372860539 130227552 880135990 746153172 797320692 572837453 677669076 338383478 225501581 416863476 126139060 628914090 582427923 142185170 15785261 957331528 92857563 731125195 152376605 555046358 805909231 592236329 112214220 673877406 125978926 630128890 893760684 776636521 984864776 969414921 425135801 60792938 977204525 952172325 411437304 81346724 949851435 890077348 905249005 798230392 496629577 35393193 698825380 383298873 606994439 196769901 558811740 116977563 888346177 767157229 116390212 661865152 197314651 468676569 682935249 349575780 845308646 665963864 87520658 750101029 117626790 658003837 814480838 610555424 778719201 525726063 524200808 74513081 82087120 769004507 947008362 886521547 778692778 525075080 290973374 291754680 477166019 6245508 586813413 152317636 34581393 900217482 943332537 878410466 586806132 152261832 886838868 760514140 704017099 392521062 868291139 718150244 473633899 2505236 654519349 287802893 126157210 628119641 56001506 838254026 69131883 801212515 100776437 705660988 268518617 333359033 197667244 466549954 64721540 812618469 65109827 810919325 48319566 858309852 41952296 875537195 424360501 62419241 946121172 884409145 893137421 775817053 479142863 10974972 62993489 819352142 958352097 909877613 589831724 159233515 132090349 612416563 314550383 245902221 634024928 246018703 760836739 493868697 847397159 669894432 189654941 481563484 310475820 251818313 863373806 699625491 124222182 633962754 455605427 21224174 891509269 772756193 390480279 106132854 659525875 300225655 395023104 102241494 452821831 26369969 931069404 853123418 410410130 82081676 310984063 251178337 719852387 418925172 824923745 629372558 537479554 89931708 384774953 114859964