2079 739124309 811387506 189364885 740947710 718244292 804840201 884826442 309610109 448616023 356355836 987760398 265301078 300798155 727478199 399795061 499393619 777356442 765611198 372631842 163109429 390721450 224448105 744825885 652974181 907140130 867309252 86088188 265971344 883697499 35471274 967984103 176369656 140748577 852391088 207353221 664623833 757100845 85315605 356652247 514785763 48502759 565707189 828577447 634938187 81961137 587778767 745070800 957049704 756816447 273752709 415553119 728572221 659679458 686316629 846777205 29599292 455513157 757502573 792978750 448609069 295778435 723761337 974024037 652701191 573938688 759841161 6192732 986374164 501742386 459138133 753783591 392029695 301813947 472730467 628371371 576321647 931303184 866410898 848585647 476692436 854673030 531261938 391028227 847635286 68202508 425352107 992866896 66942592 914535640 574847279 52362893 495852751 82296239 556972351 56976166 802853043 631340980 350917566 42592518 440613469 130889122 24035997 509927704 424673863 988065656 193804316 2078933 116904292 729142485 819530638 343954170 618346671 449871798 580442962 255333815 629788112 303707311 58714797 651613484 217806612 418133589 734049502 832720686 562661369 808942642 258606737 324772294 692741642 633763480 229061548 312701470 227821491 733994688 337234789 44229624 772963945 662090270 913529955 325279225 347559109 229517140 108582298 153699113 434463218 624916164 197490312 638829594 718933222 339239313 123474828 391210080 231255804 635457879 497744125 26199937 146758948 112008383 879347561 478932540 303451826 469804871 253930406 387862857 989118864 386276988 93316666 219714512 4221807 468403631 258778596 752520626 242673754 433610685 404831824 592731757 251542541 509617367 49406277 267156099 248009291 242907636 192756759 498268487 514131322 803499516 170623608 174593174 334518788 645186927 544828148 613044513 613900386 814616343 72934991 623204536 256482465 722726122 281765267 791299118 74858549 477136568 787000151 407109305 398850372 152989757 827006745 270343334 307331556 866762409 240685179 490248197 993313529 5177294 822449564 522978282 980153478 426237705 509494037 692999513 746022677 114671778 30389702 240616375 681131070 792882972 292779967 895281402 806126396 670386287 616233505 253517664 948806429 925301300 316575427 253726310 133280765 641105919 28310317 396259982 236419487 563541574 883834533 771762491 889173776 176173292 610079629 607493230 79201960 509512824 103154394 772187347 284213143 886312128 149074419 386731310 590031550 652005088 541239185 543223677 152321814 986664838 155910147 319155968 550847141 559073969 582702709 942501347 673842489 912633616 229182121 143835568 482510909 949944583 83927323 740508040 328573020 530115839 794644118 868235974 194768454 161107013 78490348 834697250 333171460 366633837 570573205 58938648 94071493 572986519 38096506 185834442 706305883 750194115 250441734 754952494 231952895 104975851 370317984 979815988 384908695 645841005 429456196 290070586 254452458 78938531 228781414 850964755 111608373 459948022 227931558 861792238 260128053 620953419 572367259 168866772 22718233 626066600 28308199 618600742 336613448 472884637 258251369 448147498 504930391 233103172 639822090 588505929 33315909 830813681 102123051 607427441 701327326 739100855 650491383 870667664 296781021 187632716 939802383 376803742 253384227 899213663 87308046 407308978 686031914 654958209 542428378 601284803 502956646 38622619 70600199 231176404 417519733 253698269 168166059 266878162 474772666 134630606 894878080 960058310 582191390 400334801 153444210 967715102 770946710 835951144 538940246 71032912 431336491 798283042 373232822 59205295 49567788 647303945 318554686 973135787 449103456 254989666 316607303 349642651 582697584 509815969 502146555 479237856 119872316 923548582 157254903 768438540 864060726 445733013 998331353 51285118 295623801 746566603 309440797 91634614 725323591 437200519 852413160 519548177 99243482 549814692 82939215 826158250 988106225 671942639 646823520 19847589 776566416 636300475 677776426 412145306 724102857 915209838 264862370 543114420 427365969 790931503 878638979 750970137 204852229 358476395 603711704 328219648 419643719 589899955 924190292 414998750 565713322 818240554 199476198 574420622 14550140 753227740 38023732 103845204 859380833 666424396 791656504 776111933 90319501 970292746 559985097 357441965 70334407 171621307 912230171 143299437 199134330 431508693 435427198 882384451 476394233 714771623 455751271 493249332 498342176 714014231 562641009 557210981 647935872 101265396 379628472 747041878 506963917 661521818 385626833 816051475 925013587 925552225 859034630 835428357 630421800 25958435 201385892 849856682 283354375 620917076 529942602 215078214 114043414 303323230 800004436 37918684 229284067 269886795 94155734 558911944 580181041 629231990 923477228 728671845 286053152 500068638 363165476 256440855 574735309 585486121 28131932 895822358 548037327 462763402 662675038 149468054 258216264 507767097 212637520 356416766 878753057 954485478 973751446 230016240 366939370 518590775 642829787 978898019 670901527 987345198 685133258 647671439 172855209 354684090 273676285 238030876 668559222 199905636 235765691 204154985 542708443 203707633 242597047 799617402 643064948 837870787 3243463 846315156 580299708 97487217 193147054 799856029 633327129 204437889 837065765 372466414 474127255 296164455 37323352 30675481 950821911 748469852 724902641 323992090 559296154 957573249 24895634 476357730 762200564 660999208 288047930 488132762 7500073 30165676 891763178 176117054 294256030 958697149 742447858 522171288 553203705 561937696 185487983 323883685 232831241 659085998 422917405 689977145 444058823 853846218 277004823 876790469 761660428 365708784 133787382 201277 453451358 162999976 397760484 899919804 568903138 718000122 910931785 367234934 120180606 76301462 217262743 294677082 361007598 390927400 664732840 603632811 148722279 685453646 25888924 646471404 527130764 483184780 411061460 677457584 317741282 320742704 544656389 871744867 929534284 449585764 214611195 277566825 276864639 896332258 807449268 412057792 124601174 303572436 985387626 741393202 723546043 386841264 306037910 183482953 165118550 460794010 567092942 973467488 454652620 235381430 633717198 826919562 382231663 309709716 648170085 179284098 43712759 163506221 10948693 140430234 311448130 192716530 865712904 601315360 440378803 721232115 553181294 789734130 622728094 964817078 182111191 180817259 205991884 729014984 873758491 913566666 815106129 269864995 228804404 23827392 509879539 138206474 164643407 841309919 413828811 309147375 895444832 713851439 843821271 516909402 843104658 293118239 914307812 118277801 547026254 363525028 736914260 511441010 472253662 917145369 432120132 537616645 602645335 231599400 725617831 66322575 492123789 904729984 214667195 763892055 211887365 286515851 511218851 155704631 252134997 798115693 842340861 33342795 734397782 653260560 410273315 326189096 846975198 158974265 830054737 78347954 757707569 226299765 684713598 319366691 51606745 911056625 841693658 465772408 991438286 505497818 338869615 155564813 322604430 936893682 783234220 350006371 125143267 378153635 768630281 64656883 11692895 15675660 880619199 688659422 505385679 830852992 705423457 366264108 836040302 492295791 983104441 851515896 192757304 277227514 707009255 106597174 760434105 234981660 458995972 71958153 491918041 884436223 960773308 755944566 563480155 896641296 525266462 418536641 531805342 467918166 942285101 551380633 348888952 662222694 870041758 132248006 505801809 855176314 796839863 844255282 556560682 174315233 27642456 515914996 982909333 649520677 906144701 41786313 860704406 770466376 524193570 156422969 586870743 920450849 291949822 797197443 732251729 630620225 764641761 496543626 511593060 462582218 821687557 338738620 478332692 789751462 525329575 239882080 573824565 509077621 394986529 910272168 486184322 664093639 972044951 767778359 119745810 330156472 454660817 93525232 839082790 191025457 187935482 725094475 308630118 813947751 329692689 856077790 183423450 836977722 271241567 384057769 460627331 89678328 128911110 266924354 618031401 494543150 917073516 571597170 31617900 8718768 657695263 781666053 634421776 648782019 189596841 499759235 530569538 654612538 209697035 999456938 985600689 586030540 231607084 56452588 771735559 733848129 600588868 291238114 285496311 785229375 539417685 471732777 956287097 963693664 746417726 764211917 595958554 975407575 304569455 971868554 132945311 95814995 359531211 152052952 102311433 151407205 57304573 617744831 321931147 519209036 559549978 198946532 617540916 129895377 434371400 673391401 404456496 683201037 876039647 669886691 675406250 735179162 452061015 92968763 183201384 463670852 506283433 53819332 577800548 232100072 680238728 422141233 389854372 884033256 198762441 365809603 489305982 67037356 243012870 109170547 191225023 717637003 700212764 538361688 636246316 339051279 222534789 331609189 611742986 117136609 16139813 94987043 909071766 207881247 345398566 893688311 33226754 194709696 821725676 835407874 775581347 213707951 562511736 46117937 794472209 157026571 662658073 460728631 527647432 437099085 393579327 839107344 644881108 105626187 81114631 277083165 937111884 658030097 816204350 138317648 744459718 31818853 926604399 13031267 332729436 312251446 615505141 800812175 87764700 913501911 735008479 507017024 274993468 723574176 810640854 620949812 580301417 31356992 695564372 396030181 528924868 686250647 719454035 413173002 674094105 250252594 722664613 7324219 824082901 560390119 289892954 833153971 935042206 109733598 122589930 347638633 564284853 729095726 975584830 181791481 14988544 125314953 771120222 860762801 623035824 637590971 122548302 301714376 823579693 898164563 950193352 317975450 894905172 149970354 101736710 122945268 848797329 432541553 327368757 791166458 736606320 859803701 674801427 530897026 133045749 573661264 176894898 685512012 65180591 912728124 742527051 858414651 245130983 281483746 314528790 775008815 794153614 964211296 331229801 781592557 657554363 8061086 307975437 933915819 770540380 836619321 841627385 969081549 390430735 99501514 953486736 208543530 618145482 657834399 483221233 890970373 128208309 59606075 397249384 247480083 480042729 708318396 521533945 103893519 563015114 230870413 547471039 349835434 589780815 618163800 621380908 898170032 954283310 588399183 13507002 174334926 807313792 459538200 414091177 880165723 142089045 940886436 993961736 293860353 873699114 228082167 514322999 11773369 719626287 303253063 353706133 174299098 908163118 474523232 916548336 351176345 725641721 68032220 866405834 50611787 807546313 318250433 502558047 575741128 732219722 373396333 330661619 531716015 96516012 995688961 234791389 803598321 943734902 939192606 426139384 495938462 994695249 774233445 716846138 439785436 853769870 547192582 693647239 874952933 864299700 713394337 687360702 971702576 839687137 456735392 204562023 726404922 608367080 783674381 166723076 405894880 387794941 433468279 342601297 622962415 472728299 343372802 982092248 867252448 392551752 664153421 505249063 390664665 409247871 739877250 852132643 334850829 627316853 529997399 817723858 1000198 454949695 647519219 651221606 678622459 532633523 685897138 990706285 186552270 795157199 921249812 87796140 617429960 659024260 100871260 642349529 343397719 323975466 727146064 863541254 654471286 461631714 799928426 580319444 128104499 767489471 826585167 281119796 842015282 369511454 990574353 40784202 208747504 670679243 969932904 572713828 499612820 3574565 864046529 58275393 116506788 847245578 493396087 822575356 364529523 29167316 873226606 277106711 199230546 467617549 164665082 968984442 141972349 639147008 290423864 780523614 861978261 237832125 919186453 445359405 434153301 986388575 281804437 141057200 251407053 995998142 943687533 951926869 205266091 912117989 162012734 146216607 539845961 568873158 902268526 328882098 83014776 14262392 219162054 506272884 284886847 797216471 976347961 740435667 769874711 755711619 711638742 954062525 884002669 191591466 89778905 121237274 804392506 824301560 272679728 974127720 852896172 529295254 620242152 848054622 960092971 405542138 758865512 848922234 115082137 948868618 17634416 381167733 730128205 232976221 165322126 946821862 69877872 102420050 603277551 996981206 923634479 578945430 742658077 323373332 288515055 150579907 117644371 428999914 686190000 503712582 761517632 456264656 55075655 75422334 183348290 559567095 64059162 451953805 246052878 135916244 143190769 494852580 114573549 194950887 228010028 925454108 213507752 672188366 780259982 396210511 985868959 901416058 273748362 921747198 54612299 625560127 152204421 188746159 782036600 56811522 959156231 19778813 113138771 902525175 859926336 895233774 256332822 355912307 919855914 144308506 715909546 187632866 857054353 335326614 635205074 590125106 543702839 108006270 74252141 942951919 532183800 468648448 465328478 154231479 865398552 466982548 354852197 607956600 125902734 817768472 592363721 874896094 177726563 320207823 521987747 409480056 245201657 71518789 281461877 370713402 616659214 622019020 473759131 701430862 46336550 512781647 511813199 633767110 977100169 441377629 769589302 411981939 669652280 381989992 290203589 791940358 744714854 648310922 204777270 328749000 36934629 594600250 646821987 727246046 442339091 924188544 343522866 149609384 830750913 412673054 272116139 602982099 158369579 257749806 633606459 213645613 219969327 986901669 172131196 364002716 233923207 22056685 979772340 184137433 778643073 553283414 482336386 983029952 106224898 44435628 444426276 820834717 778099608 113650152 420164955 477102040 875134945 184750503 470527981 573375243 723761671 135286934 107255233 59479164 620994373 41118337 907668374 592531635 374698496 679871993 912120603 854361780 246130957 278112816 193152507 422840553 110525336 2050406 199556622 111791862 528495335 895269635 667542572 653401590 497634164 626015798 289363717 206910056 388161038 137499253 706598281 240853970 622538833 52753968 374109446 857457156 126898268 17052129 131841315 111682086 225974729 542289271 264889964 920445830 843030598 908021003 591523552 53075373 736933458 49204929 341725316 777791978 237625132 44923528 975243149 184570732 178751696 453189348 182160681 955466051 727023767 43937503 554864886 189272146 42057587 331369233 103464420 157055449 718163373 189966742 338713897 338458371 7060917 82376552 547463956 596708752 161884784 924361026 329609331 924943308 821958025 974015504 891096618 192903446 551883743 463250938 956308924 293377695 700438540 353507895 89209181 94907136 313857839 898995324 457589291 617334380 494319458 348747777 346969199 41023774 59588416 464615797 422360600 623064993 599735455 2162952 86784736 285686591 659207510 637058944 394573072 933662955 309515555 487991866 300476107 173975481 94541984 995286853 848800955 584462150 975232094 393723427 16616655 994464232 547191557 814735408 356553623 323655616 964387410 198894883 128599629 104398926 872686455 211462464 581842592 199381534 484655448 816304840 493736623 707305715 970200681 371230482 99497149 66598604 822300309 985590191 999491006 338082582 7816500 28581683 607749340 611192977 465068864 12051547 85849825 873350816 804954222 559364043 647990294 751499319 609532102 65075977 518789452 916557859 308904873 133630198 551221023 500752463 614771506 639734575 517222265 123769172 293929128 669643976 417100964 493106113 579968736 222839427 104019277 560760009 176571250 395881295 478927775 28100087 849502261 432546395 871898550 796261741 948557250 20962239 944764177 306412784 588060072 849642325 272974191 370148075 10575836 596670802 942195398 296512129 272546685 57811704 213556099 618539370 422059847 439296391 201579727 401885077 842983958 812279016 898502038 379876044 819318168 346770174 549336313 741058156 350845479 679502738 963414144 90359879 951478370 544118270 888394689 635566526 824165651 696190627 32456908 597946419 957985507 991297247 3828668 567603037 621132487 365451956 62987290 80154238 315229014 407898216 566882286 353275524 887532426 862031051 953930770 59955374 689374687 801438009 488993434 354118300 120722356 118625939 115720630 825092608 511723687 136021817 855012898 439268842 48976752 546611994 612614101 684347621 248655775 348874762 368588621 760528675 840061245 274077229 995738573 613015318 460000658 762198938 321470564 70603686 483624100 277993501 830639939 809389811 120991688 369098809 838696127 354529025 208749043 126349705 465644340 614733193 949434341 534282687 555519529 432586768 819161934 729012936 673684209 345014201 272198759 252389861 257252831 731528419 732538613 196814843 803442540 84998399 77098669 125286127 490872364 498569170 470299067 239995657 965822840 520095185 774408031 110562766 226604061 724598625 148564176 385209646 322404396 998848187 905683167 752447225 46951412 922596881 769568644 648734618 804565633 668970577 424375393 225617686 351478354 936741148 6213030 728777813 570542015 601209081 961672761 338063475 803607028 795457395 914922253 101566614 413471605 824041914 748377593 188061908 617009431 834781227 259347657 353312049 376771292 85116004 205613908 148662450 853186132 360421601 454468091 781117850 216653637 977521138 158891586 634348249 349149663 601605997 961703379 193233037 760691554 509013195 590279111 560992322 96730273 993908934 749345623 317600652 335213260 900124409 104195721 196737804 237166081 85382696 165919818 811975915 740121393 882767908 999614962 664076189 813520408 606841422 315103598 760670688 295662339 146478072 883376399 392705888 449033776 303768473 139495554 540298670 111450962 871456224 469383162 688609921 355799018 699831494 456283731 468439703 789990400 713961020 173624790 787090873 527083005 784935236 162905061 986328070 660548586 795139699 449615654 526117607 213056931 655171030 478295914 654541201 252684766 471854635 771381266 411494441 584133607 176245695 322444099 626848553 732295949 807450113 777878628 12910816 131214836 393459640 832891480 739475007 230158113 541639088 839433385 709545276 617010648 590046476 873253828 326431966 217261943 157612250 652864407 555445841 130237300 76126997 511552994 980542519 46540366 116511070 696469184 589681617 695473534 605330311 714327815 522609081 18050621 105463806 683170493 467259521 509667172 271438619 191289998 185157526 27392804 490003141 255242208 209971616 115007474 727370397 4941790 382825288 221571264 576833847 18177984 931316714 897172879 333214948 861864319 740713931 91063480 204042786 675361321 799738374 201613382 319340448 931702910 635786280 165648119 761786409 660667989 982386828 823534958 850559257 773882758 768021157 462013735 612259720 997958851 551311611 478491047 174593079 788123882 785883876 320263423 907596616 485778668 708669214 302678804 93339200 813217697 594468137 491567631 777625464 40740335 401698562 123978331 172192657 892639516 199656314 95385731 369278496 222538223 51239473 698922218 855474954 484566210 955676544 18097629 660157803 118952996 689051 34501516 196691357 461959903 450940913 173965022 34289814 705157280 799380869 28491026 794657291 234183825 816554273 509548827 568288373 284061774 344277857 578846687 151336580 643148136 684762765 804326491 339937159 279710223 561345230 902337974 584963090 135806288 853106846 101575289 69193718 14069405 962555410 895146518 796466338 467850634 566334482 164170773 475480128 188388763 468585426 37898635 829115350 647908360 855955478 338912981 624927122 394225429 745209710 792725520 497807085 702657377 380823150 952320529 485173495 463747449 418671158 776463482 623602365 957176101 879026283 103875603 394536663 788335530 426353141 777869369 666145585 831024466 407230110 525563559 120977409 601798665 380650503 48236421 582891551 482285599 191077652 897241624 278889968 524389992 523776705 951428506 593307980 80331502 742779358 32458041 803721492 737230846 264405647 878836191 685514238 779224945 629178941 424738484 141205670 43801184 307165238 888475866 925787328 559615519 549947584 879183738 64856160 895500378 397416052 358704180 779057506 393407146 662458451 817064303 798390745 580164196 621543416 408002804 286904466 174101529 143442883 933072337 379048647 946100232 584476380 109457902 180131397 187145578 291185326 717707449 502807360 133253802 357503015 626573555 567025758 649283125 618534796 541285854 453010173 674867914 669355268 799173268 401137648 929550360 844995559 403383237 686903615 422309638 927535528 501291225 830892150 213016929 798496514 346300619 399797324 149764702 688878661 932308853 355287250 553087885 651307940 373502728 281277857 117491249 725637066 947396961 745865164 983990645 334248529 765875430 126857062 463103572 686173545 179227743 106731975 92307770 330336797 551888012 149937219 181937515 310980973 765981359 755834734 697236798 704680962 585678307 161891022 229336963 50906762 231534908 877580033 408686548 162228805 640743958 828119635 687449594 157786309 332574799 954738076 837282842 288665706 382721105 458912254 911083588 56570141 56979440 66085741 638376689 455822232 71341723 585957339 652589308 880066046 963807041 798904022 972799933 915675442 495843027 111694873 51513849 386245910 807744920 170069823 951091530 667019379 806735473 295236431 683840289 376154489 979598806 528311763 439186468 920989666 791073460 97329170 989478559 321301104 168854305 914372415 806686822 501144521 3915012 399611676 173337508 229111254 979395060 525718245 745775228 90262461 950942615 240778779 823020186 740003990 309523185 475448074 382755709 429543052 388953271 881115863 448456386 829852116 311310674 509984954 533302612 641892058 658368569 600819151 902967118 945943243 997846755 466992852 749687857 840525157 981216107 193009630 38064341 410547551 971313548 871119576 380430016 410079183 411146382 963444854 45487083 189537155 183396148 113935454 916366504 539656011 660094650 487843072 640416803 894880621 738595091 246064040 929688791 548111202 849708980 618956378 758956578 624742098 803695458 741631314 194198397 413521116 879939793 530134800 819148677 627169798 277847331 728573607 764944566 770353418 571899323 14271728 66638811 894596332 469929924 505354856 315517661 117006948 383550799 125567163 621102508 923719903 735214771 59645779 914960363 379157924 773626764 388521552 595622686 461678780 435193794 939610410 484084035 800217675 83820942 783719534 222491069 761981032 57978875 574974028 21962807 151743769 516493200 796067873 468402225 486605162 883091786 426289314 297682846 152001143 432792999 127212670 276775255 804654658 528850495 310675807 307553465 646568402 908869361 669590929 291962813 143492934 998389705 693392355 590919601 670256901 290860069 102896588 451182159 633075489 360471973 301479952 496108641 824271382 419497611 33123245 502625171 734294772 434856748 850016078 983391358 824179928 966872665 240972900 655353512 248921344 752385763 297393823 118362527 292444233 526204056 495792307 871859615 43446772 746594496 767069108 4783197 443201924 811410358 816557536 656584596 404445286 699071403 214466111 974372856 720427029 198717692 441866416 38120917 942618572 3876258 708589656 359789201 974153899 984090870 381236772 278551351 722213798 510800809 510395280 769210421 831878697 83346800 407226892 228352823 726743756 340589755 897812947 649462399 735911537 542537167 839098141 411242075 62923603 61234056 298871084 172143634 251014797 525450075 104439637 746602054 766183177 878163567 935045705 82294235 634939927 807899061 423462234 207368659 221853007 545796782 938369329 350748370 861977699 957136180 958823978 776008717 431848382 764366890 920315652 126202046 423762315 522920827 593221387 659902668 701271101 634524383 854887255 617443322 627722867 378149598 206286117 558451471 889813006 651945723 428889461 99981955 571462693 149072612 968930874 607461817 679005420 768020731 971839789 783785491 494330838 628183938 521130498 995206828 794633616 905116651 8466312 64487096 140805190 266624613 233481220 777351421 867545574 55250990 291885807 434716264 919371486 57560899 640598022 956293464 136735018 493663808 457754072 462870840 698154387 299197844 961626252 441126344 596403821 888379252 131733217 913327531 275238453 774370988 778482451 50759048 357233169 307677395 652366410 23393212 931697913 458606872 338477265 43602433 652347380 51075447 47607604 349960989 664891764 218160463 477244493 81294888 722977452 630793708 283236951 329629349 213543993 181989872 426883959 423147561 584354575 338989703 884960800 501646793 885870321 409140722 886066686 968195533 805461602 705352468 530078296 419121445 975278551 807520135 705082806 721965040 215242174 376927744 596430046 108286870 842968147 836270600 285688043 131106298 798546183 746474826 13011863 574758152 165078583 149619446 375651244 44194804 618492160 303780766 323346635 46465200 992608086 9402702 426504113 170708144 985541643 106023412 152467701 550976569 120660408 102253879 607609570 881250044 123499413 395319576 199668352 243494290 170509516 21805367 873551169 115988221 343323056 406532318 26527254 208497258 529983356 847332780 192547436 258766087 160666462 947525134 477536586 425608328 465645332 450571829 742238467 676535746 285196058 106601514 761302149 337723303 355608335 580486090 618516157 46690264 781396646 705088121 565787086 863272862 526893363 121836959 28818500 50856049 65472231 228136279 816223107 721235933 438401966 148998196 928612615 91582615 296252690 461684779 785289507 425582597 565249938 218159820 996655285 556938866 567369045 616962526 217696159 669434832 304894008 923306858 424660595 412688845 28210426 24062700 375463674 178957833 849360812 150045415 368766240 6702515 455146346 744964554 101326405 650663231 854940304 346778496 78433687 643583027 33402159 189376414 662837568 102899030 220358065 684580472 244712871 512198743 850507363 111290814 221553261 694749669 57278753 506397571 924766556 464254007 18408531 330169794 941852229 574646493 142726370 159188206 843510769 174469222 510766842 406342630 44972811 820933693 827662885 582276755 19208362 274869260 79245388 817704404 928065893 684527560 164320861 250414391 932454374 590169877 23635880 175284760 703195446 91239181 178935897 810521868 718311279 874080775 801734674 793507768 791602374 867750040 905004812 895925953 564030774 583599777 863543120 943106541 346454550 525612856 158991539 773314964 142987978 71651502 884810121 35833652 481444695 859773252 656562076 165017226 62341003 591792046 64729752 210782286 344558100 553778761 782129655 760100187 622099874 634723515 279795244 592325006 902494693 184375158 423703200 160380373 405675780 660045274 179815625 993462743 713655315 378930400 214940617 435168722 599439028 818550312 919375718 127246395 965779156 317080568 227687577 552105321 964431572 449895561 917958723 88568570 243721706 378531209 60319187 346782021 942547457 105090433 739247113 895346331 392586084 634754744 4215399 899391603 608703905 709191946 762248438 958341479 130534279 874910329 735780038 6983884 789603324 560031789 908822962 156041327 422326140 795545738 97216904 250734170 832434711 357092965 606452082 922021007 364507019 982514921 449956393 506842369 241956964 37124132 764838510 42845809 307109806 358379296 627662013 888530381 899156610 220505713 562264705 490428065 50468448 649807461 450937992 269704397 321117494 649611769 970511978 39773841 210202982 793741072 110549299 208632227 127166857 362818850 309732047 732860302 136227622 251515029 361065079 679481153 210270919 89318271 103915689 365526853 656777736 781321625 408335045 656020296 767237678 4207893 946362947 535949625 467474687 49146153 664198612 554755474 574286997 623060972 501700167 629862549 929291063 228635087 613939788 991494102 313857504 779616893 642820084 295213242 326046196 459272701 542267333 203304630 852975117 162758743 527120082 659073877 754086366 354131839 778871935 226742865 537396086 156632678 939063039 209078576 891058332 645591231 860619614 325227520 95885053 303855702 704144349 329377976 451046583 824432716 546920964 548111171 572738711 632798120 228203076 263446462 675491585 292773613 136971936 461645490 657358784 419991079 163542550 103781051 691476996 527409124 854998041 176167362 670463280 658449145 501745140 655287863 675008758 31458416 273319554 106822927 13742168 346588855 652393092 304980118 235450197 487541384 269374978 148539797 587125636 934436768 777587843 430781746 245988492 385074999 502949000 990611208 548716912 198526387 402985627 12772957 925707275 389380185 403690728 745031546 716635059 233527326 400913330 425251525 35435011 596829712 157369360 383764706 341874416 602035745 564509134 40605057 211838569 345112998 505557552 805013254 87009852 752659082 656002089 514936591 148878698 893367014 832979250 726158722 17139705 826045857 706176191 516513586 754247781 710931572 410000968 436500352 762752251 524091239 966985845 895885796 13322026 432139540 455881245 839375610 903915436 561233763 671395500 546026133 957778767 664746730 428724210 552875685 492740850 330659890 307792541 4077061 280031920 718905580 799971695 884660598 54552755 376255656 585959624 483821470 742527187 824228712 81149631 139341417 840870027 715859304 28000655 801807137 938461984 144126630 472364571 910318383 928431812 281082080 272189771 658928995 276416895 192503238 224706132 146734744 600507475 511169021 787676067 979577168 749631516 46777825 829156649 388041160 971023450 663679301 165128130 704084366 637751403 745146631 849624183 603893346 230925732 615391973 834331754 920552396 183777294 516715834 163801638 377313248 104201940 952704790 134927825 327772462 956275994 382483454 978296543 651481681 53559351 755231420 290938140 230964198 712805594 181591662 694478994 549406551 839093260 995761455 231445107 481808438 699378936 610077695 934355825 357415467 334749605 903041614 852357091 17555937 195804793 252504160 726184066 137585245 73589840 308399487 951990012 822926620 772286666 776328200 836823499 348401730 500349863 359544590 109012035 38403803 20367827 594834512 25510319 864774939 328178033 66834457 35664943 610328617 999534094 475912347 891659926 520173447 404902037 865508379 732236527 669155527 835681963 285527447 297613612 51638694 644049784 5522687 494943903 295825420 229676115 398160208 978542658 251902131 116450781 353845049 548755418 439363522 458056355 821248441 90015877 787195596 175923732 943463632 996777860 448090228 309994680 716655309 99474610 530264600 10576321 50934421 59542250 66812895 305754407 237192982 856504591 410798621 517012635 450073871 344376387 219213825 645999229 392717544 450566256 134374299 943090965 490625496 358804208 196828576 833464710 188392415 512836265 577356743 11311555 380692448 880057893 399642778 396443604 299110415 596165248 279948427 280068489 402676013 496704596 210180679 893447451 931280415 538661804 760467180 734478436 513324056 593055051 415384117 243172701 376989951 901632813 289204066 891533816 625242171 826190781 196302718 8594892 836942144 673533894 888220894 745273218 652901621 178041805 536574214 25820423 469976560 327110957 981229144 585894810 823438425 905852843 140692247 840471830 934916160 479168534 681845906 667231284 999691852 987206155 898563188 217798896 221875567 948518570 513518824 482930574 540082433 81374963 678640004 513550652 761993760 279496433 421221571 529635165 442110093 779800560 232040317 966694761 653587662 632035225 410048451 790414644 473922392 755114377 145646528 119896616 982133573 439883243 209481021 864112290 652721549 390959003 884171962 865245055 547854948 452473035 363000422 637986090 449089719 254465710 606268594 74051024 757740505 697165737 884129614 371100266 127359614 655533571 887798348 420737495 331085803 891339335 104521412 796828299 304729848 777364525 589284513 667888062 914636327 360645150 909640623 865323713 309340513 663116417 583641816 828447108 436158583 717502137 519342902 807643678 160277256 523659814 19873751 782870082 769112298 932498655 201246226 993976021 665518923 246915536 829875008 351878006 703879919 954608152 459489379 713658630 584594993 124663462 121991705 725886007 269384393 506662917 599780669 543140757 493622241 565902394 906623221 142785584 909338388 554171627 432175675 455330944 831947248 171583557 631052399 110200224 871287985 773365226 490415464 820337055 23397949 215115679 543983344 63889801 737716229 505525929 171211243 626310304 610902583 447552239 674390494 445720296 636383201 545032799 945924068 661524831 656453762 32682234 527379078 219186895 472691223 535206103 488083487 225718017 75673826 792143561 621685632 660577956 762777018 756794714 85847395 138432797 552703221 495807934 130689151 722457929 744177696 745558369 186424034 464552883 980457838 706428373 257675706 869219891 926800920 328402596 25727516 144969062 851782054 978560010 434016774 92534896 454823855 435212410 157795234 864358195 724051453 822413687 721977117 851162109 533715359 833357362 611384385 194662498 120121539 277528034 76843833 318004182 249329392 971834505 688224694 897387320 210838127 101944686 45790245 134995900 566006531 393415605 323128407 536272324 425513844 678741273 367623877 402340173 113791389 3402109 840582603 432357808 704648431 410175217 380954892 856335434 647605046 392824040 77066644 460948301 965235887 919513849 790289707 637863619 144381008 277750760 938149267 253582635 307909190 566944034 782187337 354060290 879679266 656583739 857084748 538140580 868192937 397418894 779171695 861492075 345305211 107032721 133854542 39125656 905163908 687081926 695041526 402869262 819127136 83409281 878308078 255888398 148227445 191852573 436425316 318891670 207527797 970986704 849750315 458267428 280814772 650714835 989983813 877336984 661115256 602423216 986050214 426482178 356772807 655736149 20364193 546328798 803300541 693310445 759887695 233674884 135931319 830923877 243513801 551317856 125451562 307645346 811807552 62005211 558992981 988785087 500427282 719090293 796310219 757569633 825969082 263758101 640017110 814232122 88001516 569020585 533300332 459447715 967415299 130706239 786294114 318226556 343008221 347139795 961480851 49413942 278235924 963845245 153645340 964750619 45925557 110667100 957450109 339288131 845839980 563407463 607766358 486818647 615865334 564923286 47664319 861053826 336799936 815371246 127255841 410101382 375003954 523105810 342242751 188560466 35156461 456047805 736779248 762453519 518953855 253408230 143408290 245802622 580769868 996792132 675109047 225994214 51116707 962532002 751232527 248602474 187182952 712989808 673585896 44882385 516953902 673729271 288294807 416433812 924821982 513677893 656783405 510617520 595111076 379901482 766365997 17947638 978947237 807719409 637799655 412468253 539132507 284819255 335688600 895427461 486649390 515987039 66766005 983350935 504674631 456016105 367292877 711311253 901618086 90032217 728194317 432876370 348863737 444823061 92096453 9236616 150286159 765705214 235634116 762999963 211687096 254281964 333633098 970054981 315782618 800074568 988032991 626225645 400066643 146209278 69994883 407621284 314938408 147630708 559594562 199598179 529895689 246359516 764290696 334575785 126339039 514002331 320955825 773704754 103470573 685934433 804262373 219985722 269505493 53737623 386525172 233404908 962178164 73923310 382587826 795245357 730448569 68573741 589928413 739440870 869768538 723363753 262779980 331144541 248887550 652670668 400370548 506715502 812486543 982320128 681695310 380840437 647784070 934651851 444220599 289341213 609010167 382880188 984130085 501569966 60014953 659276324 145119678 203661675 426680302 980768894 493750411 964936935 297227908 636603610 653886930 449710870 551541721 532228534 127267431 630614119 896981400 649241816 499430836 903138846 549638835 648519522 169532525 985057771 662033579 689444581 693424898 538806876 885363645 148002423 512264111 690243910 147777315 478912618 472522390 8364454 305891340 195196290 195856377 759262971 319595021 835798745 686851304 848847468 833338119 592168846 532799515 842143924 533331401 484258418 103657180 535892650 192119588 896096825 811262436 953552553 474495042 928351633 388032896 635139613 794458735 534476109 495856405 72909764 153634408 830119829 17518803 11059646 342464906 817074755 44918758 93634841 742322493 559712208 134093283 828040580 697105800 771374980 675484291 512053980 974340810 280674913 937827653 347267702 94460672 682252308 315885672 598585777 403301638 107879604 965659127 710334081 788191210 260585646 528388663 818175929 430357421 89150733 921352892 121726339 84013884 205055905 951856920 633000635 111912916 896406463 3359545 193634941 134393365 315712801 984465241 623104054 16333349 55766920 79150940 933653557 333818132 602680823 865709676 909216659 743264945 462920514 213539535 388878322 944629369 825844648 989195212 676375198 233053192 407566244 511743010 583830985 77278030 158872673 83442336 279478653 738762991 265110567 589628199 166836921 322354165 393186984 647904701 513964015 122533052 250537276 166256107 591985112 845208268 730440814 464397181 653069857 984681542 10410949 678708318 962438079 458226581 574469250 889893010 897218134 233105283 486551993 80606513 527393043 45421899 945077792 666692426 876456541 776878950 30558407 298452804 311721588 163116449 981786974 448636779 297846696 79599750 175145013 277414820 765844405 628514667 144491313 216221557 800981492 724320094 310792951 645332349 546147356 393287839 495004811 187036086 530607190 40158696 884281138 550037824 619442014 201557849 564282085 391214481 339971804 138540435 950496278 936249862 864975746 12631420 950893156 292254309 812319343 957036104 48984125 189008054 768972003 446695981 274272044 798519810 557830237 470123562 170095319 882717266 102481395 462461048 899261338 923408331 907584539 764938834 857599605 114338909 821819268 897596945 261903767 219368574 282370018 617136651 108159589 688843037 981619639 581715857 270594408 436345252 62593126 766380682 422984906 548398308 374297988 265642646 50960935 19526895 308858370 381863308 978674566 946896035 538171110 703666802 861401219 864556872 671865394 170927527 498529297 954354211 69378988 732953429 25932113 318661755 694655654 594396833 642931251 104932055 979768011 211487624 62852022 534171804 339498248 263807818 329988153 423915301 192838764 194849268 68345658 360774188 701454709 131678356 309609424 571892246 927046244 42660693 779481269 979105264 138268446 94907273 645433752 630945061 956554800 358325588 226728270 663596935 657481962 401775129 151660253 113038466 140926385 293798803 804501670 983261573 435820152 704090510 461717091 679345405 37290519 916832859 377187584 31130316 687630973 719952968 62122937 229656556 587564460 286227323 966837995 313568303 741850697 795356686 87233528 90353209 759685638 832761853 755377940 651333195 433390815 632164555 208772619 958582938 279237581 556390617 733623843 601921985 374198376 923605555 522392185 704671728 884763342 156313366 376240513 752119221 627355638 753862422 505025508 972487853 110389485 160505969 83993832 170711707 201471684 198172512 131667758 570910369 369189687 815134921 207340163 894199160 729939735 588630809 209055736 95856335 895889915 619733606 509321361 923198403 317496369 901780002 475616661 847238023 273149313 91082168 418480562 304953642 249427682 296574620 905265735 514863369 3986593 250167431 486554962 753072041 561972536 351328429 539897740 682426424 30469110 766369383 603473570 168625517 345186432 73835304 553101346 799297932 184511753 615168575 284521681 716630498 240529017 200131131 855671109 643842549 367635896 612992440 156041937 65400525 315370447 417122225 641525171 303649696 567092730 70405147 12654645 543453704 706248690 65306465 451150637 948551831 954109726 851524931 928442790 784208611 507158605 774167412 268072911 661228006 569727164 508771541 544907639 903255623 304924886 760408708 875444391 984806468 788425103 277410221 134980222 227089654 967876010 714728344 245749452 537549409 864809707 818827733 42281005 397997205 801878377 796603604 1849716 865354882 332465373 413580718 941861687 543412778 809693594 38534550 224420576 553446287 772928769 30835375 631050955 103055399 234950294 405997265 102190418 645626481 602547734 646538483 187576327 433163629 355661573 984953993 306354116 155674612 630074077 130817209 192760982 496334784 958387006 403116947 926146722 585764930 684570963 705916127 886138458 314262352 763756207 559842887 392910202 581829749 111767942 215476216 626270632 570289647 5635855 210762639 861215934 985533472 832170547 909267679 597146063 179165328 296904273 883397196 992357802 388244570 460832390 766005151 517860977 968943597 692423155 971549661 505799278 532708126 428379344 21226676 514783143 345782015 285525812 630206176 796190266 183877240 795574999 472182353 616779228 880397151 718252614 131351134 855591068 926057984 948429607 193541435 623580872 687516143 540237510 746541682 331547911 82341605 966379148 127650869 872172335 53543134 930320996 678543069 153465826 164991342 790051867 246000702 436006145 822896611 531222348 891335330 24701277 686027877 826754278 601897536 691159864 20913117 878905601 891396456 979942987 268248219 551201814 758793186 936743352 18929520 755738409 56434654 841450792 594890269 67356037 155074524 187651239 633033830 347908620 12278918 912791995 144172500 493551429 479109654 902058652 54261941 577072131 86963119 187522595 619942972 153912773 447824394 800048477 298723346 138287174 984493660 493634355 203744176 249877830 84658837 545559033 847777042 614224153 347645966 251071685 333255872 7591961 414411080 153075895 160377685 601377774 147870892 502651602 361645860 633356372 729752401 338537119 956139032 263889766 105405553 108765946 516262757 970314507 521644433 807593443 853684975 980513350 497604811 689939269 942077060 524330754 543606322 706224496 253807781 309614885 68215748 604065045 172089063 712935007 78181426 769991139 392429778 157330105 637578928 537894675 528804425 346213044 777625495 188183965 798809468 660641745 880490099 330403195 51379550 14817074 139491709 479054186 712436026 123131135 913271929 514044364 143207932 734441802 190232521 647334387 719705849 267483338 352566529 760763701 353364305 325311885 944135418 780778384 363589744 15099372 65445417 286993719 3523159 678652951 501804170 547965978 875143734 442739821 496643705 999657323 40317832 372525698 854575788 307280314 962910952 193946414 386049790 450082290 418423267 842037194 421650571 962960847 399219523 942157821 81907426 386439456 118132065 220658628 619461262 691360928 332253515 929181070 390320936 61992932 94879426 299952085 560509323 286875494 901814929 994246194 23885586 279268656 519363856 876260529 428550205 3119458 451586373 514626999 328703756 219001033 700670977 914481509 173584438 908553309 25086532 457149995 623928049 288476190 747261188 598378544 495729311 80547210 178450271 998256315 859844999 769080996 8093453 945841951 643254524 32660685 321401374 385501396 228610859 823940865 418677792 650549389 882452230 843772445 758531121 631451585 462771686 161727517 729096322 239121547 456905011 525990880 724264527 280247521 57414748 711165897 26723271 2427611 8633416 934480116 999185714 726114195 297133323 444612738 997376485 668201555 922000258 760704916 342951437 201195345 257017586 948682181 965104916 276690776 422274100 192763375 793477979 748898191 606088311 495171733 24589827 938297560 105725229 752593036 662203360 54142856 662722776 842419127 357559604 136216402 689399319 545617056 934820068 423769557 697445573 987727147 432841205 822336483 163714008 750117768 953660161 129598122 985352186 502195506 13532076 901099108 851082481 11518949 16980208 229690541 787774331 941856273 61315793 857897763 811895693 322950647 768757105 307763385 676141730 636419564 132366264 422612603 61592568 963642581 318946827 949677476 886610947 824878551 981466163 540276854 707802761 502288674 867205011 490490314 964715834 482494170 780446547 713388136 263429280 457396554 809349473 343784302 29766557 318589453 980437577 395533871 774365225 822187467 546843692 896740915 423096662 938909226 514171366 648123454 912162243 371485881 965268108 332796590 76181254 85141939 548747066 820011828 99260100 871932261 369921245 652771208 399323767 526725408 885440434 936159482 549705131 752550639 100549253 365701552 711049562 629181002 915268570 305918244 246270670 59845335 74041663 926544574 94290307 886632010 969181791 994462097 941996705 720823597 398576360 294260096 47781431 678806619 906876662 329586882 146205789 882759297 6669640 426852530 737254790 923036887 948422338 130497614 367838716 963777516 202506117 415661711 624686464 833112374 793205401 360659435 287807046 910702615 966739008 557719333 63101156 240994853 865659211 808359357 410052174 959775721 959984958 842456214 332389961 644289660 434364842 683854982 651046104 758278758 536015088 169528052 798159474 622168106 391975476 511872357 264811781 128139272 748082076 356345904 965313405 787968080 509783826 212433805 534200628 973387510 359025275 243656832 397338460 140408062 853927426 748590330 532279198 304138366 364314484 407996739 976079009 111307045 883211516 365301841 505081177 884875787 73818583 252620986 939103202 945954168 728600479 669797524 862198090 814343033 669847496 563560890 410840530 50347032 571400843 209758590 252085134 788293140 835165678 272028076 877197246 722447686 818108378 977639571 840717488 636842468 196139264 97832775 869623221 131007964 732756681 993495634 523969087 571986430 262866628 119476801 7726070 171841506 674693500 606029834 966800959 578865680 76708262 204828015 29553606 53234830 628879172 432453526 487762842 114656337 159333795 876319045 22847498 287749560 138758739 626518141 286035362 288712520 421015728 241135660 524710085 135562542 46389231 323318585 991449842 692345891 24464469 916535561 575872672 715645622 84431314 91459010 722856201 750826759 173061154 99387065 30225563 753862343 143399908 495388175 110831938 481218040 580600057 986305398 564334764 832898085 89763918 851626117 260478551 385151910 570361837 144503716 754278469 462048190 763459512 217074868 624422006 805037326 737782215 116337332 573797957 633066978 274135593 344655388 936787747 397368902 587127007 780670058 548341010 874719069 333434242 582559832 850024938 599182428 320606211 445625745 832538543 391197099 143461722 678930618 885545520 207865114 916604225 81983264 400616983 636361473 30348510 619284125 380746295 705786303 447839523 824081762 299327496 642933747 237050546 48634552 16464692 291442003 444498332 192057400 528886599 191813825 787661562 544538286 214600089 614914409 881825779 821086724 617081074 118088059 544634119 529613574 456580806 193147028 943618906 387364024 365945821 720383275 429095488 503438197 295393150 999770600 930545390 817247765 956465971 279320560 491314724 585859565 322229286 550761677 973804035 881960478 872730726 258284479 257102483 51597127 278382512 889595934 250991296 403341501 750892030 886244934 871042717 306218898 220823759 562688785 14285609 462482443 194718849 531998708 263289194 813085015 891628660 358779210 282284384 243430885 820493513 138839889 780950699 337644094 933641678 652855947 524425216 606582221 943258787 518744614 478412064 717216641 333261343 365179115 357137973 474535709 403033960 26824300 342816790 296981063 264295998 108284395 934175944 811803893 626486970 958967786 200768589 598311080 637033817 525056105 13712705 817121351 798762883 859493159 430801848 393872692 103006200 344140224 791026721 801380682 621176310 52824249 47764235 646124260 895655235 606336808 958167901 24857206 91181303 977795457 681350928 884739346 747787002 459055455 547265029 57509924 409988837 785419330 227417529 504466173 79591108 395018211 182271489 6288767 327770842 528349962 997767740 191973945 552519781 581062908 516907387 447756413 610221029 896297940 634953540 148150410 48211684 276242507 968476761 681997807 607005058 841111543 985656359 572684518 526993950 299586106 897414374 42495336 548200234 724528206 40775153 589548957 579082763 775749554 229834065 94757796 74873573 634058941 515963056 128614083 444661689 392463058 655013738 970452181 227400487 490947794 286783997 573815497 570418456 442547571 923623028 19199556 151724578 792445928 394464166 742263888 359207762 940155309 611937185 99736907 254792302 246548151 573704271 604962551 663248715 196193261 193332369 527573615 626667715 6346027 715227691 719355428 577881483 516602349 19793549 211096104 541753145 242941020 609830179 497052012 44876866 405487021 856297857 800864196 115746970 150357025 860960890 22923579 326921261 585378185 233100607 538089744 921153490 351058178 991333275 595557358 852240345 82873070 139120222 68406176 958455633 706715907 960019693 592942233 934714863 116333171 168336854 912340966 587192153 21917420 942521380 899386195 513867997 732795898 449181113 406076073 206095838 321216026 998653914 466516853 164648523 898463561 374458676 392521771 501227375 333152698 832752438 557564903 720871696 941734660 730714779 533083807 430381473 608768367 459752518 387451440 372343196 223847478 411393511 321764362 790432756 484554094 594335427 457935312 638634898 465038954 136846909 233509874 662906142 189854161 384817618 196102225 700219190 423280840 978123887 1866151 807566643 802094360 510854524 46331043 56399538 132975546 469229104 412652529 857308154 248185467 563080028 738189310 245322393 227199276 202290736 540229779 203673094 938081593 460938686 801305623 829626656 256124194 297641246 726361326 233026559 94391437 73290146 272737356 251565915 619098597 142216608 439459899 366464624 93561875 535652882 478235561 261454536 298911457 770956674 369444366 490330005 373257853 493797341 246122108 423922608 566627920 736224257 185579933 94293543 603309749 906311999 943932523 925014118 791389556 96078532 816256748 489469239 269042900 404138377 4487206 865429076 155500177 344488709 639919552 933071309 650359845 972097086 594546628 49584869 692794622 639571317 118893248 465694891 153832425 398949985 762626967 623422325 226819776 859621131 773528015 184580739 319289139 83352179 353242043 992076476 260817587 144128020 363687151 538379840 417797657 160716732 446657906 495565392 967337208 725219303 331333179 921662880 435859284 185230210 183182883 322995550 708681255 909184084 336390529 412439428 629290716 24332044 607585903 894304809 915707922 393184011 689540726 913225101 90575877 848206940 682821189 242344783 196025433 738133036 956616154 722446679 899503506 799433193 654857877 240053991 446264819 495523746 323318716 411494652 962223778 859045865 388588894 328149953 625544647 526636524 134705215 507137149 136457630 343634973 333145892 668736416 274682623 971017701 516565634 381759307 714600803 189923880 576920339 941044494 684869350 359859650 907823688 969469740 444804238 473063165 223799175 572967374 48315780 575772947 930822225 818580291 268184241 786664183 913554331 287078192 531509441 804276395 998086492 636362043 441458646 352547798 596959603 421612654 892744281 998513579 342364381 139716162 252563036 389713098 242304197 72981761 759551129 929858652 436659979 376575400 74155122 319669434 374006031 162692769 931462565 115695253 519683867 970373961 148213248 864542286 624717422 129144399 867249353 708717272 896225838 536722810 54663089 332043726 33411657 133409584 290040610 202215001 159954147 542406156 530000299 798735347 107946187 107973207 959402696 387515579 179923226 471459009 841351252 692796454 608484986 707809156 763048921 776533886 177431528 255067157 481007367 355683753 775253536 551804811 140097616 809742708 374565143 812672517 617714618 337140548 41828779 697441326 534988690 692238917 807192882 717487495 254972263 717166343 288144050 20104780 70549478 951510933 630725778 963506272 569318192 397432972 292633846 172442811 682613804 174728884 205032949 181871238 414562261 349521939 733812910 352037282 226345417 552705057 740248359 72486828 566623354 43494330 711437307 431296739 962678014 165136927 424989419 619042442 733981202 492138431 886595455 85865702 333944434 776551177 724040372 519773442 369441598 663057697 698904692 284121161 516342368 722770323 73227055 301727061 371437385 117685576 109003336 401551727 4488002 465926049 76409983 553233852 697952635 58894604 81462580 939969202 951059584 313598639 477242018 728300218 360800685 416336625 871746741 53684687 577517267 563273381 678551940 66620812 882554002 862171186 499198638 408903796 8349914 917598493 201499235 883313265 979103083 43651256 808176789 328889033 321138930 170839781 51897570 2624802 189012696 110421250 955672535 858881302 57489725 658806628 250431509 51649564 601396050 183001650 868138654 184299211 15503261 969340555 557307227 180536581 568201842 639144804 164137474 139973278 554855481 294240459 560634979 159831681 340831706 557193964 816756453 449551679 961263389 206019062 368707952 260731800 725066821 87487155 447467763 965322630 81561567 674005985 874261962 225042649 967238355 645528826 592905694 871511663 816083933 971368782 77051318 608543094 880137033 996060547 367612337 943313549 193450196 225563995 944647870 194126006 966413519 649726775 73097941 21265216 975298911 236492550 224097161 488698509 520028922 274980834 107074108 713026410 184590223 782090717 184011745 187896136 269781820 760754215 79913811 810630243 265973606 964443124 184588269 814122915 599404237 190762310 668349707 398296358 919757879 920645051 421285208 498502506 528968244 982371393 862490924 949877695 741838983 448378147 870562614 237870356 698269066 839133243 954656776 702284417 414137242 778433395 677888042 331813343 142977418 520603499 506378036 147536621 727109495 811026893 130782355 61097871 501335371 599109174 896839278 350231571 995217913 916009702 789376239 802762223 93388992 870337990 386122967 42044092 552945542 292314454 169535134 54970309 504863878 408707114 803522578 81553196 797180389 658865902 738255735 364499479 606488722 777172286 927817607 738740870 506802746 963060323 210020371 757437941 980586218 709770405 831258533 138157655 739221588 936816609 665543129 755457743 848477935 504171612 387326375 670644221 505868626 627169786 996239474 810118240 363710100 781556004 922059383 233494230 637598251 773558929 59935501 300562986 583817998 768435766 762653743 127062187 744238237 779771248 887310096 260301797 162731861 108631009 65142175 440803623 803055895 580187980 502896939 645848289 411396259 252836303 289080278 911437533 191006730 905706782 797911460 947019034 650992651 29589445 164933060 816484869 241792784 546664651 533194869 693746880 41445824 492194296 161325818 802316448 998399400 853758491 864797351 434692589 899731173 856675263 168256927 8848060 665399414 339969228 85533593 713659943 561417841 992056114 805155123 566417624 394707035 107650232 549498438 469920501 253333336 655288145 626626292 179170826 901973764 687124125 249793474 749479210 415052481 768287052 581270961 888462218 273350717 2873016 915137532 642905260 893640430 100724841 776230000 763338259 837198794 722870057 244007200 814898338 483792040 249882223 609012584 28754554 856021925 792751872 399843890 661348449 617932313 26767400 392137252 640714861 326456927 968251304 532287817 971619075 473202510 274222794 930935014 214987232 886821993 3822638 628271440 894272859 319224861 74179179 755522650 706833834 173754088 470892869 925938081 691594006 313642379 119655789 317072236 221038205 35975415 897894790 428112919 219623286 710704204 807705724 798314066 290129858 85164048 746610630 897826812 450684042 738423235 199905381 731840376 890034522 152426509 527072329 133590756 753482874 894287916 604479994 168266379 465503387 627089912 213550780 534072746 816435519 142373915 450754981 472046338 655288432 115730709 865955576 632992613 741344160 892340984 190720631 980791908 978377665 990237419 603665978 339142530 970140126 268084177 794821950 348718958 232632865 858865932 518965053 86948478 542437020 522672940 86011916 953935090 684349546 382497853 822724322 795985370 20623026 936055424 696486482 21315649 366414417 612077689 637187653 497202205 393550320 298213831 772817923 469898397 826632591 36997410 150917212 481444224 377137540 777877483 822876775 280998558 410338920 607964121 349704888 683244828 976377187 201241291 666417895 156110379 564699892 677557226 484955759 292090200 138216227 925480379 6561331 829806693 998355471 506516039 95590786 710628758 160404220 885601695 294335667 310786772 362217730 86285643 578669369 328274323 148579317 177804580 596281979 633596751 860026173 969521195 269881283 993998451 415313502 47795725 785612337 373594067 554346174 642149559 279011080 689681759 22658097 114567773 740646811 2960713 802832655 400392245 895435480 226919123 564156702 941120218 979002691 91525544 772704341 305057035 525576164 869722059 737920126 505858473 464669530 889051635 168313755 547270582 692546451 982042303 325058058 983647475 105174524 570942766 158458893 654417948 331661619 656899113 372099930 143846240 322273710 373570844 349819989 500191822 658907995 283482501 836486005 24617604 949063736 344133388 350309693 400995057 890814272 173246152 554284038 926115316 874008361 479092124 695881582 960836059 203643078 75673395 215459142 763365627 914021216 645719014 839902772 817377810 776419897 997893599 519601619 426696405 650444467 801275726 635275702 820370288 775315393 36394220 411046837 47444072 99189241 798590998 732700890 389960476 718452874 666346367 396633149 531823084 362389393 461201974 389405149 581771552 888644295 973572051 544823466 734478744 269673440 778548536 708437470 47278092 528826893 174457382 823147480 331215904 26712281 315722044 360706203 76907241 955616347 785334993 113055742 92966829 842572083 17864188 557985550 551085597 553395767 416364473 451369259 834112755 919327151 583935792 277078754 911059781 796748065 614682830 901888776 129460055 672114586 473934287 651179756 255703618 313057129 653262645 856217813 254823807 979538876 971656313 256241901 405461973 613593159 432642395 57845344 76601345 566763355 302862729 520115518 986390332 76110179 732672155 367161915 630668168 543475861 301897524 406425715 224047302 332433816 621729297 919151081 20817288 293336438 66390159 967670647 636268720 109467559 428571845 431423953 344301840 496001444 218365899 364195761 347281976 199507291 731983318 719908293 267948441 424746652 966557926 534362898 741830153 94591193 730123382 469602607 626713886 347640769 697544644 767348522 853113863 716257718 724802809 99839935 346413201 216419383 330279997 222490783 410655161 756495634 351379025 47087803 310778336 66754894 80320614 925002766 175783340 312566338 981058628 488390702 562476675 589528748 576984397 38431990 258690181 409863261 715370836 922156052 907290458 519973718 901690323 23041998 615958011 743093204 722096610 128543500 638768815 95358812 89426642 268777792 206714750 895804281 9368446 906493546 264227722 266677525 569745062 897233339 253386714 237031034 236530530 417396313 53449861 655878632 389685301 504037705 556424731 294837413 853142350 882665011 510300425 753375429 497222557 366859543 199432064 780635788 482870822 362535645 9125476 692455376 701477208 953635589 432398604 89790122 970997303 661083754 735108239 592293187 466756460 220775009 863725923 682942439 175560883 458303599 440973309 449762689 231294740 769761676 149964713 985895138 774878150 317402497 439604084 557445960 352055908 946146579 903274800 562684951 743967513 601331620 890780211 43401161 289722654 436249873 367504801 713103405 63113673 750416339 522770265 853615026 137172117 340653335 186599779 331878144 987514477 225926635 571194924 499377892 561426162 255035431 515490188 733854801 73457892 323367935 394922586 635860635 326094669 548440041 650059751 102598274 247180627 961836896 948477365 228336541 864553879 2641041 506212328 441859818 144693310 676173157 201385137 479374398 393728292 370130106 113811571 721499440 844674235 462074783 109574432 757864014 243061782 17886766 470597861 446844143 996778266 657410330 401258572 707572757 688069673 738643701 398412112 458708661 923290033 688863043 704385926 341947258 886130412 893761855 623753632 193771001 71089182 681709208 366595511 618088040 274386421 460243615 382526461 632331887 418047864 646415351 444096154 161543227 846340450 66276059 652271358 38602385 787472663 284641852 542532007 442602483 911759443 268621984 977049544 137425684 637832813 860863353 234098922 819189753 798218121 988262631 646542626 251596787 79990044 56494258 754859540 352481879 445416524 88458791 5765591 99382908 961089855 134389528 998855099 441953351 612946675 982686638 609199380 253652462 964605793 522347374 944645829 461383247 468533955 386630810 140204525 915617714 245851842 401616506 928843002 949501777 392748758 443320065 873178881 246871218 832928734 774151357 911210707 618157302 338332301 466476617 591580302 605522912 347699336 112881314 751884919 696501618 410452061 887280571 576591523 178102294 171760311 524453795 950723720 954624020 194537458 428589429 69458242 826294386 652493002 56848976 791708294 124753717 201663965 759842762 737611864 601298116 530378083 266030916 450187877 301869068 636325422 454388237 57897363 52753413 961780132 869681113 133020221 161965315 873878092 403330977 630618943 757462856 725076626 888605408 666550663 674145554 269402713 45637143 180501001 301252258 908873412 681511968 373521895 79006880 552899735 688543099 186945459 374073322 392091962 899331083 738737419 784311758 955434315 952982764 108069596 65065535 581476789 528086970 229931257 821644201 840211602 609190500 228361083 110186243 953609497 718186302 45482473 250547145 103564587 371770652 190252278 304648903 551383610 482642100 347521953 738821625 541372286 213312628 689246474 394275002 181050898 456179255 841351605 906494654 792413084 742717104 553925544 749315795 859021231 342897956 640656578 141995507 936702602 41010727 711128467 613956619 92308721 871495007 534426792 835529926 550908756 640209737 235101915 809593265 466738295 868308179 40632213 177870407 285401469 498527796 339301737 220951168 572623171 550138414 236885017 460391496 978512530 983260014 13081034 962010995 474887834 63655723 187527319 842755600 77439881 59264186 734633836 644737125 606359858 86017227 243470290 194148220 327327560 218235357 636905217 793589103 51172892 258294600 864370325 211926334 708359623 568857819 124574234 405272009 840608160 997370256 425743299 92756510 612741384 570743809 851117103 61143590 585608319 187531013 350454663 465247909 156806227 554621434 981188636 426586285 785277700 990433597 395770441 317329707 634726640 564140286 197412903 586604079 505117189 124782447 925107358 426720479 655206009 286617707 882239742 550737539 892752712 123204192 162051662 55390335 630791574 901110317 148140815 987378351 697339494 674638953 376485964 775643195 816534909 707095387 62276101 672625142 846433600 556972656 57889957 288966451 513776968 593709359 780399277 58748807 435994454 193566235 110665301 679172156 116983233 699253481 602721201 68384942 406544630 562415567 740423914 481415726 717505863 266779331 54343773 338852096 172147698 237041912 584018847 595527609 474668245 416728145 572107214 274014952 357049319 621753411 151261709 267393118 3161388 48998022 357656682 115364382 176523440 266238802 625660403 527470951 618808459 105878319 794449702 503488092 916354869 641017308 636171642 753949940 615595032 428868177 321724602 313636119 419058068 809560971 824994417 837527722 585524576 521183836 941396893 325545768 830516127 152269055 263654629 622920340 738245320 222788474 611105042 883519308 587992778 45520147 920496843 354367155 908280996 859548586 437658917 93462406 528994672 744558986 871099046 609414176 530434888 62407919 652695193 352391490 819069787 927513019 279700482 157508390 836078568 882770567 384233662 305795837 625602824 250031193 50741276 611699106 655539902 985807134 737555074 167160029 736308324 945291011 487337404 287371292 403640161 404472355 29183787 589474370 727076417 603904552 658911960 351231589 719332337 441595076 714387902 793560219 35295244 156331654 226606446 684838919 855651216 338558279 172590098 813917854 906336634 65790589 989247002 999360901 276179833 387177600 14128477 804912678 601157394 42189820 757103563 538864751 637957718 410521564 425066876 233327135 348666661 215485519 136189859 755924059 530834586 701024216 676433696 878916023 159175342 841476435 569723599 775614909 622054117 84454241 892052379 379484941 160119447 329420474 793511107 750764251 182027007 556954121 717817882 115371766 200006452 328102763 617688831 849079971 107591113 636616552 175586729 999697716 761223651 9859687 199117745 598702236 733902954 943972532 925932912 625772006 928803663 333172681 300981347 800225343 940689907 847148898 715841804 529359224 536253579 527748490 587355844 452887748 802784122 290068244 954478660 566515418 516138219 646225911 764297527 166192477 797292976 990468720 921463218 821857400 378173138 740250757 109760359 354750513 943481902 535366436 95805953 74828497 824430631 732888335 673352912 907137565 878884045 846857454 363690903 520044250 839506757 349319711 907853448 329563016 685522408 343557555 69673890 581718058 272316806 437585510 390367866 980768012 360208883 389000232 768222359 452650665 302870161 554401979 424774724 187435665 856902214 507575001 583494373 60012690 803061007 197868668 653976721 809787131 266402756 736270881 383730022 692567910 704680991 917227353 171154490 368528998 694666902 835817256 215852313 8428576 392551141 941734695 457730757 897263885 271765758 885649721 44486872 534169405 698918736 506366058 3537405 235242498 484047421 919689277 402177812 72323384 179689585 767835949 561972631 265815042 456326507 943276162 79129514 122489121 884467946 370113071 915942664 813664837 130842438 132248765 537773955 481514040 90115538 189869816 103872670 906543153 381699723 885684592 297684913 957874057 956707714 906529804 771901304 835916174 145938029 824856012 144274711 868935175 469355889 762499478 239108284 189500960 505412250 730309518 118515397 552900300 767981201 727178497 709415007 321269817 9096174 685056429 500625074 485929632 912749123 425641057 249965103 251257733 137224853 424070032 774273562 968061658 554638611 684736516 932787971 448588693 67736964 451328081 949204577 46856022 120056873 233625517 590560901 770871421 182365048 219312386 638768422 966438284 797828244 213290364 944354191 529113921 494008625 609822441 177389663 305990489 866413672 769800849 843553100 484019958 56957386 732799812 170381721 940704842 797063383 919518226 909394445 895494747 905608786 533267143 176757114 951198043 931179421 635070931 256198023 557307600 962929643 623835633 458501603 404487894 596931008 926358715 852216720 792943051 154190299 77335454 41696997 689480864 285190470 398260472 651577551 846615011 72277342 228523667 976515156 564024960 170741608 295225158 190810127 831948321 69898701 225936091 757761583 128832997 320641383 435264514 251875975 677303353 595513827 299377461 465546921 502752504 12251597 545346699 142281516 48171370 710612822 499426369 249138467 860608358 894552514 4681448 628633453 280470983 820571132 938647476 5596594 302274763 266684165 520904266 293072801 938511717 281618308 947343447 294886683 499304776 259310697 142191262 387731339 378259163 742688852 688992668 812081758 110903321 143466959 332373864 98392789 350179448 939535497 291295664 399467148 742341419 597385077 285108901 9515511 559102340 755086653 834133885 690894960 615530875 488490596 983572649 675760366 834500907 554415488 318479233 452556928 454521676 173926624 488652825 740430990 289787355 412317024 113763031 255536695 272981011 552924948 863573239 236148140 953301982 589885410 224868551 455750359 236134783 305319543 950047838 505085 466414265 303110298 113621477 450029930 75683304 688521504 718298236 40663866 43101565 79914370 228541898 193789264 491486429 702653114 783015029 446907677 369155505 649847429 205331701 676185191 64819588 714435692 253226914 461783744 627209640 102490823 52374561 231408096 738791383 785586543 551172352 387184122 203264344 237323750 743726133 308493254 772432649 935437983 668644284 975995686 638318919 211465456 740544001 56651177 134107972 711933485 647534785 55685999 427327204 571511021 763817007 323309478 362823597 781960199 122454804 700422123 629603067 739309714 758192476 605251817 748834825 986323762 221967376 149518059 866443367 961802564 30268959 582066967 917987586 681920129 689882304 778807893 992578720 257570174 923403799 715386336 847875526 968019264 549494032 846476180 12756538 76345542 429192059 671365488 651919704 814752970 803079184 610951255 85230538 535687532 547941455 594997267 299126192 187982258 365255607 250000903 580077158 705591129 511365437 268040476 751987901 423204946 430633375 45469023 49414163 715051460 287081392 51561038 371819003 616962845 191450173 867529771 413217900 328496718 332274860 841426092 673933374 173330336 239196619 853568898 815880843 117581169 1495442 348769101 594561449 791164792 241425033 480903174 840392217 417525221 327935272 776906303 463846261 530182940 445598287 294095613 984882895 302838900 932939986 445411078 823481783 238527930 41287572 531780510 257468325 850306482 353266925 1875768 863012772 126814137 321591324 588611271 823065490 143702195 864348016 942411961 968067844 507537568 961382926 6704927 54002603 417902887 682003975 502262581 729761626 414622973 930801564 731303282 35679174 377258461 455914575 694062028 267858283 18219551 39070999 394118158 207805744 56572890 953416235 281298022 828635803 720614178 751559192 967786906 108364221 205960154 329472858 649115540 119069069 72190342 273142270 980191687 208863691 337857318 894679339 525121425 509389819 974185388 145902137 350489086 791483232 815990627 320510744 402800631 447383017 936281351 567584658 84995556 128998236 562537187 405549444 745259163 728142495 12902426 430335450 217006106 250359551 537658275 647768706 874522815 660199975 672548286 595947605 825570518 726399141 560958290 405977490 121050562 644975664 331056954 541205156 846760682 950117503 481971373 411708162 528555735 2137854 721016723 164465103 364451241 296187619 487057000 953787643 210942133 342993428 617102970 97789227 48399234 331810855 852175713 941999576 598893275 421114598 462379463 10734984 489732436 23569127 82314086 313415066 922747866 595237093 35429793 573604420 317425977 139013285 770834443 89627878 89151330 346943489 580373386 238502284 970326212 901410456 99748623 856897544 737126736 586348985 19312357 473483622 429588973 82996732 262588685 322111961 905206371 22033401 330388978 399172991 462303956 837792803 568242671 11966251 895519892 596795904 285120396 28515984 26749965 335765090 994648583 679035963 27648116 817051548 829962759 540367258 43902605 811307357 178623868 115594496 515464374 713076050 45598219 515082591 591835041 998104264 401383552 596889844 48492215 497740313 298201411 697388049 759899060 165092027 530486165 452649217 404732794 24333856 987989276 14038462 132444713 656966295 855126922 161364439 258825275 117983711 381706194 436196306 250913093 737889117 551703230 742330511 601908208 630989233 44783075 763580585 389968617 878543841 897601957 780116247 128708877 885346979 542265459 55980153 51985516 443362546 289534057 958348852 349174805 443424675 426043663 730933521 121928436 99899594 1132277 842170614 595398311 971780520 272945789 472045979 844369204 275037129 234881516 469474559 586797684 293359818 724255075 725186432 635619031 397405755 960777639 910798005 860841257 221572328 28497617 90791620 808310954 718705366 661423567 727810892 384556598 455694870 130206054 950415950 768798618 749028472 872401925 570478242 736460467 991973163 754013563 468705046 830453288 542470357 89747961 56732766 107852660 598016697 675394011 217615975 496238084 955393963 588517867 328413820 41896754 989889145 306697902 600154408 202802398 741752457 319543134 946467487 750823514 459983541 316998476 462330410 799432838 74237419 823908134 848599040 599467214 952239962 247903976 117869376 690853297 743445540 505225860 184012918 709813620 980457199 499327109 301551135 150324511 653538868 920469356 610295095 878614900 617237104 839654331 549523604 920676402 27032884 879062430 305675050 289883905 805612704 110015596 442725635 460222805 660595268 104653249 825905961 665883301 805849059 22933307 321673201 234215483 360907872 778488479 946205049 728603170 119160687 71601614 204301841 467370415 941048584 354726205 248893654 238015000 653461904 237199669 972331105 601599793 809982230 602957677 435802441 999948495 366803134 618687156 731695148 174060648 332177175 233115744 297255402 86890771 381377807 484607283 312137982 532963438 754066824 706605866 146351515 556578468 565129681 319629030 554000360 829941350 294222121 264568522 530352514 588468286 498433266 97668611 782518899 698684564 479365698 287690567 832734635 510950426 321446740 787898677 37194855 486231569 544114799 405008078 417710596 765883319 600379799 482722438 755814284 241922036 201214883 132341873 688824953 313617404 538242531 55795205 268922338 803344633 438953764 542680211 87701899 678588051 382578774 741118357 176256021 135797685 630050468 229972084 916710905 912273457 713790289 626764975 206847164 495957765 968796645 954521915 928469765 134396761 709178538 258242289 83675686 25744692 683325201 81233636 641142421 398924585 26048156 263129506 524071854 87937804 762565634 678561766 953407238 836863087 743949265 621230538 765535486 282230418 677116361 244897944 587575258 138055546 669946390 161270743 78629930 241671680 720655330 184367738 2371401 957662096 316272674 712425289 365148302 800818561 621307899 585713587 759403226 731066394 928826724 766705833 497189572 167090070 444797753 818909445 674938844 634413279 540356472 928581022 924515509 338402799 280472190 73050339 412631699 760988752 236803782 362180127 706264504 782417766 551302395 468614819 615686872 35881097 918978928 590141844 982005944 909895275 365328922 781134614 666635706 802262366 710993284 501566885 800419705 481873113 328024695 435996742 91026756 699256885 835772993 571334044 135525924 539110816 726540758 413186104 779192666 939993526 549438491 715269337 394123830 446696329 297938178 746037365 280638667 364916477 868682098 10683753 844373021 758554701 629503512 521071231 173640995 134928364 893098948 191616542 473583972 712028161 145198102 466935697 526323789 137620531 705327264 460026344 641355428 866389620 173808042 353630792 3057903 104192785 333523811 552667584 572525683 224208068 458847057 447890569 929609881 523265944 694118789 126100163 668649646 164134834 900782713 720253012 595435266 944424397 581666246 650075494 925402527 151179603 845225975 72685275 984152902 319484197 463208492 851803417 376490681 788484860 525952500 196361412 54055545 560224555 867573630 536304698 988527760 230100633 623055004 364729512 970313800 292406274 519187231 326233197 820986721 450333463 320674159 387784052 752334738 85431955 596619379 622812177 692512428 430560127 863212261 685714157 568772870 926404487 199799258 167994402 562629865 115976338 54910082 711453655 619904520 600481503 388655450 67624347 185694099 491685733 797283409 811068504 276547108 739866727 129158928 698763275 43473254 904701298 543133515 523300731 760156356 157821210 857420874 747016683 620417650 813493688 390637802 652308176 13237755 816501243 886723178 762748027 472956261 711507479 164863487 23732442 176770918 879304026 862636911 941745492 640210905 666545245 833177293 363923758 585895937 380925129 923184832 267787739 693336170 900988273 604456595 563194544 154912125 754279738 891104365 137741625 258298160 21005410 116802155 872347510 613040516 375900500 375811743 715515951 402935885 653994651 191801987 159897873 834483496 781874999 774382845 972631310 626131114 820848593 524971590 42174578 495361934 79906231 975086137 532004647 126492622 650558464 201425453 316008535 724268283 114458516 607967166 695635161 285528626 26585778 221039398 873672758 605690881 861955791 923913874 442024119 599192335 22498870 959286842 628102173 958187896 818427645 770167706 842584984 873160075 437425451 142659919 168256501 800698569 276257462 50885024 420788654 483259205 121045160 557759332 673781106 98536418 876280326 157406545 157747950 808460315 186388846 416400077 700523595 812125108 705569994 668834124 394660941 61631459 592654017 312000311 979410744 501434658 23639640 939876051 339605022 587753095 392476488 52349579 54139241 69386656 681575078 108819119 687504886 255688625 838470468 22511512 150728962 369117044 520812041 225682523 45381858 242248537 265402058 484507383 947596088 775006997 312479728 200723078 98274797 145621061 504001443 972853497 136112943 551164454 808716732 339454023 148770899 698350381 649079858 837926252 641087953 630325861 128995495 485078724 839749530 966936390 90632949 832717617 718256794 833609714 801593362 52311419 16336934 80058729 97361597 284369251 756933193 800464532 680476940 565185244 459162391 662038672 320107678 182742416 485173534 208479157 548817689 119687038 668776631 10393722 393433021 35670178 504740817 888420924 61785890 905803528 917600 341487384 392686874 453300741 780854956 549641506 650827730 142905492 913939662 198112074 442583513 102647853 458784637 590829437 828383796 122296580 671498117 975669270 401672750 875414808 217757405 750639927 783596221 960283523 701937441 547640019 723490065 610742914 435459056 92033047 826196433 57387991 439380969 352355004 729732997 693176580 347243918 790417320 891181408 994247665 855807357 107883916 257764854 427862859 425768924 721340277 444273108 619092599 755095187 366542698 632735973 213609392 862674096 109216218 230376378 352348556 442255390 443229390 654470859 247575826 211397067 312068285 718135311 896082065 195085242 888016280 293983473 518389682 355214019 641410687 286976401 940895012 782514629 784390376 996137894 93015077 407996791 957057769 440168864 533271711 445719170 97015164 51595596 560524527 822145662 923319402 316975512 105019771 31142289 872703610 995761429 655653340 260944373 673998320 323337987 171763742 722454384 633507633 424537783 254520612 943580166 396452841 714825176 846630585 593279455 705914742 624323552 941866477 124601639 288056198 927011560 548765614 408816226 175064820 218081371 428145266 115517263 347715489 440729531 306079111 695964794 461135174 984630718 41580762 471589935 364515052 774301257 437308506 627946009 138234327 555795911 153246584 23728359 131319321 88308986 691576690 579603714 723277406 120342305 647465323 448120458 128177526 331011031 60930247 289111346 348261359 749210730 959397656 878952948 224062142 216975753 326414672 124816950 787195801 254337519 685468762 252790011 328884518 145791357 782273399 884723224 406922510 608590564 50149193 40381380 441961111 670014566 925286876 109830714 858649261 720442452 558519289 612804827 951335271 127991120 983776663 176717207 565271476 316122771 83109849 245534314 839367298 768069008 802299498 421868073 960900029 309336537 427199780 452759105 441711180 924903264 874943120 529656176 673906226 872137703 146665844 647953175 134415807 261421433 664851383 892051370 705923755 271628016 709952001 278454361 552371477 917771676 237206134 309491546 751838793 781479579 308318147 847404016 24230771 962459012 849036782 903161453 893680128 846995071 271289451 425403472 468848272 732451022 517531183 284726925 542808200 128093954 432142159 124034246 398491200 547716113 818975313 304819297 181217834 17362713 633350890 913369629 256965793 374029392 882447034 833257494 861156478 687249306 329802582 993335441 766338972 872090732 185882770 164449640 222161001 216022356 348204083 382494927 980873790 474514038 327256206 483556279 97875293 99906750 144983498 62049491 93098853 387486768 90093203 51840303 788812072 916463047 920068374 34155507 288216110 749377138 522163649 261349715 588973381 739938753 740029504 227249906 262446531 343757360 752281448 497739061 283997213 179321627 708378688 185937195 210251729 782535461 188812036 366035177 439973435 233740063 844969291 199287192 519200284 538956433 240463616 175370757 35163069 455235973 435684006 138745381 930971646 330757782 461495764 258991505 465878393 200210562 86992157 237653021 524874465 373111835 737444356 669889211 688368567 729227532 373561606 550695446 681483339 295577054 698468165 699987218 421251133 529976955 502297602 362657569 455593809 150330732 526397341 850310981 107263634 121931002 464650007 564975717 88886437 536849833 693996118 836817440 848707331 618931625 335954080 939810583 454428858 775360051 655008717 681772237 675090458 263027455 915173029 496374461 368715983 588915647 237670447 94139433 918952730 116987796 848097258 290131759 421040282 27083669 904526749 672409866 272644823 461727975 230873768 892914947 483252633 306905631 474343722 167614111 159471721 953269019 780660053 668326127 740241209 189402891 680422324 21381117 241881161 60399644 933029541 675440503 168122784 177045200 878257975 162683561 491231256 700869741 531830509 125297019 564443617 57453281 212382670 96045204 565980184 602626035 66014597 123622708 956955061 613407000 784807348 241255732 80857452 739170208 133457425 559446091 472493054 578365324 852134651 824903424 247070564 830697242 485831103 161708779 291267466 472354953 988860215 681023572 278111493 403189995 496743224 857380939 868139174 58437199 186091199 502785939 484224393 787655746 409004687 954725203 308311619 297291503 684815783 911549489 37739515 217771413 173838372 87494921 6719861 883905097 100705503 55323870 334086324 991692703 545297451 520935763 554226216 748218448 133504246 176330236 365388994 566814869 850844609 789324674 123021720 822497706 395096588 285571444 971147831 856524500 886758992 923787007 953816549 420736847 505032945 473898635 763039646 900527425 991217783 872214133 571984058 347458048 233780607 610333172 70581186 941922947 523389754 864003025 726118795 973669758 246889948 822728605 290132606 287923550 406072805 98096990 173228649 423141661 544876205 806068048 619200306 27543785 331751303 842590323 853717924 942962542 747314458 383797648 453649997 690173716 449730246 764932480 682099370 895468563 386201835 646378137 272574275 931561018 810513410 468805000 576019297 726865653 273889968 12849607 648977244 68672884 723518932 22992716 387072710 570690234 176238705 628095253 762684142 322707115 492474172 192072099 656735999 289662760 105478627 916116663 213722540 312581768 825533713 131915067 715087064 544651850 873039486 205268893 771971991 169819500 781147681 100461266 756758994 500167325 964893819 560110042 292227121 982926183 813548478 978755853 677166254 967877771 850532504 860927615 181456061 83222670 163880078 775285281 868400914 783794509 167058184 174843965 384207329 54386206 293216200 269020654 804507530 199216312 981260175 102128015 238402855 68417740 792029095 951556689 505910501 54509067 449640535 168028862 478995171 208646036 163442827 935849647 884001322 638793505 206956004 635975929 707986674 574618879 853103623 363160351 81077412 698820675 634402765 319022548 622927907 261228306 956452395 340546787 650963616 158410272 943201794 631647000 458493391 36196151 159708492 362592580 507888897 565554754 863872825 509138603 168821566 989093725 510627976 524351631 977295945 697192056 239876040 261647261 15048486 505777026 388677617 358148533 142025009 400606868 446614396 966676014 577892999 132268717 468119031 106020595 207627765 248618130 564383362 214254057 869803004 987175728 316725593 448766317 440212437 190347617 541396174 765379566 868709718 889223658 211104331 453532237 731673666 987478564 372092100 405382646 758152715 320643556 481829688 149659184 197038417 423056304 871167249 315971564 799693831 23093300 36544810 304944329 928767438 813800254 26899995 741914873 566250502 66177786 905580281 598983680 662110887 451927693 292076146 574909923 132191323 165855000 726380291 905230411 886578398 889321712 208815614 748204215 210034352 999857714 583796434 109145362 559157888 388962719 779672744 398821984 238326559 662819780 691819721 431410591 913574746 905404605 848263355 633123590 876461770 211737233 579288038 607790960 665226461 981799997 142961467 290981753 961324652 257072452 410613507 916342053 88061162 740594824 190642705 27755495 349389083 673424401 13950284 773869129 334997013 64717879 334869528 879233591 884854995 170368978 58954315 486785353 382125808 979843633 159786940 305224898 857685659 513101368 465534257 800037220 732276682 2520238 748310426 760820281 945347085 442456111 604415247 404172015 351390711 97290807 472957843 765104425 675676925 64392174 363584683 244157432 639995296 66855121 999734943 258073064 322532854 877852409 361815795 689613539 562627596 811356395 116791667 558133190 909794757 109233668 432739248 954776462 598692976 16339589 63324376 170320627 396891965 111096543 167500786 392769188 940945210 909223074 983934985 221912960 244043149 624435634 13584589 605355391 597845557 816149047 880168688 712519635 585435109 354260094 832394992 863750674 435809686 483930098 304172675 518535952 260779456 195539091 645937084 211377302 719864740 833228090 767165818 762058163 87311511 457885619 726986754 890247511 16783838 346020779 816872141 513702571 198888668 731552894 515120078 137420791 979661721 690855833 333653372 380960922 965233456 667499565 576336069 842363012 634264402 896840830 63183250 869824917 491789716 317252789 645091689 501298994 973468614 486233583 519406953 476301322 448227795 990656647 924611384 132866997 794560171 806884721 652673905 319940689 105375388 136550603 454849174 947114080 197922477 549993857 363895290 739736478 202133093 410421989 458988526 694343853 990186017 19074362 892154761 463236262 566809103 383561645 402317326 192842687 121378618 101977140 403078084 516250961 976697714 936572439 704090136 300093161 425976405 545838375 475107534 826435551 708936107 222398869 273279728 725963010 39927131 863443560 726071624 768918447 427876686 11552735 679800316 690868632 398708747 442260551 77443614 692119516 972910025 110526188 80840361 412157916 117676038 460584008 251205032 153541063 905995999 5622445 751751871 580225915 961715952 145936641 185365120 665344936 261693537 722953078 393908004 29727207 493414315 690301625 851107907 379858499 895030026 903401708 539638852 754426814 196536980 274518596 407627877 42846024 629363277 603881734 604758553 525487283 654182130 651549158 356832978 374542339 715221509 203585376 940014637 149884070 275868584 573984401 916198808 358022121 694096575 436064265 79595313 309575171 940094271 157001106 995415401 997366709 367830272 800168609 245661424 611452723 8830294 983513853 926411456 718560234 510347015 186839885 190571513 279148594 773212819 13525709 442052144 374940351 475600555 905160618 286603261 271406060 24966418 881269069 975146015 696803768 907408929 373092698 78387210 626095326 879825601 893940349 264793612 1336686 456984312 167831497 268714571 779195963 801345306 538256016 281141044 162664676 929946016 722399763 440711734 86851077 153786518 86257981 438697543 618223052 771121196 692215004 306668770 333769195 19076588 246444078 361709516 492958989 820816800 347262326 486506997 730922071 922463704 316754503 630128954 930974981 100352804 469132304 120808787 166737760 23830658 394795395 662590549 473948123 415443506 355209238 125340566 510104560 429579000 893470399 510609116 457810862 261153560 422319558 885392568 342444194 360869605 546523388 837311981 809683407 277885207 833846429 144600651 849130498 625525273 935169081 325105250 864266697 429758117 852131021 973896736 754611690 713830257 47265439 587376145 687674577 469959993 385361956 669406444 87412710 978771931 887329195 645945473 147149438 213632275 739156781 711638632 191744915 909403091 172212215 547823152 556036387 89405952 342936620 155843646 108498076 161130707 174542823 118463401 23997499 900762500 493344243 142610733 251406726 900871796 808537807 824825251 631997018 438730299 93517138 840494896 385870538 58452585 252279519 43411655 369250741 830485220 583687192 45223688 781066086 498249845 357644377 937201527 56494567 993118120 486380517 610522564 142791840 467505949 180892125 823381537 965332368 580908369 618453335 920506634 52952538 625286014 156910238 353253290 347990273 957105051 912361304 559836888 357165942 135097251 816352310 892146682 613675232 872409633 954200790 585506035 263169992 520875444 731602615 748290848 881046959 859906479 829886901 454499907 307502145 86079669 850843129 359347783 929472049 464438750 327529437 561886293 717100735 439737517 702140299 924897141 995442769 261251689 974150880 217107367 648585495 68825161 534950785 439507373 63274530 643283725 83316142 573092286 273764279 671716158 470920710 50840880 235383447 424482763 178840493 767586955 332376611 91137722 51158353 146486074 239408493 119761249 80640160 347070271 529769846 711486973 518801524 299721100 120182509 107800974 711026168 931768358 196178818 65802031 873367316 998496702 754830310 949275477 959643768 497380666 954142410 698667523 540014035 129809523 434014224 919457470 185324870 580218125 748775943 993763580 284305142 612838672 998285929 888530350 351922774 638617980 689916239 617235265 95061055 254139360 594219150 238227299 507764646 235896251 866831414 853908454 890113794 185355496 235611170 430760342 479205811 835863676 783186385 798060358 584181520 241436027 230796145 479519546 565066969 190013276 271988016 945568487 762730962 94407833 971953969 647605546 487044295 138307977 374432945 584806246 269312385 960404986 304249289 735506560 925758170 890993151 433697045 930372192 43074851 63541583 262554866 346597685 399804053 635042011 946068065 664644571 651872054 83012301 812470008 658638031 648818706 295381231 786404638 408445315 188322874 934653631 856386046 674139310 744172026 523310051 459890520 636229754 657837123 814298147 97641205 234730088 963695750 808597244 600725680 895543869 259908936 808169693 496075318 840307968 228228809 737587542 276829227 563106947 923990025 425377614 206641476 83785656 864318089 651960705 588573597 404211959 157963379 422336639 492573600 970684218 452116582 303138431 376700895 677955469 298570280 190490510 895475011 252904307 30623868 937446336 296413116 208962657 692036738 472101155 605595404 968963292 449195764 29590064 157648239 907032529 255895313 218132474 943380218 981009243 735898677 861683310 451031425 904282446 761943405 635156861 950562048 833270815 765817833 683141978 745226138 43899801 503218459 161680267 680995699 87127160 833829089 851061524 644350007 561512491 983564036 33263183 448456730 664224270 522072100 747024876 439710721 292374169 249933804 153228969 644777788 453814168 792447695 864835688 856350667 52108368 520970743 598497539 408847986 167863842 697176279 996565659 541299982 161316104 173150811 959760043 643054399 18877318 321661892 586290794 282664534 479572538 723264286 133931332 722988996 523738194 372519368 832125500 396684592 579946183 992261620 405796428 543124491 324492037 527449851 65606306 985850416 732613752 890386902 426969404 271117844 534765340 262272273 138953502 697187765 658511001 410942450 818662279 151893125 904028781 598649483 402875173 47329647 669152123 492537757 694245751 511275572 456152293 531451679 339542233 126677422 928407240 116590925 990323849 366597966 377155794 448229467 763529012 350081311 890358296 739928945 215091634 926376275 245343705 946644113 477261503 201017399 191014074 751176196 240124107 931102994 613822361 229808813 107341472 758497541 815714849 907790357 892570311 586382746 352875031 714999438 606357379 855973108 959898455 683061016 101620517 153762135 480229541 821562240 650577686 319609191 698683493 209090740 521235384 49049017 499223235 311901957 291165933 880463043 163769807 313404017 643982789 190008384 922565418 505553316 293443366 301519466 987083113 422756841 520587677 387918016 594079603 372569679 331490657 824702166 727738141 879772781 66458282 870558514 831002196 492779614 821558009 249264931 893667154 463860039 127618118 61320693 161975170 223990661 667377928 104088598 117168850 533104884 626642613 605771974 914965192 868894626 345601028 141055237 589134778 127365646 297479387 154037568 70098847 338610455 128642437 148364698 809188476 650454284 242416219 85782103 472872437 108538499 557231970 357563589 139780842 673749131 993622001 556677451 460730242 309440988 145625484 943804551 464437823 854033980 455489168 506010669 302950634 959985954 179504071 842896215 977177058 728944662 837467529 929101251 489596449 764587865 964382287 274745733 102219865 926256073 426449836 823117493 983464546 783047776 407627210 195768856 772084624 606361820 524777233 848138853 549403062 85311595 480399416 302793918 248627970 336193757 564949777 742825738 389901466 746795593 240104577 531800800 402835513 422591938 717251474 410908492 471526356 350610747 657695515 607784010 967991287 874949644 757558763 171674072 172024660 833479701 715290320 259186327 618137960 50721826 714767110 111461919 863310843 65913569 356133324 357311954 115750450 870206337 758743255 568321086 899695223 210591871 815292999 111447465 779032554 950202405 402102105 775276804 252857177 368985760 509505512 294907636 927271078 715499638 911455832 858321266 662434920 569897517 716111307 355523377 126053743 952683754 745045916 268603602 422132993 592004216 55996431 556730438 809633815 627338730 338600707 222905233 248165307 117605934 706848537 636281768 529550295 625721199 979667611 554689320 509205030 86536693 757107500 173097680 963693261 608945352 800716113 214877771 411888748 512292827 726387732 255480313 959301947 877201884 501824751 672401742 570280338 817316874 620412765 569674609 281323677 521863686 12211672 809864607 38887937 54196216 408751829 541051485 315222053 947677792 234279605 773126219 944407855 890421559 428993565 958412349 345376603 377554710 464985239 766928859 685964409 79970543 238460287 962447169 496541029 135691438 88349811 219347711 948165333 103306242 825145832 343755180 959794854 982728339 515783172 960096735 630531126 654970971 30080444 189208918 37004970 99402795 437161035 9834261 956605 142042069 524803663 22447806 65313183 707442430 93809984 736827490 575278060 701226327 595973751 560070195 243411286 888027569 512229533 925168337 195179741 865693437 600617639 683704430 933532169 914370722 62709348 119070047 176921763 515554094 149050284 485663870 999492650 209218890 869600832 44031964 997001606 89729143 602225793 572167717 447666807 9395924 850269770 969727366 494407885 188841510 17145854 218312027 915842646 469957133 867517227 763277397 197738536 84016036 653828779 227283715 395306358 708456909 438513041 453755916 164982900 364865873 790209745 486212898 233353742 572255385 645552804 598173846 986947610 933112884 155765797 382401540 220778540 848128573 554769643 891460216 683543321 520906462 423909041 340848418 311748381 824152404 94580285 207903426 270068253 994914763 595496214 734697804 962384707 969211407 743172540 341207103 576491943 124034712 465940936 477263624 961458150 660552858 551533639 382536361 259925558 427518573 134719862 34997034 811088778 145693209 119896783 937562731 620168174 516929683 755527905 188504016 783938183 500996795 269518753 194430209 515073154 91923623 734765347 642645329 607033704 245663888 378825347 777310681 839880249 53737726 351769333 876964568 588416674 623410953 692117180 444858862 731802792 317631692 262698895 932868437 599788314 387030291 151415331 505582576 80733846 3045955 788319338 29900943 935186407 454353682 970883048 462065936 523731159 742342882 482891630 344988760 829114443 307648606 702308971 250634039 241138574 480081965 260327517 69038696 564769321 685038102 932782047 997808002 941585913 295817491 568010188 408431147 783033776 700231997 623917126 927903606 72169045 203279272 689661994 333801007 241030450 340581401 356723731 591515081 324388944 662594774 472269571 605399393 104044522 317036301 53379204 979971942 978139681 668706310 878350959 748122063 986759241 118458719 974759913 313748043 702524894 778711047 120383091 542888628 624647460 443909635 362613808 149001034 954482774 495456148 854293025 888947770 291240132 540599359 857392802 692278762 959533713 994699909 338091298 985109153 246424554 416759067 725724346 620882775 172333897 64622284 133804656 540991570 506781407 109155999 373020245 389897875 815824715 868351054 201156024 721226549 544552161 899897426 943312838 354455732 77933825 652249676 263646484 980389658 249017493 166058332 626604152 890198641 458208033 70044680 455019186 301267803 245013045 611446597 945124864 381686393 269565080 639131798 298543786 240951139 623572177 114679273 850241011 884583230 173521602 172752339 41644965 820420210 955090201 813684116 595251474 885692589 657707944 803872121 970446320 827780747 586770834 320965822 617125206 106357348 821123436 969036941 852251314 6614116 985918645 478139015 496795299 514386067 535836251 874140193 392522927 851255698 73951574 368920906 30310978 843030146 333554295 890006687 373254772 586072634 154694821 855273714 250259314 633068656 689504781 888307381 144556351 15201517 426524644 206038220 707351367 100109534 442554421 453832602 285074828 835952941 865245888 857300179 243408487 774699149 408322551 731808913 46033879 230499066 642594128 92349133 327265062 772222263 81404456 738245501 363811734 23556002 606857879 388649357 904609449 18446362 288526394 503923271 458098707 477855964 648780644 979530393 214256701 660705910 50495794 182223670 628185431 560204245 347779822 411815018 217546454 723452272 56538499 78543597 497895839 195216621 215742659 682707436 39251015 552896086 399952645 900104496 191446514 824944912 749700950 793180176 651983187 597803338 93428428 942305112 275005479 342735244 587466611 250453404 501428969 319800118 425430962 486478560 970935270 37325905 265744172 348104268 685733565 89557362 931279592 985857415 848474600 287983632 246877735 567665683 332101635 982554038 146571709 298378718 551350075 767820724 303999458 450550937 645330771 311227891 622359842 294547119 888820977 447672367 88933755 45149479 111488173 496694901 348342844 550967304 172748702 252857055 61769912 261959594 976573277 690611097 54358822 849020278 670098517 734017117 602236354 850929931 653230451 281952607 445475734 269439774 666869484 540161637 862013499 840080374 821285348 657187058 284003227 918784544 647328298 973483732 711907432 650300048 424478897 292707633 776997531 936692905 521450262 477029320 874250765 52159901 510857432 600909912 381127488 961951284 957001782 418468507 276058319 186237444 819235079 773089166 562164917 974470976 205875227 639469543 855354056 702526181 407435771 290887778 427545838 159236024 430168793 439948649 651775368 882940918 443121014 902668266 608692544 614925435 745735834 959253770 231006756 651568825 661110471 438115319 757710077 743802588 490735897 748750150 148574644 684911927 715499511 22074722 163146997 345780962 77857766 76235769 451992259 493190276 894336479 334671611 479234013 342277118 536536508 105973123 501613425 116464667 92026641 229017046 826003061 335114253 263800467 758000866 125968692 598829211 563729626 9669252 137991091 468792330 733085433 817781557 716572308 953364976 468672466 167865106 61148973 761367105 603011085 567470037 257164131 679966771 389665090 13093383 765666439 13545822 888206677 330903872 398756269 990895028 271838099 910072061 319122422 155877159 660780879 883090881 772611644 194498503 856524158 108990873 139909581 471987712 492527751 60035743 379961941 211779288 447694343 848507325 510748249 390594734 4884851 954388922 109180904 607016315 824268976 300541524 493647138 171934535 639704050 710639910 504870492 236513272 428715441 610244925 713006482 912195389 652498204 216700263 494039369 431667398 773181411 894131399 680355432 499279856 261741971 508436542 171035450 937268273 115664458 1569069 520654988 98530180 848008302 166424413 814049948 489532877 162065325 449015591 68315483 240217829 155331659 819961893 217974545 317895346 794134153 393758186 604783308 723617037 722108587 831387258 544606044 178947172 328832563 912852748 867205082 127149155 102586483 23548758 136998060 895450773 112371502 834000791 678829800 989890919 847543313 694288581 84899820 510960961 863552410 964908000 305232241 550838398 527821943 997780597 249353228 456966709 810849253 265574218 36240360 225250116 576449342 827109630 633411014 967082550 220345103 816599849 502726205 510508480 586409048 187722702 552482282 417351464 267399714 99420419 333851214 738000648 855102963 570491826 775608158 864455429 961507070 181960216 198424611 854132783 456765390 247171415 878012688 858915314 261528380 794222778 207947286 641984448 650611659 907126118 182590786 968197712 38698103 436480912 739048425 540852741 979629507 682976997 914950581 152362739 3055644 71116370 313151454 858649568 633574091 747158098 653302964 254914871 204928745 31782514 227521995 236990916 259658497 574475293 521911599 60268319 352538163 414738661 334287942 820177783 171579532 552683926 398874253 141917294 687602064 193208488 867085566 871173275 815134888 759581314 949810177 91270919 836300063 939936002 100328251 326114536 489638250 923509821 748239382 348047460 176124711 702606442 59205514 876528520 486599792 614734526 133037738 394626445 715568176 53891177 157232631 734700928 443576531 715045866 22975125 753907772 497123400 1770708 985327611 822317766 960428686 758139688 386428233 434075338 85198195 433380632 379564891 149027477 250470505 301644653 156408922 139367120 88694681 208588099 71736707 649890558 47226189 615488923 342725151 336069062 780598030 916822900 824032610 626282711 777043026 183702024 214757475 113367143 151716345 421713127 296409990 998521952 447637531 379369851 216622834 208028598 213558902 196551421 507741815 348707016 542902165 976893934 17396586 711579707 247014146 6847552 801678564 313617940 683768232 907469974 321117439 587095651 215713598 391003922 956848431 479865490 510637109 707980888 485734849 172534932 254426291 447833127 384818053 661440810 894666221 591280898 963289611 439517607 371455520 775068597 116917603 923681360 407129753 27409928 241315005 565697762 863880163 154651103 829770797 5055339 81713115 302189051 793190149 25718759 70635239 368485638 503929817 872495037 885995004 770237661 801854837 960804211 746091996 383960256 869659318 662278116 160725429 959647389 632762735 700534756 144793711 536512512 440292040 652349922 348126665 2560197 701520582 159558745 567073616 240740652 463945326 236117962 408281872 794817955 761732406 465827533 533379804 495484761 243090645 989139829 449476041 523350748 348435085 990508920 898201769 179759789 87334373 5654412 181354781 913775557 520641618 716310682 403904367 587329217 535267663 632879540 314507606 565998653 247059806 474065647 240241411 464392374 687410846 762221848 921672020 289825908 968002108 854152246 280871324 791309528 638223575 192258627 120710535 620710487 413559657 230947224 466039638 861915098 610366859 675356683 178273487 837857546 486634269 243844625 301688705 29390590 740029366 302630805 58488342 900489985 246022909 863449 235727784 713509661 627417830 582934868 735703611 630130939 2833358 718248427 326568268 712105575 934189248 709215866 84669866 793676191 721927516 519086504 887720085 270292550 703969168 398382892 584526007 546955140 284414637 629814432 528643049 260101020 87666972 842434800 239089741 376440561 441239099 598488241 797482127 668153635 832540770 191221087 272157681 519196026 290495235 753037432 236939782 525693651 781382865 903432243 92278860 686057989 512344708 935507735 131894160 598047625 206890976 495907206 776041724 86113612 279402980 565813712 671693649 111817766 255269902 609144182 6579287 861321094 552131163 137782871 258502121 786647382 213953817 736283839 908010296 205379738 258690332 435866501 119811037 331294344 291699121 563606488 945461803 584293444 601919634 190753058 96901552 566287995 549546389 997631989 265822391 621782662 296230838 856512913 977755399 821610246 749320549 174095432 89750055 747475073 610528109 375316798 722796904 67725523 129850990 670637555 714810036 583074242 712515468 782617734 621232839 2351321 993500655 822227386 702732695 847669546 681033345 109453246 906305056 977634716 786583570 718923206 936259315 231277036 243961537 786258409 985468919 568859387 461154783 446432726 276979806 140450627 935810430 127078152 928692279 63799228 624328561 93065699 447600711 854634508 677879461 508066487 684569481 505708348 260548701 336965401 871509478 558907009 748002927 54655599 846227016 347934018 67123247 307025440 202924625 125189748 871404529 286325429 73664164 919814114 773613205 36758765 370741745 369899327 810862168 491185802 25466350 48355445 326358936 656229922 429024762 792165868 221369945 146008541 578817028 330511923 487683452 349986666 730486023 265009017 869361548 638617012 748110599 520716648 170175946 757109208 474332011 525015512 370626129 46607621 692412678 435586393 740650593 937730096 43977648 156097916 706578187 121879419 919814208 341602863 952378853 992820248 516609577 810761576 734362970 595156995 133911387 807312438 188957327 541248112 172959006 567823475 152205277 417083129 390662257 432072832 836714199 136952244 808340968 928652971 548234140 503716901 524181199 545393943 841873832 492612724 367763715 549201534 905886973 578353191 715621532 197768037 685912965 779706310 516525498 758830226 556956606 925502338 392782036 823031957 545524147 185253697 700513696 316235623 870879154 975309469 931894296 357365315 877231851 744965608 262133645 434364305 826431113 13973051 292301053 827072414 5480602 262204268 830905302 681549366 698910193 276800887 886469987 226303799 225330341 652684365 663480049 523416403 798525210 225314721 574922064 918892790 475986439 681047061 954127476 84818782 204596676 666324515 575407069 994100143 130816175 351277702 776057483 434187256 768303287 907755875 658072412 611177841 55248060 859785678 245209082 814621442 163058896 924525001 299049761 709212228 135386019 953345761 21702833 600696220 201461993 793175247 846363805 862020150 993552190 250649578 944596543 760838170 800824737 897681222 82463332 728694095 247083214 340206929 328880603 546784123 339005073 20585716 552196506 797932737 311336000 241616136 874665104 458287339 457016222 428946385 805959576 844823197 218973175 719437364 122394798 739456095 787032273 711677357 281403234 20092359 863400836 698500898 691637616 167103013 523428288 749454510 859787166 683763223 822651426 425090167 437504657 118314921 747181251 50695667 894706306 818756706 778419121 714632222 169651650 641512654 327691626 871685687 508162279 585781778 837938445 326758225 740015333 855864001 159216930 662501855 960751828 411571967 927034086 592536294 69576744 264382423 241272740 964961508 210908676 90411521 855744268 149751946 373974754 295848313 809930849 913359822 334119423 729050921 94955563 838471663 183098337 823174247 483495738 190689942 287068601 238363354 461660462 422103980 635387056 249233795 421717080 443208841 57360240 408000072 527866456 931350586 599778898 327071094 365524138 385987943 889603261 747962732 762178580 572316783 445770845 601816182 461125041 246305330 553964379 117544153 486226372 225853426 869800039 289004886 514673240 370108668 283185659 726335720 700492766 736670555 874966830 116186962 628761807 142485966 357292641 143840085 190614607 666704597 211786340 414014529 285821854 595612010 544280001 906979134 769285451 682880615 151623114 641073178 824241059 261304975 233625765 826363997 151005670 76152977 545345339 204721402 78847197 229734482 62559806 315941583 147541965 5302765 983797992 262147304 226459268 129313628 607480827 987307157 529216758 418371935 684317926 298742838 321896065 252522606 219393477 731208920 498806521 308378176 825891756 365051939 308110779 436487986 626089089 28114167 981391663 477412782 314438361 728855454 288025925 730067852 716741150 325287872 189124028 579043588 397694433 281327805 477924390 407960640 363762804 210148401 751395187 442873856 158470642 530995870 482387070 213265451 236573733 80529975 19931212 516559773 451367111 651742802 288606652 686094535 508797220 358381555 663382628 832359464 653936500 285405493 653893378 284105221 919449317 116885532 464128223 980367839 225750515 182394231 279890126 797947631 358285917 570632905 675013844 620742238 15029166 965332205 888031727 328386749 970989111 40633615 773729358 781729413 680877170 241294430 494429754 325960020 632395715 30110616 815537577 778683632 908040076 694011498 386991426 130609323 311582764 236825003 349772067 813938910 70160735 172109736 715120948 256041377 8962638 971581281 763496518 465643231 708004787 943838112 589414501 370332399 339618316 238331713 155257071 774808650 326714578 367253549 527702362 278860864 154911352 664785029 312625555 10547230 155448165 442884879 458247123 966322636 174132635 289571157 569030846 414476450 994688287 664705439 12457510 914518045 429925631 611428722 351904345 627395553 121477713 76636142 128752289 272513236 392494602 726664183 785048110 855170852 620854019 424603869 440340412 481550723 735048489 274825917 755217791 303042944 502742331 520765235 562898042 129675050 449594315 387045626 792408212 252935579 60405264 863185883 77386477 877234072 776102898 334024563 658552787 350824037 250021376 152665811 633204715 485025194 234718042 663515991 493486094 210434480 531780009 204539568 238344138 165378368 467469885 818533496 811242999 376062514 653479465 797546632 853005793 368937817 714757444 256830861 445944540 110967576 656450402 389061733 452525442 119276385 339719996 316539824 766688862 214259684 48166712 90897430 714834317 164697070 159917886 573948205 417535996 957172875 68010623 161173202 101001758 367921049 449030093 408808419 27690704 771611391 694928044 805444920 959494620 703733378 698385455 241658618 280803587 35804086 756118010 140005933 979978376 266013762 445927472 654377704 61852970 887887734 423226759 407173084 373730633 918711489 411651954 210431090 768673689 97467426 842134022 527443672 679489361 473963686 569573666 207820781 775476491 293739709 315022887 719443543 78405494 760734072 777979962 73734186 631166280 603286984 845551879 327996660 151980360 565245178 522998969 809337021 790566685 125735609 910165493 803444852 289618577 16226759 499575055 750252153 211096987 426460241 179702328 843347312 314613262 260095576 715434369 514509170 142235722 955511272 245575546 424702193 565195397 583648978 781962274 388284588 950314663 223710957 631860066 944641205 125397531 664771552 435379922 573336243 111343685 316296886 346688988 308624717 548163795 144639307 32529131 192882610 332162795 709825768 781297068 467356301 973074548 583380072 175742670 398788979 131373747 413856044 224882476 518098261 998893268 306441078 875554356 606946995 472907902 997947673 858318701 570844620 125924280 108966949 473372898 426576864 841946123 394083541 282668341 413098410 776196862 90344164 236753213 743499743 743829809 747930470 782918637 132319814 860183864 314280486 812248778 547433928 70134108 118937256 515594514 672479813 521921054 619685418 748108581 618012149 287402689 306611764 924889831 383989934 734668544 801533966 722514000 45231652 425822223 49551763 829148367 796905504 385289576 256256509 621444709 567456423 894009667 187092461 831711467 623556391 424242493 720529942 411166766 513099789 987723273 292968673 377409402 304812024 112434811 827931031 537951031 473524384 67573866 517837735 68684607 352667469 699416687 353405905 89470041 330838386 22522081 344292013 222243105 602613739 78114365 829104965 324588497 629628779 845578625 182235467 364325671 123316139 349414994 592771552 814937343 489159038 909855453 714368283 406611046 397146046 194704534 814120369 400019026 248484160 364077525 97517165 67283271 991749094 662559044 242801998 49012648 50498505 10610226 668958194 449196325 816907898 396511997 48576770 869220274 88937620 218416944 769047279 117928535 234900524 644361960 757593420 907092956 605134770 917091250 348065270 128171283 350939589 562108419 707520851 177744711 813591988 337689799 625334531 30350567 544190604 398257698 216522797 948589405 915910426 125863648 259028468 747703704 341912965 270927209 872014148 894189616 529672684 629308699 284099614 567330476 337691985 874718935 568457665 360755221 665412394 638338606 724321060 228094863 610550093 89834372 483346638 302495042 270454554 107198733 186385050 878479 272761532 769005450 778303398 369139478 846524171 536638496 628789091 93388528 770476876 556948048 693249925 236435084 815676759 412949663 695428740 140436883 163342112 501466802 816223120 86483656 732223769 503659431 579305773 427461235 125458488 138790424 385092758 859665473 398422677 83046578 876808553 801319035 771858597 577108585 710716025 599841647 547517493 698981512 573757719 338268028 850504069 225227387 178865801 561626714 125907585 888602533 560670917 209739040 681113308 743041720 555323667 687937915 117835061 133645336 158821559 272566593 652221957 100762916 164878385 710928893 302755711 567648724 773391995 561507187 564576904 613909456 31224680 203836856 752598764 554980454 220209776 616011013 455456777 114700027 374240571 831215937 723637011 282509599 253522721 4836469 601431503 106573108 914155173 870154885 448241712 669491480 735226491 927549619 97914539 298398068 111363791 258725186 932061535 324340850 835033355 233239185 134332940 949374505 135823297 778372886 973111644 241500728 478590541 321961091 635717893 842804992 71909484 867931623 921431835 309005900 797045599 910127895 228310714 912286139 693089447 212452990 412675818 905619371 909361337 390859233 707372789 41465507 890358506 991392639 139128806 958099934 604206734 212574104 976503279 754405152 122109788 795140725 863412403 412605114 507313445 367152248 803729259 505203050 262809607 626314573 27600221 252782306 50800360 905838348 179942766 908961250 56657280 237008311 443907881 174910617 866259482 677070101 85817028 439112549 224304864 923341308 257787890 830112353 44988347 467458323 677585500 719436917 532980791 554988856 857879290 691404404 740000013 441591430 801395046 192002885 720363501 677105933 865692628 217687763 666727754 599873428 33638241 369706849 742390452 935551812 337964146 600944470 492597548 654967015 436268431 642178934 788630014 908244425 147005486 162249427 85699367 925186952 616596086 343906517 672875688 260629964 212588290 666574810 112215418 872231779 366489273 693987557 217262012 663305305 783265669 335284719 835457293 69976863 754350856 477278058 432340665 661419475 108907823 987723084 498405235 524856545 917829849 570885748 507034939 100072938 436466514 165837279 991263845 143360869 73538619 254994976 472026033 642401475 961643063 354215411 692297435 320017372 355867255 205423159 924814260 18022049 564499215 196032039 677133475 488552213 153284114 941406757 776214326 495793175 897694936 430905838 381100543 907316243 507058053 703794332 171179916 167480687 4139648 230038670 460026597 912190279 804424874 319757970 826555954 156020371 512218070 943670605 593147661 616762531 400634264 653223016 402819920 276358787 643310653 597910635 671382006 48807919 663276091 336792190 409917771 971973015 8900969 656190951 948334783 542067082 887777660 760101711 166855117 341295688 196827581 841681005 733845454 325538202 110664591 226355849 646440864 445728668 781740049 146680498 654868057 734641171 560900367 710946598 96992259 17309317 335711556 167086027 194193374 976833371 771816328 167363338 179024109 657541122 426528258 56258737 797809262 200506268 399231410 589983928 381377026 695049146 52081493 659493003 220128120 125920034 255952361 878791688 613505316 738849923 242204524 61546474 581143147 561590408 568065626 425345451 794854093 108272072 403460262 877155886 547370466 566561961 161909259 106253529 270168796 917093077 916612493 398918977 373883972 299841376 227344197 98859105 652348139 510943605 736346682 335704794 246252365 323042272 489908297 645323498 108238277 637917628 169338165 581966440 912846234 361795201 14973431 256136800 605599859 392043833 706666220 547416493 229174909 518337509 236168683 146690329 317012078 383311485 75027999 966710970 388787731 25463849 868997419 79437418 780362275 107762403 321577104 917675323 521949835 740835330 191702586 495423681 607275617 87151598 514838933 153444064 817646126 140335466 280288933 639562434 338713536 754688173 519126304 481036846 311918046 844163210 897453119 468998718 90978399 909230899 46013605 217986641 265190656 927925848 113055453 495717804 89316844 204237576 183273043 997200167 804620121 418452999 460477525 668199165 681561061 690508646 177754577 478566299 511957570 7479394 803171420 496067498 239325198 340616574 81374760 78682643 557301201 74347350 914509349 19456016 681237248 309488469 542566371 881725445 670325565 202780913 84793547 866938800 291260867 348586523 204962031 443371194 774391900 590991853 937631329 50425931 296471495 281687249 143568740 982139322 319210403 185496424 288317323 678044448 179163030 672936845 863518236 905148249 109719599 351438482 985083353 991425769 515229820 532213003 732285625 646777087 824303813 41484034 572421181 558568186 725952523 822407201 132082181 649450146 601733125 237372847 182862218 786919250 707861177 764108410 462705393 450791597 959395086 157280394 140237022 581115224 848727077 503480487 642264574 898955449 246828041 97268528 500892939 45251127 425728158 523928542 427022880 483573525 995733906 922938859 110521097 756395238 785717627 217514246 951398991 839873275 116225897 626181799 963925037 262861054 974697796 141749684 715814562 455048609 493085351 296157631 729760462 162332739 396254695 513786838 195578362 497955824 863052040 590467114 642538725 932872532 569144775 744875972 434729298 169556810 831667870 926613435 429734964 303984202 140229649 366032918 615595376 887873487 691496298 269362248 826249867 936816387 198943425 462925496 308745081 95230069 90882747 332225674 267467472 480033186 111624585 536748572 447963706 125047646 752985446 386960653 169414942 226511015 36804216 797229733 119307210 525478233 819724519 567480606 265234865 691777971 363076981 620875328 592903041 358976790 64253397 738167296 895906224 33378792 334648970 378321141 746995383 816651711 119599167 777261765 79807688 341720681 241960669 396036363 36181751 806081861 291384464 148418150 378407774 694460921 548002352 133552302 265097306 833001155 549729085 546053745 14868045 621284893 242425790 228333046 93284712 652552507 433675506 825979229 53232504 543991337 284315966 868227442 945129911 693163149 782007412 325445010 523374784 320996431 31122600 979322237 465514807 421872790 297039571 806632303 806800032 496415342 679997720 561212936 120494674 254400310 911749118 544283258 202209379 906456300 345097719 223795528 43049168 681968300 631020322 451295729 200218259 75440357 888411593 143468570 997549561 778763870 911833197 988394604 767155638 534680674 830844929 175416596 6734094 350909508 781501170 647433890 498206278 37480963 459765429 570641490 710331660 605578162 875212184 143032409 896358339 304444251 668527776 994604128 135806467 679546509 593312129 304247031 603546066 925379878 337333604 374601098 613433127 674554667 857126518 205021495 560226063 988703959 822965836 154091782 275078406 411534461 161453087 452978434 33686761 491308418 692242391 252494545 83053340 147799435 528250923 395342306 318443648 733080748 306842647 234372260 826599109 541378510 310227849 398338608 724828328 828566399 565824487 146728709 171985513 644357635 327607262 756239771 929056507 4084563 977625998 138955387 310671739 573825503 1491675 598438945 612554995 624060829 727243410 181644536 466783794 10848367 437882062 468725744 873510727 864026583 362416095 76287130 561078634 700161338 621448273 911875204 82450248 829855760 749753218 616621693 399744999 227346213 134673219 413895508 25326324 836738866 419243567 923160895 93162657 981160308 622637057 165797127 72483937 797899628 778238862 139823244 315827327 270694761 557028017 873899587 201559227 172287440 559532073 126586232 432989794 540463082 231457159 905130835 450180522 81766403 442374862 297746279 38154775 333035718 113243586 405741113 724322286 956639375 455111519 511960014 747806095 939316637 700271585 169009440 624579690 974615040 674745552 466262040 226379285 686389795 912628671 584641953 329860594 374400710 966588590 558444472 135769571 89041852 476332407 827867864 806313606 281004208 34912675 495173991 417898537 374939213 778679300 924778681 503894823 348789028 330780416 988464495 286563163 294515823 745494994 794992065 949842996 529180542 754538174 119056883 231991536 356909522 189167385 571665707 154960622 481184831 879835313 988613556 235940495 795148401 708862832 409815046 559849324 612228991 331796155 414043564 852605982 387541353 99082263 145402316 71419755 704037543 136829062 766292120 81426955 348387959 591754760 41931934 221362066 508367124 688663009 577934833 128084240 122789953 369401952 421954444 420629939 496143514 417884712 905349212 68441133 932317085 471331057 754442888 251789593 308019814 612765281 901672245 129660060 940795568 988486607 141891967 669296720 370926314 872926999 899421904 939525670 300651771 846437730 971070564 710812339 14764894 927205324 1180460 648373891 666044081 648314629 365137711 545836254 272869640 217659532 376292333 549391088 164555440 395600570 962831602 599713332 505686756 516905904 652391563 243919978 176541300 355357308 469707902 225194666 422970207 686220869 641915622 825549502 588955188 466861762 278762757 831416391 760438233 968112250 326978327 107304803 161009792 107557959 507214756 574204524 971888376 783421632 351177965 342360478 181466548 478392905 823974343 431201765 151094346 743734716 81520875 218093020 879269104 38799449 105515991 830716604 680036345 532046732 163613461 853406969 18553211 323134261 127319867 863090189 1247129 62687512 219150054 125471136 871890700 862984746 68529607 947384174 36251552 838880319 695858782 543185063 992128942 652531896 41040187 560678568 200781448 780988345 779305112 662409636 487304182 370486754 54928404 669374539 113985292 34713646 825749249 801760402 308448309 460698067 794084496 124731238 830382441 737234265 595148075 995891365 314228395 324062156 995200590 419303192 376912648 720552242 685657620 252575118 680422534 835989456 650874945 18575542 78949492 9252293 248836436 510114032 882918417 530743630 850556031 763022387 258271180 519072159 865744205 520577318 195013060 577468236 528531659 589732088 858431740 639586630 747330682 729778863 537950834 110391601 202341105 126351152 674736342 306204823 34188455 183114495 877090446 235771782 464510946 857369252 23126378 960098816 725657392 204610998 972274597 623709608 655150601 778364555 47626341 610685850 508942128 406292595 466978386 329223604 993872319 268193323 300389667 322618372 242216532 323524 205146771 153333502 762863940 889440956 596361773 442089697 971056146 605168014 400098979 510049650 852417022 770605963 971792879 851858745 915801048 731465019 577997317 17459278 700929484 474989257 404060285 543349267 423384640 883169753 491319556 139708521 962870518 788164077 300815162 388579156 745212723 656500899 977638455 920412969 681235783 766245285 359180964 882437319 865930483 386266511 907486888 836954248 631971756 566450528 239602983 383808693 897126896 90778530 237601862 85928163 280108231 323474356 521019419 668697975 723505893 621829058 923545618 903758245 645299083 976263687 243330708 33918724 965061959 284171886 227620599 143598521 647988393 308149171 607380960 859932137 710933665 154862980 26420422 116677280 649688499 292112087 439845529 543248054 112802004 475581530 682271853 957910024 53212818 759693744 595751706 216163121 768236818 529315336 396741107 371663331 514949093 28571022 54643018 798126354 291646679 166908809 523642589 211588431 336906947 420061461 901077568 291627647 50043042 863330251 407938442 486158266 987108082 479050107 438483553 858426697 771103779 652200598 433359462 236402498 268414455 548576432 207010017 132037832 156087026 511238862 331020687 448360422 459478770 18923263 462828949 644165034 504226245 573552027 895761577 311620171 698828185 713737807 813569941 7889320 659002205 289260139 967279190 505739945 141406076 450810288 697974485 876420815 288657075 503254094 58763549 84358304 54545386 235959241 636442567 83252340 161142153 267970613 592378288 192081622 725459340 669308338 205549855 158893602 317130149 757279007 874216499 791422822 306240159 853914375 803920567 457777742 393133916 634751085 4959108 844968537 566325451 209747776 40626543 10070391 343598230 409232469 123854017 29691845 373381898 731125283 837724313 902752072 903800769 122473431 324059486 853555073 731311060 43917923 440531206 637190410 184550209 155713744 71360727 174854760 663666113 813289165 421999535 815962622 45269753 134515265 774458598 582327549 861605540 463737559 428058447 874382500 351912762 930886494 442417712 704898798 465952627 635183110 813973597 80320431 332943493 575434185 751840946 132821357 363510012 71359876 95257772 234122663 534906451 972974290 474593120 262501737 308028864 884134397 83545919 633353802 914008381 961694246 779639021 507040041 311754549 23927179 901033201 993190636 716026596 145757113 769942701 727480132 351617402 820876963 411616564 847940757 166274919 986808831 733362943 976793705 482323150 241569654 92634690 69144033 490059821 355254782 685445430 748372881 96143331 83257145 967812519 954118673 251841430 967412182 852241349 923553825 418953614 885479405 113860384 669833679 865731 756568568 965847019 901936629 538007839 262207627 851745772 969147031 45542516 558293607 662132352 341002207 10324301 867387783 828827268 975165654 475164522 287345432 593104170 544001349 55065579 539548486 454116660 487576602 770409352 604145753 402215323 746682363 893619064 886790396 356191837 124407767 490004231 771462731 459782654 794820103 249036740 388663194 140731018 412703966 467465116 221087837 238507398 979413690 795738668 492990345 771005349 965975974 128891842 12523624 38489565 818560319 735660615 741159419 795666121 724235825 444204813 91074426 146116950 576755695 738416662 443776569 955938926 893579990 929816436 441134792 158136508 245765590 164997043 672885339 602374417 943739476 661659836 913680799 247472618 403743927 850241857 554019873 957577526 972795360 24997937 464651916 854285175 372892178 243096123 654104669 586243594 226703295 540831398 535801183 790128452 512100527 58919598 759781513 762805430 282865539 69250837 651259850 642699029 670526821 111433596 39239539 421396134 98885374 908287522 621782776 104020022 442007206 22799092 787545819 963284677 39221240 969171123 306937975 555544265 63715715 9379710 262899467 809584766 379673353 89397735 205837201 17132451 354976641 444305884 452581010 646361604 897891664 305743971 554450369 403101996 729800670 135800456 351070942 786755164 189409959 264848629 769450702 927021464 242749897 956215260 693166237 512329714 547658679 898758672 153520312 224933857 660926870 232616121 784323501 270662504 361563718 274330632 840574664 385630674 262638871 677621151 661921336 381462840 642772405 355460825 560279255 723474628 148040646 466673366 742336034 362810110 934495205 484211059 923287039 16170141 86810403 970383489 474032809 52284146 392159071 716627717 413713438 816998244 673206444 361224455 665407653 100924411 901619780 895442232 59804482 904626216 560643481 544662632 27497364 590767375 327432472 930886922 331964170 568009504 904633277 279974478 420517006 755923968 463400279 742734137 243035036 318280702 292617592 349292263 610422815 383979420 173898409 219693745 702892753 27617884 962448704 67816668 839997892 406423570 592050596 722699927 939147903 58815609 954640004 134762926 715614134 203834384 783477649 443685306 382260535 2702317 806022642 430323831 981802602 866604762 8136922 27765745 734294416 991145252 500505767 562227152 248841237 736901816 433199830 530721211 722250602 110808001 976501116 856632768 26982253 83825920 190436701 70967989 437058221 282351353 189732840 748540676 81863669 905291200 698191933 651075485 142303158 385106254 41529497 186865071 263280029 677926334 47079550 892772963 680757007 713523848 853438741 818843701 513514983 90152041 849283924 936322681 449179319 977546448 296145070 749768110 870610297 432641484 956927927 790382787 933697261 694333021 788856102 561235647 958950293 660545475 76835443 767847198 433312062 115682537 201569132 673726657 975204459 426274438 356764771 707672434 275040987 781330254 523478819 32204298 492947794 773186634 621431278 838882382 103104019 147550292 124718156 355002463 520722353 197537888 600604214 415979847 446272181 989959664 6579593 946065603 265152957 780402535 8262042 692581215 653577886 26423871 499341122 304845529 311214940 522347638 824479057 914032573 945137522 958985873 808063375 342240595 648433570 620421646 864768191 386144384 337443009 216089289 129935472 862157341 702110006 966235052 203786640 301207968 21619890 335063481 468053973 38841984 549082939 863002929 623017830 10658744 299896646 653204207 793988424 584993712 595486040 332983199 706812611 484818597 607655609 707653065 348144028 105147932 36885083 410289641 842490054 428144659 510320035 200669253 419244973 390245140 181168164 127546047 187486005 943610342 464694200 645375922 549692046 244862217 278323415 75416555 164172116 250866121 374594505 338854600 10190943 897424382 654692115 567336092 878700220 439429868 22414598 642626037 966050209 349841528 741121288 385711917 878387206 722499168 256590494 886996446 675233526 824175907 691922325 454429798 372618512 184199372 482041412 564236665 759368091 114542954 22920314 834100571 802557452 116635104 849786150 47360766 398832854 866671283 758197402 26007037 323464481 788990263 631170999 494218892 79321323 775053785 32355260 463480578 425013424 854105214 336556792 353065207 360672577 703087482 162278280 450059413 440716882 136860650 450803729 827406599 796642963 747916654 977767472 436799986 922931272 834585504 797801922 533800030 515597521 514692387 570203238 253761680 238506864 518025667 655306541 897591011 95425376 42458358 388869754 248335183 811459380 298312254 533627884 263467847 14341056 85454015 796747853 364444457 546539145 684415719 232413443 284441644 542443486 644333431 113970538 273000890 37716889 53347234 999231107 35601157 770165191 833738052 472117948 981381735 174091593 678996735 399009819 105383273 833223687 17525746 261714930 904478910 296780170 402174855 242461176 192874871 574424406 565296499 199733471 533928234 846791399 558516353 517590211 907230372 643441975 10967385 609572127 506453893 335509663 174197184 954774153 75642774 980078770 664564163 629236844 719711759 792309704 634282762 217146908 50373126 390309129 241360427 486052486 587155931 973734560 464571607 622207000 675471933 472482233 213444567 616950393 866389936 246113241 882305948 129788036 63188337 878822796 665249186 748625938 490968045 508839241 959191592 447109633 302663390 249444076 312412026 300985197 33509347 717801241 316249463 53896050 274776013 930366391 857306074 249211581 6661035 746265559 778303506 890995452 613393268 732512427 534593784 632798340 218513510 580593295 977114481 511611266 379228800 572577334 11712403 98143134 697737622 973481757 601877598 193116259 220132141 975195639 999096375 977202893 837002308 319043861 364935107 425062100 695604696 171040409 30187627 663033751 5995145 753550506 628587291 171801267 785338219 195500747 174624660 340314257 907205022 505686291 897424071 295287007 871820032 811723242 900213825 286779566 861970897 67094914 446820244 198604247 528309689 799286802 368369453 504417768 117761480 351133951 352277666 622157806 827359981 871163028 878465658 682364274 403489905 13860414 304308814 180858207 847416185 681449002 18710349 305131114 756844355 83288562 238041867 92029087 700137251 102166874 145717677 169499825 999419498 689089058 233680744 414233836 755290898 107477861 870620570 46224878 251496749 636648861 518571069 257299383 826413149 549945654 716856589 476132620 756481619 279569089 244715265 423338456 37066462 356672031 977404014 610865537 963010607 260685560 555944523 912565071 124267968 595521320 963185040 64475977 332291543 205412612 153947216 327549334 598117278 252249897 280820189 112925795 338071718 158392709 585962763 276493756 573290216 312562743 824310928 661855153 32492428 229454565 42454482 775450433 851264014 369844173 234706460 907902696 729754679 566646344 694959863 790527748 121365598 453018426 896962345 898716049 556538295 156452116 332433375 701069035 943933714 613196512 970935540 66955698 257999010 359537251 185997165 704749799 386648767 353001581 548630364 388403253 962385200 78651933 915743769 455864541 83915767 649360659 686571727 440064240 840051583 581709833 751922598 866396274 741681824 68844957 315299158 113339953 39211761 389368847 992383331 52206665 693984963 690335882 643307059 739189441 685809026 217049492 462528446 722958044 917415334 87950112 256261785 447950925 603986862 864911718 886686078 224686076 709000682 759714246 878291006 604179268 506687239 706223197 647530379 374997234 818374608 868050553 967604514 557785874 619307371 173555818 169730660 744599727 717952787 892269788 789663064 187675149 522212337 567325047 394166403 973097660 14622688 757468840 614414898 465339352 211167770 300563263 480787922 929057380 540807985 285046425 944629569 810962401 272635309 122054345 329694918 138647318 222490787 531282472 210934488 797660569 508070812 100821535 779711562 466330013 230033930 154655800 878258401 50055323 850494688 144620942 90167521 9078878 314336605 539291084 214750057 206685187 386449320 17170479 116405722 110859177 737848825 160635854 65225201 328105611 449639699 761247811 569415496 205904160 835818445 325052508 345988398 765819782 895167267 749347275 944891311 848617176 751194915 394332140 174406032 171645831 657135028 217100327 154217784 104344611 6600793 554230683 294969306 4437513 182630405 24241239 639920427 713900349 819261884 770677148 265841030 493829509 958509439 953752529 121909152 931814530 246211739 180403047 186322943 890218702 106190696 611771943 220089439 397967422 746078653 863884894 989443856 503455326 254199143 288727117 915379987 52266512 703453048 676948339 297643230 55100318 612858110 476946109 145930830 334686903 786509259 167244787 73826775 908709499 872808016 176743625 695913265 233631290 738284549 94847723 597952766 334926194 832077536 111880015 721052143 984169948 422709106 471501244 896720298 265124765 345987043 538978404 641056921 258415408 398041444 376373195 606656651 238252350 270989038 861062582 775605736 140467335 148339039 476565473 874111213 639600451 333911440 660441039 585605801 965964359 747146851 753150135 898907608 668963902 160867513 877935586 888152950 184330642 372622871 983419174 169334333 160368951 95442627 951594299 9273410 782488971 549128717 469113137 331709116 769810159 182283011 77082122 856793840 760960050 174727069 764666619 555355496 592024351 474767095 805781963 171594462 912301234 836129190 96970197 809652727 972993284 749173601 258212564 407153787 109462204 629159715 422563653 234368860 115216546 410139803 77438538 777908496 251402994 320984209 897257343 489115943 767133223 833868372 570678854 489129597 623569825 975726326 563096414 997899001 187529496 821737108 282371589 482860404 886921532 740504048 23614074 296368730 593963109 570983248 115654691 817924728 397830903 691476179 50696812 647883198 265699004 769312410 7988108 754714363 537674794 265026845 421083336 528417606 359463596 338080975 193934935 456138767 523577583 765028852 224708519 212178963 865677009 408377083 522500379 415484525 940216859 629872891 866449608 149634883 905742943 771006017 663302355 280279173 538226299 888919352 37551733 455485903 667102292 316289994 578067053 617846954 842525595 122043024 416832299 877825248 204295510 59848586 402978000 398038766 684396410 740527545 647963191 861260686 652032438 682136409 800794175 94263040 825775868 220311503 361553116 849615532 914100549 613832592 909780532 109755778 766131489 64782462 746682727 742187749 896436047 325828621 388510875 528819140 255126037 399182455 177726483 204347457 681786529 381187442 193506527 887917001 838115259 674138717 918796411 629798229 784464869 516486591 77014598 84722038 744688004 743802740 262139868 604211328 600634232 472638311 658313086 60904701 383396039 952310094 930195049 85829375 956436105 913286319 473714577 608564324 358692853 790869088 615051972 170557880 318579650 273091980 336773049 685233613 575942174 753279779 479929083 920231463 863452904 473963944 852991441 411240520 544128000 233090228 402954771 814698209 124318618 772056012 147990905 823446765 713491781 658256076 761965052 524507464 291094745 901612217 224124326 344051866 21727793 414198159 797697168 409243252 697270903 89105590 902072517 270579209 789467336 70065292 514607306 799143410 750309538 125794735 946140001 937961188 177398631 325912777 129454779 925619012 540330793 477029282 293326083 4573376 354707964 231641051 910443451 187666698 593447684 343461068 965199613 636818860 648033353 145043409 899019551 611541105 745043446 866775522 881738176 465188678 235387645 779545414 631995663 593463425 361583044 900200329 305044950 317718368 604492891 104587619 719281174 648361531 567417216 91783869 269691407 817764921 178196865 693431808 315609030 332782373 403890041 996184758 253547796 152044582 199738248 936026862 464455154 60030399 677195938 820360071 839694116 393808920 411894556 198191958 477050813 897197254 478830846 346605977 319402860 942960279 623579403 225118315 589797709 758465569 674047651 254829746 127206418 74728274 557293010 946187570 860408565 145229323 850799426 936063886 647288025 353092240 757096525 252110643 747130845 233278445 15442449 381671166 410472132 996840556 437958919 75997501 384414641 524815390 777238094 568370756 50477424 232880397 942197847 685979210 812234662 364163937 179323702 457700007 888039030 998561132 423301748 175852020 558920106 292171876 311964407 897423711 193522502 86173324 565242938 526830750 487650065 776935787 220266547 646196204 250438003 806764293 904179844 314378914 318583456 655548515 887669970 706845000 981986768 110613683 744352618 631434762 425225812 614466757 520090893 963833224 389645098 902052712 807839925 341621748 766457263 128848658 363802082 380721453 868407833 666129608 372345645 451933607 262998245 506026774 529958144 939173187 12335899 118882783 25228761 683967256 375475242 178889187 599870854 961136586 608663257 202220197 206125667 173936428 250711016 531747350 775705322 929239077 35958798 938490734 632049720 494153949 390028863 815226576 927409269 77490858 446651828 772413109 163914401 444268611 277367675 930563681 186372066 110819680 66528510 539641575 805265071 46958134 749704734 160647833 597405810 768408381 836577416 410551826 82558664 899080668 76931517 40063 219177144 3160997 474941213 252142051 562595236 461569718 562964920 843252768 66239549 396447228 135443991 34941119 125454349 731367619 91225668 432806872 338101420 515310336 199945226 848461089 865301237 605608703 240043951 342222615 522595326 116081913 786018365 146360645 32459951 573846492 350870956 446957038 141472331 751999921 8500596 276100399 551498200 422669326 903622328 322229792 749046254 671561574 281546192 59526843 586459636 837649340 445894441 55335517 494244314 871426656 621611967 163170988 337713286 103559309 93775853 72160356 33914663 978277930 788917406 808832198 427087075 437405132 175478503 392756840 844525176 976676012 483440039 682826386 812042986 466853711 982080989 866834048 609299400 740323765 211988357 850138627 996616852 98640704 505698792 156592617 927667023 675356871 252661130 803086413 927233927 264892223 180307539 371620223 750537446 246802391 620846175 320010957 173334744 703130184 843999133 617308624 184772113 322201436 394566755 307488166 215752119 835951516 947317805 293842552 606973805 865920083 666904003 753638557 839513937 863036507 501203407 630972523 463336323 409430535 493961990 988996297 390630562 619627706 331859926 657849883 974387967 223238220 218672299 202423019 479770608 743970723 741283475 802243410 548202447 622074766 16671656 390498609 379196395 77630169 746914273 241945584 707995237 436787440 375628420 410558801 472021254 326029187 891699522 905028840 470628608 134133443 372675397 683992604 752347213 625755082 395022583 774089615 193803284 462481103 807137159 876609410 924888153 907818913 839390452 550196099 367108262 463096241 397805440 468415211 276795094 715518041 986563093 808583971 903583257 773897878 578474338 781550763 233044172 57207055 932158478 37063667 686572299 20919568 457305270 503515439 919755077 331676482 425356263 198813381 671619513 59452636 946640185 547892005 591357238 575536885 132123992 526005805 969238762 211204222 542876746 467052348 13398968 90437945 15650404 176274810 82914823 275831889 886921362 499350234 76557212 757276954 761357710 959339818 538172859 576483540 737242794 458361831 124295265 739914652 903436596 859025157 484029485 271041442 150526912 114516869 483848015 709337044 223789681 935402904 167389482 143254542 63136394 885018804 674997211 46000134 709157878 275481828 313041605 65229041 629666787 22149695 203912175 512428960 721144546 186752831 748246921 565856867 791372506 323837820 863496836 605499392 318168142 905249332 631323901 143273217 905454854 632873996 458102483 128047050 1748988 759731966 65189590 756828395 502922322 252690036 201829421 739140661 682445015 675733908 745214616 49020789 331889834 52611549 813597108 290283972 811854595 895821864 702111168 391568435 467974117 628786522 353121126 103787944 688963640 49785774 973992212 704340116 664885157 448759814 81591377 42717130 264819561 23375439 138598538 779544116 980088847 661258357 443279543 100049313 49823859 749560339 286684059 992565385 839005246 745631446 300324425 375281513 925810732 610751379 61548418 916514476 221179570 686083493 6798598 652867841 458793588 72553556 81462658 835204997 880810197 53863863 767029457 454234037 390826430 50553704 754608693 538023855 442805539 6197154 966004501 169200060 943800055 832301780 102567799 253092029 933881700 808552736 53334346 515212480 906141818 656712218 490587601 613472854 900233182 382924587 689348673 720324133 371346344 342975502 382577376 839212906 392185109 690877347 113217043 206609833 214565964 313294391 2090647 743503138 813412407 775982831 565381403 908525454 789297945 30814303 974021180 693136689 442628860 51163113 63163047 19477508 475206180 872897442 789042212 687313701 816874826 673077093 144165249 414492077 17372815 495494391 718715446 332535561 984765650 167236254 35485086 540855931 83898760 122725594 985390823 131403217 813515433 255104481 130483955 829364869 23821978 27897041 460641747 647778754 10888520 853517864 708489103 748778952 429352310 732391105 606138067 898156091 486048628 112692520 561575358 719699445 56203597 529343622 656663546 895004400 729574885 628688566 304982664 336193998 669807890 929655560 803157334 639068914 680679603 752921787 142479389 446900671 759856446 154856682 822819196 204057254 494675802 223249412 989574949 969110355 401957966 563947837 196819 30466936 355933700 684059541 672001217 339242447 635963114 774015663 678740598 212622966 824369580 827427716 329752949 774993203 750536029 444509452 180447895 35385435 461269251 994005788 397119877 796830447 23521048 698251053 753779398 389221202 94562604 91977208 181527902 843719425 38392015 393008965 170942343 788390541 5012813 975008437 870041182 781193158 620170136 366331984 338542797 650301376 338366323 815463250 394124476 550403001 365162027 299425186 575091195 513174128 141305188 597685836 828923546 267371152 398447503 776374370 556477109 361123830 647182712 169015818 393188112 133609160 452296953 426821824 73288767 574574724 402161364 765412549 199665033 629127878 100162187 3274611 232615588 71814530 408336927 32420260 565300908 752456390 869690423 62386988 456138640 248503779 235071388 451879194 320670070 749435481 555007699 591588543 744344827 408236948 433121641 800662654 381805119 850541177 443628542 890736890 642737894 805872248 868991465 680341917 534579100 515247775 202823140 131124963 373302067 557369620 514387806 651741664 297085145 674771973 144494726 744994784 279020851 472176551 534719411 592842019 113061777 788762524 72634547 896773359 55839734 818503624 821764168 946004733 466354431 985425212 694341318 555772298 176554762 367427392 794557103 318616393 132061564 937792054 924971267 227253565 702769777 241339195 202093495 53627243 132657042 685823215 360241950 955536082 290925731 199354310 643505 35541285 61194698 19150850 35532417 947566683 90714015 711719253 854197495 751853034 864090500 549154071 745066295 219223847 593208122 134391287 371384233 133688238 779338443 263507827 462712941 612723631 70203704 912267003 371123993 230470875 911174932 961405132 759818338 173796378 553128578 556532554 708502049 803192112 227046872 586751948 527377438 5485087 163091782 206350849 290882548 523387535 454460842 910103705 829719527 524133430 58299445 985560478 965996789 320623869 71833312 345250700 191006085 289784053 167108340 538404306 370055481 257158250 153232666 57013754 128705295 833691911 70882233 899038104 432591744 900033055 941980716 319764279 132829427 572441662 472747660 971500808 185179473 126794087 405912298 749026716 438167630 209351090 294381709 237412946 1980068 57603262 231401106 998294199 70560490 164708392 337655410 688548253 349380439 917564132 971170633 391148607 523780540 986601846 378756509 424371879 620610793 629130925 129557070 797196924 558683854 623024628 382343013 893734197 25037123 694226366 616489795 172716215 12458752 943537133 895956863 802933569 432082024 472544810 60378637 74319022 284331709 864489764 890340148 8540754 842481644 938492249 983983788 373370778 363434239 114017437 431980729 659932727 284696919 154182955 443110764 135945520 68250267 566711502 877956261 403287410 123347273 840530605 619554060 824498068 480848128 846123194 516071781 692083532 584059873 549526584 25799004 288178323 586729274 599954586 750598913 195186950 279531802 533983615 378305890 110320528 306122342 106962312 75088683 194263253 161015175 133153344 580916983 975893693 853933830 692938775 112294875 76709337 466741391 161517250 4204115 717284829 88372498 863432310 704336421 21182544 603961268 398279273 967615889 640192451 682022032 136892517 684323750 822115442 539992857 984445694 143760978 263843425 535489665 630111431 21269350 866992951 632335739 695229812 24044503 227117262 816928891 260857530 306352962 746472982 755566660 913796833 830260297 150245717 897736775 898621671 404627940 720381064 985385090 783181019 824220421 503552174 708805326 832372517 132901861 947725320 905912602 88425100 574815226 643291874 696675321 896903982 215009789 244539137 364768312 311704521 128789396 299709422 827165884 254111416 901180540 655044765 675422620 212798808 50216610 410599685 464288351 407855637 93847511 114571331 218109996 951357291 824226255 704659165 137144899 270742492 415839028 333350776 521266503 805378574 373269700 531222770 872416295 770795431 83380523 863535901 713312581 907674501 599568682 493040942 557612516 511912778 463143857 423693983 844596872 317289180 934364239 630494661 29855552 593503895 26869510 955845069 377325065 857181627 974196727 995019807 138963446 939698194 191364884 24204824 902417870 769532084 956389654 574799513 167526020 791270720 863826354 76352175 100542121 966825333 484412960 36689080 218328724 341381351 660158056 632281730 563736352 256398334 571057159 637561382 37517879 972830907 941325769 552181753 583030981 958409448 741081383 699438274 187935546 26450795 109176683 166092699 597646009 789941021 205771759 75835965 811746446 641196309 123492335 11635775 910710995 582008493 273552649 238508450 763862900 530759466 828528962 629491122 461157852 167252339 802838424 719196909 196727744 27989976 460318418 4640839 785117197 21456114 273899294 978901667 520855477 209392671 769212265 235547933 892869936 544835829 811109346 35955763 214310521 507101051 672329643 382045874 342332694 159501100 481321339 535441171 472104226 183704556 789828108 750403329 117249749 93844881 561739059 185593285 176906821 853994648 990836338 170363783 269868716 96010825 611930675 348156917 644355913 173659268 279147274 623618515 758557794 733628211 31461248 327037902 70316121 761956675 651076798 698599653 270334410 323869850 785917309 239407762 575626582 582549320 308532508 622987643 73717102 842211163 101166757 569845099 811501989 160634423 566918238 681882402 397409174 863423747 511822882 515491554 315008512 804270349 467384934 311635672 862847000 491796454 553964768 911170257 146224743 436486217 814353651 521420703 865134401 683170201 591967154 236262983 669963228 757868204 401407970 501217315 836004996 880723075 906449293 360305352 72036951 259488045 215292149 570745446 979332064 3178216 59178808 441102988 802597334 831148387 211803472 821304234 852952647 114051759 735633401 118320483 427514537 715706109 715841807 157209375 384021795 934742798 27547362 165041757 460601839 3696121 846374589 951354877 720229183 644776446 247826119 39846285 813181572 247783567 947765295 380732984 310410947 163563084 527388180 878549473 436688492 860886965 385078945 536480781 806862567 635045554 346023241 412671122 164211813 985262962 323515200 398918217 307329533 56571575 679776455 137596545 933416051 572321809 464642100 247229068 202088258 677070918 803809576 402902091 479919141 791539709 48506078 251064140 695395265 816113521 273708425 475066615 152295514 801141635 435904658 141998298 274524220 892558228 202571678 387304105 678736421 900430108 691951863 75985293 125137628 74147110 693761717 834595730 881613607 351150624 413423901 510594401 696691736 90462116 313414368 832592346 434353414 621425862 881805740 303202734 398250038 299709284 710342029 851456223 537655888 572669096 734258722 430296877 245573453 576999124 845769791 916642859 47703429 817987059 83286632 845779090 715821372 14466405 850689851 786308788 639040936 555549124 65940948 15748190 340548177 999005546 472983770 866910740 223959132 783436763 967614767 185506099 676290331 53594283 123413204 659140081 153691702 504392665 89017884 771860038 158822857 985014165 693637272 349723563 878904154 650218691 917497101 305314144 904432690 642463097 65782311 989677346 187442776 549387646 282040738 854552405 249397751 831592436 555610996 364424583 424019922 510333745 263395157 22006949 720306911 250404153 629494252 985905852 605270510 587380129 313331915 674023073 100554902 693017345 974854714 164460070 919704296 72016382 412330735 459276981 559237438 843488785 712411375 810876137 546123456 156529420 740521108 439003865 771387742 426887405 739507251 421789381 584120147 527715807 499706480 745899836 172414535 884368640 398625529 737767928 825797260 618268854 905779730 815558978 539960411 600657867 508992611 40806304 363350111 137343032 73848324 999809373 471908609 847242948 156322635 952359612 833509962 273992544 710440130 309590528 277803194 996873793 725442982 255661941 191969435 182034824 41949075 654204438 829647395 509238841 993998447 390025224 961779863 379372633 118804321 411651803 603308380 783235394 549949095 144959065 896733777 890483257 792057182 164841973 65982771 90278330 690256059 557624043 721048202 502419600 723126080 684793357 298827381 330966422 113078296 249247723 989328826 629806892 846992923 643809414 974373059 529952436 633839878 442181359 909395642 351035770 626441392 938408236 604880012 888384222 387177665 6143518 886077635 504224620 463223706 31110610 238329881 135460077 53417158 335708955 572452623 602549348 961271796 616952351 247981377 144590791 830076540 242630978 661973621 147565756 341504498 105944653 754984574 774058146 913063726 659966741 844638222 287982694 687024094 951318752 202356999 201076533 785483038 611125726 117209075 431927936 144790883 902666216 207429420 919962130 781993442 393161773 810168869 705812330 59095276 45174620 379107165 672529881 646672203 880769895 633506432 525538932 708863279 958030004 789399822 409784742 98718898 705983199 589678763 671528180 9857235 938884903 488491111 971685618 741259314 71907392 524393472 404116044 446612518 590494353 669009212 129116647 379919916 131374826 754516527 370356001 331556985 311213155 507414009 310707858 155944978 756077729 631479476 538766679 565876614 273920175 814199388 276962930 871307202 553890628 569974760 463919745 77494128 759803021 232728397 44473030 147202829 478546020 102944369 475296078 581802229 90814360 711648194 57942992 800176521 807507692 885090042 548872816 853689717 32464888 88266816 546287548 836847490 166365379 741291002 348418826 580049142 316446701 879357948 626051342 710165763 709560945 482178496 909405028 938271668 859940754 331727056 271594907 777676163 598575288 275230647 465889838 115152083 298723452 457890787 182422724 711835260 189504921 241453134 505725790 684230078 819880797 555360493 488934161 42900279 697905397 135730198 811477403 489128058 251297286 140274140 130512365 892536493 894975975 576954750 83925818 177075531 251394095 48143439 575471472 352211338 421494626 31797134 916780648 280564565 978436852 112270504 36818653 748976174 634527483 309717437 144997727 25845776 982825705 748510754 86130006 491296137 821688256 70806123 949288553 962185967 51604170 191208739 910259758 722447781 910445681 47312234 133294233 741927908 660187025 455749815 429434216 538319762 256762177 92449789 981641992 764681486 712290107 812134816 612896618 926325837 122604954 670775664 343299163 647728771 122632334 749069665 599353573 998247102 530496279 354891659 290461655 877798747 583829636 65061489 520156170 446388439 180574548 512663028 751108590 391081288 317707612 390041403 809592046 606449561 804789787 31793300 289822783 285749058 290595546 433172499 474587503 56098815 56338373 311956712 430892801 206418213 175613612 24842441 747093122 552237507 840314401 349474524 604331128 276475714 567375437 670993528 471148055 190743947 174526639 46307053 381749048 745157210 89710720 310692877 38994282 939220366 854915185 612809826 644835733 923481186 361588754 95199774 314486713 498097284 56307072 204688692 140651454 708129334 813602591 591748448 395907599 673688801 134621589 185344949 728800828 375565453 986818617 311219384 52337002 526136837 390272034 50916594 697367749 181999235 602791334 173963349 895308609 58993138 266446513 248291871 314874627 470711033 806784088 330809930 812720263 634618181 555972360 261176278 599834731 428296204 916094755 149276545 738462540 150412925 443130864 784685268 330676785 854604796 761540788 859906368 351538207 11234729 237367793 439942955 592030828 677041474 870344837 689629847 81444829 758312632 329587728 448760604 317104119 701501816 298068277 957470800 201705716 359111782 473659819 530376723 957225240 298829521 346268372 444242139 50606767 196238479 372212137 716543059 98105867 701767975 334337899 578008207 761262131 911140886 166511270 484923246 427556992 381371890 974006218 599441376 271828985 594666962 802295260 312701714 117535855 930564162 183103172 750301490 721671383 831114252 474543388 962098333 385850404 879329942 500678222 864824574 346830151 888365713 718136503 840079237 765023885 750592450 424995291 40521926 592095931 502971299 440220355 675696659 919586448 634859635 402830620 819507227 927668852 47904542 997549732 362227415 322136595 23750200 811563996 414184629 761008755 635579715 786154976 438032709 716207041 885005921 353365288 956703864 390084876 998243323 937517522 733925819 493876242 546953323 196088674 734118979 250251425 625257211 67484108 394287330 64965637 565477443 219380501 364566524 424324951 549841103 188485143 421791483 752880085 819145688 600407457 225409358 320740385 505719978 259336968 72606930 935157344 500100256 375780063 917749579 610390140 689083389 605240236 391400391 962348667 856840219 839998198 407514629 413610473 996252709 221691800 965483823 87640581 294738498 500083449 778676888 480679142 20779133 868424809 126775291 224714766 311755743 170333205 65686626 34417554 437315931 111060185 930742906 75637436 381085961 540069602 116685448 810835677 924957020 628562120 211820351 163340724 642388793 353900187 28553465 776642129 673787805 885872962 91184964 847534908 176870969 109172443 252107480 713576657 991458832 479961837 789420161 481594070 217618431 126064443 511257009 344461218 678434772 329765778 858672017 29844153 858280026 217126144 505848197 165419627 70811101 448396747 973455528 438983116 404449381 368503540 538846859 498192358 491788219 244335193 532237393 488664716 590900297 755961006 590212438 639358351 585571981 243504847 94211089 609369668 968707804 85232681 30249366 288002565 551493480 325795116 369736666 575419161 438905338 947264425 654057462 83784499 685077038 79906177 717699593 635138897 798655375 595933073 448080399 649884366 83922241 191527816 137802865 471518953 736931981 541341540 520051613 37581055 453648827 760026746 997587131 297415191 397995450 175924291 222547197 960400484 256061480 132860915 273800949 12425550 41935825 737724268 998944338 941914462 948821859 363687186 831458930 136823423 760197581 284910724 440348092 631459726 129986170 221080087 49871218 843120835 932161508 645792136 247583872 747733106 695369079 469609952 515463254 80040531 738496857 595674688 697397369 610240915 439222086 104905239 934110890 383147419 292099097 715890189 100015323 897901930 548986538 585896404 133288466 425463941 353332975 125946944 786080816 557039564 778421878 787085351 382599458 14417969 276556075 321435879 811372595 538293941 721072297 734487662 304502418 351826998 828061156 152025105 930947721 373700342 583682770 75739635 438688419 358943640 787288827 224065135 802884885 614016871 942568863 313030463 648228252 110574001 892109864 766798195 886817594 950723808 918726066 569783932 400844789 430286841 535785717 753969102 436249886 966215948 364527715 937398174 14702287 789389324 633471780 498879181 469135651 549950294 754998010 671891310 699970223 584634663 143448563 819079434 106496504 90421358 64958560 695301015 506845365 706503429 563674713 425742202 306771071 358830044 547790189 902375579 872401253 73566611 330251708 123143227 917971798 950790811 716178734 368923258 808949261 136453534 231998344 452288415 57945935 348904227 614807517 265279223 895634876 374908654 710330305 198388709 151571506 443655703 223726049 724246164 102655053 799398913 766599284 325045265 900541086 501809233 580100965 611592505 835963977 43869575 491363798 342852843 628979001 264437525 724368766 415041857 522816861 20176159 595523535 693136830 632771565 828875713 671624653 529508634 135134299 680422972 648761720 550854273 240843158 419225347 258405295 282159513 518439300 717912277 719731466 782150007 274182949 118903839 953014624 63286612 552812498 789710024 120238004 840971402 750535675 166333977 392404663 370845717 120006185 94484524 725856882 433546530 891726221 536497589 436475670 580391980 861330901 459975837 673308545 811544020 635156879 75186022 179137848 119403506 708101000 545845676 303634506 358562200 772110600 242250480 506885435 186397503 394629251 227889723 644750768 5102458 494389325 320420614 647292920 930241968 57331643 904832876 820378761 339342630 422960476 38736800 107864212 504891443 759997376 287535449 94577091 618362355 184266960 523504843 56760009 491326335 54432406 951981950 537081886 251251529 336401298 316409532 350735103 501981128 144786650 274665225 563236184 571454458 116921824 991700361 144010360 988100715 794702840 297247761 730622146 978930740 379455131 885438621 806414940 74404249 608968466 102581322 231489120 583646470 633196128 411367687 255417595 758045389 553806191 431767806 548654636 264069193 162307234 179448291 234505302 332541186 664147873 319128765 115235102 324577167 107611622 369827867 845935889 85858273 605896499 275651407 337484308 225188941 183417060 970965629 43951850 579461664 283996125 715972721 573539428 529590339 591254914 772588782 658500095 576684440 322032826 230913076 819887779 248460376 109855701 130315339 693560795 425958825 308317099 957259002 734484403 593767492 402471600 622999888 801820163 127926763 994474438 514470889 177958711 697537121 342669001 884587980 16687779 464839359 359610852 403094783 180696945 611769495 495149324 76438856 330782075 191781519 307750615 343892442 186872056 257640240 846601256 696552828 530694208 787965756 615626578 366219710 289706838 660172831 259669468 756647985 374672824 190091269 894004693 682221039 404173771 188534483 105402355 438969798 345664351 857686540 482634712 309546885 541232001 586263990 63211997 826267427 955185216 48342011 165250399 412392689 101487479 20745771 371705601 981400022 272196588 984987617 721223340 846189379 546380094 445049043 606292438 506498651 447260403 91388719 488762449 332781054 103000467 547340105 153372785 124568786 309404342 348751854 871133122 814120480 299656915 665159644 353608894 924678209 412042870 828990015 789055339 500039862 836584625 516696992 378011286 915364431 392205753 669860546 851218845 373977247 167915366 133512185 676824315 31526531 425207802 628394359 905424551 288007853 702990239 821711163 164911898 704388933 30113937 877450188 369914659 279101302 187753912 811629972 191425501 433929083 966208213 503053152 190984599 226662776 187379559 196186017 928938569 185336438 408909287 368328936 990934334 182216787 567783355 847706306 128157855 350420600 290721245 139062104 824456457 816164757 540638036 894817379 537036685 764680613 778813696 227763532 786063433 969642688 890102440 965851055 676326739 836473369 556709599 466563095 958893243 610905654 758472887 206977249 942083111 341136744 668289821 108266167 512744247 786718945 614849077 445788547 527843528 544032151 166931012 470065677 612394009 484771658 638509139 451488520 458350803 135589082 699324235 333770313 980298758 782320164 627387911 675846202 149408170 730550408 599961557 483530066 783226193 569566960 579069838 665043052 760030561 850395092 292954627 115768626 971773340 452800833 37852274 9085323 245803486 671618521 416323833 491586657 237961374 28975758 423980320 229236911 24196835 897444117 478059573 587969765 452201363 813032537 263155044 656933068 480444247 505908613 918642364 544531587 804611283 497331838 898638055 552028731 983944294 932570865 543173228 412698052 52741857 945297649 820576936 882343013 71496220 155826139 745626803 370763848 191794460 173767111 937412172 202000394 86931152 617614156 465657593 180482742 324393019 779796293 704810727 291749423 679706739 459263891 377595830 308864048 630906063 706972540 91836178 122937012 270077879 833228354 72612162 171428529 626640921 110318206 85485712 931286226 949586939 15256947 749256376 839015967 544538410 893950820 652085208 894814878 534247858 577913471 983582932 515828546 644901131 977037992 168497086 989728960 717673537 248519468 922954483 71503929 231482527 152370937 961869416 710911520 186350160 418281917 932703855 745614780 948118741 373989443 912883138 534133705 614825544 609452410 402342333 627130414 876176019 114302249 329291323 997306197 281478009 259655846 466183221 958388242 89713530 365675747 907396859 464992722 76383953 302246202 206338125 56085390 680149321 590408415 752092043 104246937 430835934 63843857 246598808 170781567 873971584 415459502 1292778 365696710 252849329 666049750 314820810 95549579 417091391 390598281 333003024 700863015 800741943 318017101 960498434 939468811 149245028 98433718 204609591 380280896 856560266 921949214 577873936 654707762 529356359 81230241 975795944 959763691 611559548 416154407 227710474 466268260 299763548 734750633 582703885 326133699 846118019 407923686 352607468 278244586 904376490 420122865 587096782 973974331 244627766 280195576 425051724 603505962 184739347 529993353 33931812 954395594 823306772 784891154 870174851 219744980 39974742 917423929 731438461 803044952 957582792 49735532 765631884 718679240 866359529 217807152 914277564 282885901 608862650 339092712 974902555 146896872 553692320 957667900 124004716 433406953 614296983 999373799 27077499 429585013 131891036 455680137 237866915 885584051 251100545 972866181 626603589 28552515 720346182 487769070 273360029 593779055 31775487 938784862 379818259 298940352 189764089 462118247 182015490 718576428 279123 736625131 838658007 815009982 253506513 66446792 228888510 225909201 335855187 416955292 987733115 704234918 345087576 317216689 878406578 515621364 49266419 793282201 586365649 187480883 382546032 762235770 750811788 513958452 841510894 306799593 178411672 832794177 496933725 558683371 460364819 873915234 169980466 121678025 326445416 607917516 59418631 648366109 781823599 604583759 542404951 306448586 202209190 452520015 84835064 884676391 372575062 246105649 374143959 615403944 340984498 369752357 945302075 368010658 657958555 436037416 647674202 28762391 601755927 882869190 829610168 761185370 246138915 780176611 787888078 406029952 832101682 744425676 325977797 390401434 913531905 394013442 12086407 943580780 558351586 752921717 733071947 920200402 203232242 670208148 947509305 904559018 824425433 532561497 422017784 6654882 358407031 829887385 417673409 229951766 352460494 797073921 462816596 243940328 758594459 443972582 156563071 82017547 294095493 128202304 573919793 3611703 98179938 917234519 673274700 480180473 757129993 968235826 882140880 479453309 686482090 753101343 867585677 143209458 623936090 105415116 186052178 613497980 620947750 197221736 552899677 318599911 178061063 148958539 74054080 40007119 942118481 383543656 554097193 494676243 390948170 570702452 904501385 330416737 45906892 52576873 827112409 364586460 937385925 399251233 300039327 903071185 739384749 767027641 190520917 385928489 44878242 576891530 718463487 916729965 236916519 47986967 601409618 562155812 827175237 946957805 936092967 132972543 982318866 306883281 372193123 331485941 869257503 365199211 543557485 754992308 13373634 833133516 258046764 911787140 798918846 1447435 750659507 51976775 647833989 965355226 858418775 389508520 551535831 749800656 277434443 127064794 726642798 824309015 72324582 402376213 945182515 6283850 452579616 768536151 241848627 262950497 152381740 647607429 999931408 794552578 225825391 233001092 79856573 994099404 778951243 875642618 116352059 372177997 137318464 313003898 697179303 64669929 711581916 68622866 228506264 928884809 384618471 629783570 48764399 608169998 103207732 693854935 761665134 506252281 16146509 340196754 670142378 714104819 605035060 120196257 871683396 905755790 983025944 397344953 360571830 711222019 242407148 448815148 912101342 215119720 631578750 278168020 390108751 407566115 927548025 474692299 993270789 400805959 76212434 257991662 285449123 394583702 355708106 201358056 596598560 55822109 160384744 719198498 463402222 573594355 517390965 553364447 912376865 374150258 732782769 663027918 564178738 474978320 190582347 671421129 227656467 112163092 780193909 424257145 651280974 38782199 923118261 94926293 723904935 818113542 112263415 966899313 544634256 612010376 631864889 373206075 82984682 659683174 887487147 826763596 757798964 548805890 821115585 900801770 358116272 219168859 57191165 510114412 550571620 8264506 668994856 7756755 300468581 433527004 852947657 423076399 552987168 989876459 777362658 211455253 765665123 932432702 159425755 390722103 572562391 290839586 128612015 361432737 995539200 739008319 654875169 465545201 486286658 166454070 668990361 262152494 280659473 698441217 933298766 354567657 742917740 74736139 380619536 339646999 688428345 37970509 18502352 715647349 289694721 223689654 917831531 101817007 322051200 112763963 69815960 866812903 161568941 273688606 976249963 972754810 900266294 546898961 480539456 74411318 995177992 72952261 827624446 177273532 510492958 905994826 895013036 107225421 374850853 784682200 986709264 647474195 158950443 780472116 975923858 642652360 115752021 57140178 206931915 181323670 712439243 527181687 737757187 51256919 327768478 121303167 633738873 830407570 406762694 774479161 203589172 242937908 371093990 431460084 524399470 120429697 973275923 320932366 258931509 379358555 794185381 746766966 208442981 220419332 860743770 450819766 633924009 302873139 683695588 637164725 441766216 814594920 474093424 859876849 985001180 672937076 744169116 63049576 665493045 834662531 70761192 486309472 85667172 952699144 701216994 213677258 192988455 230555312 606837774 364789462 798568840 127537343 279819236 329267692 698681595 783736848 690898897 272514230 587868980 409432643 362059088 345550303 486548927 899871015 645859203 365856858 778851582 462387949 464499132 155692746 303251763 374055076 470228026 440122757 200415805 479076237 915697071 134428116 363201793 244884284 978196586 606151344 78081385 263424428 455435354 4409172 868437561 955692822 532143636 956110383 26399794 554736926 503844790 394842621 441612305 284237697 10684779 158181369 409526940 538147276 646624448 106553406 640853119 148811534 472509700 411747486 538715254 653307938 44729320 617487578 114784137 862754042 508486070 226171467 557587126 309062039 131623612 521356505 494865908 520761944 799563998 158905507 889822003 950343699 854046715 160905050 633606730 656337884 135964643 290845383 520314396 540068190 497854474 948373865 502575665 377570275 405447063 779671511 887314153 414130743 314011303 679346329 446041544 984233252 759627096 824493825 592996305 855909521 421998448 481805888 384463568 249162546 43658225 305677235 210603662 694010260 182066486 212267003 225687731 793660596 499083889 745795870 687723912 510873817 154605248 728895626 111038465 397887967 859980568 101235351 4043755 591382276 520152509 615801246 631306576 702851335 853134745 998016434 839061203 317581067 532837799 586201787 943974127 327423719 984105149 535353020 400803268 759988739 232779942 295286983 125459732 940838769 824420859 424383531 976548619 624666923 136742925 280856480 574249017 310915300 183373444 740296425 858230304 637016533 267470157 888333246 409286282 476163864 800993245 440173281 81611357 833783057 608427615 876423752 876362411 491303455 262983885 207875019 437239009 259216237 733612875 578216493 789238875 19923172 897542920 44691337 870420005 430728768 770001732 344772871 552355874 659654785 838140212 383429182 412209763 28724705 739954353 463572942 431122198 593079156 731624436 796277228 73007181 216470504 112713109 99692803 500862425 268000577 706188541 167345783 194627925 635928588 698892905 924359755 493893445 725906369 964414006 101392423 404204904 685555151 524733658 464683834 822507790 243332150 424661103 728439312 184782206 690626579 809637524 73580299 101933829 143416189 836398570 446862014 573447675 191110972 362672206 930590755 717995466 13644132 482790769 498691278 127105656 87651420 826115002 825566193 641830574 651057799 190607813 389316841 652250668 653023538 591611045 925293073 935941334 683628074 754186456 491429500 216554329 209551458 954126318 830661493 288365220 92419599 621548583 517914967 191194368 959377794 405879823 582318111 413986186 798880249 719628103 22990891 717431068 5202418 115086478 185738628 168921909 738824568 723125085 728415939 745572377 315618766 230328997 985851801 122355836 351741801 359701882 857853135 785562770 388348338 107634810 14527476 575578377 492387967 195741448 677245335 167124503 349053626 190156069 422025270 107446510 546140207 626697456 84758727 615263547 351928682 322704047 251861119 546819729 329704221 991504967 303710736 476601958 790166928 883340910 764399282 255404783 691826601 46487723 484011283 606436473 352059487 444771196 516106490 245426482 568994923 991768633 329066121 642425925 428019136 482189670 954056082 848683464 908038300 640024487 797530843 286470666 590118464 83524161 368329081 17909246 466774524 831223287 763412924 92821587 781384785 739589489 32102862 593438814 462618557 920535907 518111450 121209735 161060673 163936968 250652338 355617090 262825653 218458579 546341070 889978732 315375050 835076868 199405239 130668809 772164539 506285517 862331124 822839746 196510674 845107197 410404711 159678392 752441583 813925570 905517338 75940611 708340259 612882800 75618382 382931328 304532212 223054787 857020617 84046334 51329048 408206236 508623909 293562116 503196042 450953673 111099502 683211901 497621029 140275311 252458007 12338554 57420624 40172824 722247202 480418213 356041702 728904693 793289599 685071494 496933443 895218221 176012084 667496293 626104156 736831468 357906201 500407527 533512990 467287489 623706002 472662577 93703693 457532097 699518777 469312394 872190815 561923923 578224240 742116064 273286490 227054592 474832593 305256610 405623215 156659458 224372192 161980804 474217152 978888510 967045413 826751143 189767451 428609459 974700066 752950176 647721523 872719900 209365697 253087598 122727293 907366415 927767245 271784420 247120066 895083962 806458701 761060948 933618305 393387884 801987795 107585209 484209842 942114366 120086067 47680543 693751262 821333262 624827599 345134562 677185177 466759984 820142919 754109076 125491848 959708856 3680400 164225310 441429722 350721825 286492985 548461657 37057299 244246464 857949974 267274739 56920733 249237969 81394125 783024823 246535157 21737449 478107370 253203372 739158882 372798919 885962224 401850784 644037241 358460058 937358530 537174630 666609646 599874735 528768670 326008229 317969980 511878360 286806842 743293194 281821093 979051874 10803767 255069778 642566952 349007241 688361219 326431129 850403182 958453122 32895799 364859151 26905458 805123674 813400695 895902277 127023849 250684489 835762216 861221941 184856194 640360269 369505851 885857397 711195074 105884670 158568241 629829088 872611003 561108192 756642090 902344075 394966214 709699981 743915970 889082273 236595043 997024031 348517358 84972341 491943681 756174161 375997890 45370012 338872484 419759270 629719624 975009345 836511390 504592154 885896898 770281212 939490972 860803060 501431331 896611992 331831490 458417212 407235536 606650691 76357966 971282403 459492407 719652011 436312040 264764851 585742082 717007934 444737653 636298732 876056126 458271268 500894682 347255169 766390249 874933092 887313163 658973848 225152052 577433838 440099977 401401471 380771767 548240207 673186725 914235671 189524958 109316197 920842847 94867880 690474831 399698351 590367093 875950329 650594598 246411040 467272628 150809979 79439480 985679381 6659040 681882767 338507529 751679042 484297559 421905065 518334519 111428976 244420796 593547813 64844124 255432189 979123465 871675559 293895801 630018845 108322086 232015964 292587891 360875493 27947380 369433749 911848746 645043731 465737226 738850241 446010518 49277439 713391796 964930539 841014847 347461126 820303556 645196450 728966917 593663803 586668958 495651155 198533979 126155272 503029653 323330378 535471817 911055650 243242329 572962049 874193927 133798407 633622477 968180014 676697692 806185438 397250247 234210110 486766643 940804298 640803390 862606760 683237106 374473270 245729422 110563921 312009664 499958947 30211561 302987079 206444598 937902585 963559433 686062910 417494378 27680821 392291773 915263884 547558602 117123406 356212874 474514222 348188682 451818217 582228004 296433051 429774874 570255429 338209682 407763749 243970697 756244251 534734124 793583013 300208787 132984100 584167754 97752071 400760095 1801698 344301626 903416434 89997211 445843392 894019388 900494279 578905442 792841169 65135951 152508991 349454760 768628058 708261844 878998992 319010294 412786352 248517078 654586589 377736303 727634459 793929806 501605947 881274293 632810667 913493940 901165449 396850227 416383229 188910951 114329324 697548382 267956652 498230598 798792632 980036245 187671341 244708631 686477423 143125179 425127965 507452135 839695403 919478732 192700072 379080169 138445080 832872836 520735040 43621092 321859047 307870997 431386589 172162937 435138445 478409848 265367641 272210414 850811629 462903414 805632988 800596128 126991810 32817614 443611035 299071789 52967612 738182520 141743354 535419127 281630350 414502494 379639069 672074917 822752218 26086621 950157618 591962078 135141379 738256242 647606587 786744590 223910483 15320067 289015589 242025613 744340761 325351404 70219959 16716625 883895087 818058108 934597742 651209718 138186461 819720460 163381778 379675491 790941667 150062059 416111221 311983489 26889278 566470341 192543372 365368958 675972221 249251744 547315364 161166041 622759554 830383846 838396391 784806391 609654006 466388002 931734309 716143259 612319670 209817765 850504720 835864393 597366696 841090836 72459994 311392385 210760318 913606464 947312013 405839906 529383350 120501632 725541358 666964500 283535987 591112442 666368801 159825609 936859836 528719106 479395173 601469825 433109605 270557282 255572982 424963384 43688148 395791283 924499211 342947520 154449105 169788087 872244747 169802968 748777810 551915691 942931622 99492277 289072276 84687765 878369062 487820822 57608106 467995626 210175162 851961744 460165572 992593510 597629092 455049381 184752213 190002068 224452783 882575310 988322432 981597065 661316322 246783766 419274716 962573231 861980718 399621319 700985175 336799359 453268864 548180385 271854868 378894131 381641359 594724506 227073298 873616995 263857907 536866639 636815762 86852298 233387204 273773488 771594329 960522441 646760112 26000105 180754063 17780780 995314640 808342396 213166092 504900118 809142488 832012660 862696788 925914910 12096424 952135935 890099505 725832435 524162748 195925688 168643102 643555020 767429509 987811490 921565438 399818136 497896554 49955915 122812543 876252694 798898111 149341711 938627168 486783603 267902449 623786329 332757206 649976546 219345156 821504620 890131658 407752642 396259662 473013119 320417114 396277520 6997685 548259699 40084509 300180689 123643536 144603904 800779253 845377722 560835154 690435960 83769900 976026892 224762752 881524044 241807516 790714018 882927398 808835805 465431688 945812858 795020741 65216050 466936120 262243811 319708925 866302734 603269939 530911963 346882426 451743879 573171262 695205408 442642546 791247038 438306581 521797775 619395934 629452091 994805574 325251347 400271113 642116017 850724386 352754008 612478717 315080121 595926648 692587916 667624777 131927835 621668513 699783886 280928716 521197520 356858787 808984877 368729855 876203320 967379703 548046127 552616476 777822582 121345603 312476748 669581282 736371322 50996422 957887582 421706811 858177142 629577052 758416642 240578266 394897026 633145771 853108293 433052227 441412648 556366378 153042307 26665487 718914389 49513563 976387401 251302836 10336993 223418029 266654543 164294204 835948003 555611299 332856998 626618978 31278082 63034660 247943736 63833565 977594800 482655785 574767296 185930784 661316963 695164195 77030023 738489138 594706958 557832897 815205021 525761445 987193074 391252234 906063708 618920224 496507455 259885840 440813746 777179239 564860702 517864176 751404110 299470950 159165159 625987998 541199943 468430944 470124046 200501125 31145291 866114909 711283884 837778058 872713022 342411111 526008583 61756111 701184310 532104738 376511771 87472418 869078197 816370582 510812489 226113653 195616411 615875459 752036334 39945516 853266343 728126466 66962216 726961808 637133041 505742910 512209240 120165820 63898534 692246163 991054909 519691653 247869539 546905378 742241997 597342287 132719703 675655525 365192814 699691685 422833540 309461597 566099995 553096482 179017586 961103314 889648984 414760176 968518382 142419951 808960744 675735713 278882767 283010736 782496261 951525177 3117529 589647180 858633779 404420745 966797479 369654054 992983831 909985979 411302754 258998247 772124880 830726483 67829119 920915518 485170304 22631470 565048690 769464402 612243220 638757358 249547169 984679983 140485517 962286164 124646292 399495718 896140429 402564995 912664077 345656707 505286117 544445368 410819558 796553134 698182742 360382726 826825001 696636226 524946634 306561190 548780391 342428290 355114322 633311181 393568163 781812478 861864139 710399939 118160962 247274459 650359723 894578124 793994884 241005437 609413061 788777014 628188451 196312674 777693181 735525452 764226628 588589479 560539047 358891243 506229915 221065943 782186193 852705243 458891024 365666787 708873312 516215976 218526483 275876389 770986290 156258051 582640201 881766550 492105847 970055699 134492468 199983231 734211153 426476908 452211987 562479433 33107879 828033272 231647437 689539393 442397512 518848737 721265375 970498229 300199059 297344250 156105030 450921742 419133507 831718748 264350469 440917825 25232368 561908558 6366182 466050695 852067507 118225366 6235279 455939207 928017691 994756068 715266233 86025498 174288891 519236232 426129870 959215993 331864830 956921875 891202940 430734065 132364373 700056433 785154626 981808660 629427341 239448685 46102951 259456125 512367600 748093104 919621431 694514469 722717447 515341973 126053774 391462880 261688379 50304895 926199225 993289955 947356658 85444472 313015928 5910468 90550568 105468428 941680112 45311937 279033228 559116740 603725092 35029534 553114376 673148985 374239430 657263368 747881933 818527860 27480126 638449646 498567776 87940190 601415980 797320894 362716562 419787494 86487811 536655999 298357818 969847313 763971407 774781147 134466856 492954121 154524386 430361312 205665256 403495081 524298294 558878728 178614184 930910861 56389913 874702592 741986429 477061302 340664170 544385675 383702289 852469246 813111731 413181131 400934026 977741671 524854375 265104806 562077365 538254326 168223075 365286433 744537140 634976335 376122916 737324421 833671821 506326385 8929384 492461620 7406198 437305876 875371262 459027251 106023591 3420572 274859086 948014093 174263123 413681148 341630433 528460076 98242168 997848921 471861483 369172174 199985879 719700196 584900858 683284952 865086527 311893553 650573610 85531762 833784759 707584479 272720077 948533611 597588058 929517232 161673862 850892356 712368032 725365262 579992570 879829328 757342403 218191715 736000128 617901775 92574259 715604415 508846764 558351122 722118563 847742685 206370386 549283961 28550780 40966226 863223577 322743177 515680652 977828011 106738736 486259748 70584180 983736587 976615756 154816085 483874529 41691268 827231541 474007993 500995967 868381860 925670451 72072885 263851458 759964449 254271145 864875048 96433819 684510240 925857511 9242659 970107154 872849905 919977450 827866590 718697117 836634585 14300872 367555352 596772639 417478098 91203026 514224937 949835413 885586759 999953960 70403657 877346778 457456922 99904424 157306472 658829891 238187155 971684161 442721146 219913310 365707673 189067654 766250337 819985039 792430638 524985442 952690302 435336256 930333560 549027573 849359381 350402317 859351280 625989439 784726340 200669626 607755664 576424672 667219036 586138139 526331569 369932753 923413409 542738226 524140104 116082680 198606621 831640531 605715096 6790641 599648965 156177583 632741590 331180877 596783568 749566316 127530145 569223681 78932039 116712614 59239876 474370886 716271443 220858374 198913763 321986798 538689398 846852855 798633532 162034695 731213891 985517952 681190905 214049026 688309321 406859513 430985635 321859800 97777551 615444012 450097829 151439153 90674273 407579906 437692994 705542977 687672289 58215922 321539800 273527452 103495212 562047219 387080847 70136617 870753533 499066057 186301640 455491477 901925770 452458138 726020095 92989261 681936308 804065463 30243669 281187969 715409184 176119936 788575523 106645579 190105725 607192846 800560418 827687370 45436600 57008843 38503355 791074353 759873604 840034077 479153889 578526152 696005906 511306043 290998227 77204699 989894055 64672976 730057969 48303175 87883350 993203332 740309482 38069338 10075948 371643796 912239907 610811004 380216990 922317247 917240514 491263244 302648799 104126786 233232592 884117332 973194724 126760129 983650658 646226392 728039939 920234727 416182728 292308925 367440665 307621368 15773287 519529703 869154077 868228544 561402281 186681370 76311676 741079302 310737504 696585820 470636466 798751188 724143119 932270489 279903369 449628 269282521 906591183 473848992 533416446 808195146 873625750 379175284 775603334 174473602 967752916 272939559 146300626 121844094 955846772 904850344 690283145 926271403 287358150 261730574 728943653 94903229 582295896 259213621 502436494 672025409 789405809 45062617 582006377 763399317 78777469 727366706 15527256 130978777 147063885 536396757 708250966 690543139 98684362 851501701 514863639 265024564 953044948 294970194 585772675 776894571 956529903 674132723 99611040 64418020 221070980 834970686 935418159 649490274 133450052 550522597 401472891 265898374 916499413 881571347 117330628 547951920 823958097 740743839 478455947 839430593 967499172 978847769 917740943 151176248 145624761 148916621 38948975 200879132 219209632 400934859 905267891 916713801 758359842 346268912 837191866 297878561 207709001 267581320 182499581 836537188 360545604 923988803 833496613 707356967 101861227 323489922 677337978 873739738 80768591 597189278 490372562 13862921 499476666 159677642 989733637 712192593 256903609 426749199 902907697 33030876 254259947 108913447 703169321 747998380 507507694 178599667 206074886 882263353 363798838 421216838 825867354 548785449 723145765 870759521 529651388 369466515 68842247 671156768 844939472 198968612 822990644 843607698 446305710 667304200 35552695 835427146 536947218 198574752 930009144 372010759 541474568 340466980 186452009 746128535 173860450 5002943 873716616 148301311 574922936 308950375 891362142 753021565 566048528 76796790 703564052 418329467 345276545 26364405 470577745 278967005 65132272 766162577 710450978 856293732 949221251 321417334 585919576 337150925 987407417 156916416 653760672 683020543 880711990 157323573 657055886 183821501 623696255 576383743 358160625 432586607 162327659 324818543 655074307 400182523 715619944 64136033 171634100 127401699 412511749 776564399 814755958 419051273 427201730 354464877 739343043 901686710 305017648 54099164 886615919 984541187 81494454 368936364 719814491 297124531 990503147 672315805 123150360 72764064 697460799 228332762 889579042 243780317 787373240 398115471 569473636 375449438 344045403 370545280 114108041 209644996 879343058 173211720 953903720 221318803 103375671 560192699 265657859 402636340 43956879 176978288 84073458 65965617 742305841 42733797 528313686 477263488 938077645 772457725 624731312 804987351 645915594 181166808 406912467 573763424 479832647 513506078 105243023 872048421 164156009 215858047 48828291 765779672 699767209 587040286 803233975 589404681 179221181 415960567 346932597 97195242 506654257 213289790 862746459 479112231 420131945 644397410 789058996 8932966 195507869 469606076 436211858 131004342 21013688 129878306 596350340 337044448 266025651 680839391 199273173 183906269 680245172 574431234 754407623 967587700 659308532 111628719 183606104 157135932 181737050 675331490 960529187 554800931 377970581 887392068 972867532 824358375 787891613 478476685 326651345 387895232 782311848 218607205 515444250 391596632 86531898 231778910 127712764 793712715 373891083 513509265 871644605 490134809 208188603 235859059 93963271 206563740 17776203 459331480 552774321 772787992 274765402 838613580 410895035 807110450 371476566 451056528 376289685 119676676 974929775 21604875 281535329 520629412 176799457 158602897 636639454 694115333 791475115 837334534 768595053 302620680 253615238 827079448 297562465 863449227 121233186 802547901 286138488 774389398 47065637 352113966 605655385 822067022 82913052 147811014 242761957 437375111 282959018 327071852 929736917 314322524 928735189 670582947 538170518 66349477 219573111 806499351 914896688 758869966 911121701 881744004 85510461 290043986 145446452 180444559 166390985 948422714 353867885 574696874 413990655 721487078 722527387 60834249 415565371 657670883 580661345 957453655 698312303 307169950 755324024 748645619 820754532 69166247 365154452 511343103 604999739 235433074 30436701 670473103 642904652 278076436 459949677 137899783 552213633 937716738 330190050 901836365 48582022 497986414 509598325 143271161 112571489 929110536 962959042 818918608 45514065 553212204 748641517 31877256 589328019 610490196 493282980 31763685 841184085 308571572 27962608 939576446 563550106 987775028 546855306 180274496 854246287 40490210 22480421 560334216 878478124 262264737 917323534 623014668 457105007 282520822 307239999 535318277 213361550 907815580 814940641 829094519 371556914 319125612 715777267 826361548 190636143 210496827 407780495 398815218 398368066 812580051 166097868 610462471 725403963 728322834 76563429 7959442 241848113 245613809 56362426 907106618 847074358 750599564 71933076 257707662 50609122 542261038 587704812 556904030 231469477 441386887 604057298 174447756 772377725 202017731 947444747 12584660 955963089 703110598 565662901 210362697 633278022 335351849 227642097 522716148 974589430 692929739 638271383 943294835 304893955 968334296 520455402 151789220 474634808 363546507 321050999 4882985 93634451 657346619 874667242 505019484 648959372 362930160 948235532 171964718 327337443 321615548 477745706 277625198 375754791 615148699 973010436 651304107 609452794 101201347 353474421 606217812 947540843 24438533 718828531 1792295 423232615 864212634 924368420 753819300 537658286 269507206 701592350 483003294 966054952 639837506 44057011 447502858 838435569 370078506 712711636 83607773 138014470 209390038 918614969 94112178 208194776 233046383 671030280 230894172 757619936 482258379 629415722 356026374 909202429 391412155 927058286 7433038 642581083 793137028 517873908 633282396 816441200 732580259 903564475 10324520 395205253 870789021 675576572 801161994 770116645 412152913 402528365 688539088 457861356 166632265 181578007 420995553 130113079 978086955 425726954 701872030 152897451 712201402 788671297 251686732 224584988 149454274 451456832 70775270 108557877 117589995 752924019 850936396 853428926 397079209 558286446 270055961 263565963 194311378 907023589 748904792 370228802 217429337 858829623 956725592 427102020 250118576 763503774 879398656 844060651 739815257 104823029 427991233 443707518 549592650 112470316 691330539 619289731 528706856 979641547 706436567 75931300 358659461 210632838 592344526 268525021 384007032 628910999 863464890 269961259 626102781 135742850 309951190 501486277 324273941 331645492 408936992 115336134 352665146 3609614 783220419 157447260 647222496 690203646 429607326 13040794 139197644 582333238 317684916 854378106 290035465 783173230 715858218 523944463 235166902 593426591 453734357 789456903 289833796 649757509 829793520 211343014 194736987 840176661 354549008 533645759 760306854 114032599 488621099 709775272 806930229 625432762 211187715 11036245 56692717 602557540 398958320 590259876 423611513 413516860 987238042 476040833 785798420 552394929 205186991 647032230 380430348 799726646 594308158 792919406 184034193 768980336 515024825 224300157 831946013 578034850 187226300 740132425 863803616 131147612 199420830 69546366 806682795 750959273 798930398 160873416 653302947 639998485 5366401 462369299 524609097 322018968 859511724 14831850 58891223 493811004 644909460 885288130 704052131 732590933 714955800 291887412 854374844 897803987 131951965 610566803 950255469 775354956 868288521 778510324 161121795 630882210 737204214 224896888 919827871 938996387 749581224 260712374 864552976 972035053 462528537 61481529 42512665 656719497 673427626 40375599 613858773 616202133 411915005 466417803 579222400 701521317 609889187 59283002 758396368 327305165 792045691 166293748 368946255 223364913 943352159 906434399 159181187 546178172 350540728 76940783 189312436 311280489 343256636 1479428 61929015 553664642 109397676 89194785 547182030 520955022 889945511 861559644 980777181 315055683 614543175 501215853 373766818 399133473 529463385 342266977 647733221 685577805 87160940 51158524 402965252 190361928 272677284 872680910 48221155 431939360 898208420 259189972 504548880 381772475 894588054 825393936 115938879 823531827 29582493 336188873 869940613 866524918 925947 267488611 790430009 956547 620858964 806949655 801118692 386778917 51431827 467982008 231810459 579017018 914336998 910306771 98313236 932862119 957666194 313458884 183985934 298334625 270594602 83708356 275619708 321246137 339107118 758862880 74488098 606981856 970306793 599319579 112577397 345022300 548235856 22317549 570211938 132544126 413082597 116576236 143861332 776803400 463640749 997346454 168111501 750876451 145029252 827052904 751013342 651209567 822881830 751777813 937051521 639277986 284026462 418546937 80853094 664809015 230683309 446055317 924928256 717779465 549316579 591013495 138262493 852377768 18311112 985398662 296426018 410036997 338687346 415156645 43261654 667185050 385556342 971062651 88230239 700750837 450190810 295049577 677074140 131385894 52915745 893705362 193051869 36077391 320290537 890067123 462379077 383601434 891247957 47354958 195979126 886503165 93918602 868003480 46157416 745343865 668208332 40146741 691552579 720129660 930855334 552576955 942903744 679076886 183265971 893650115 359073711 728664019 542630081 704446200 196241145 218585542 670927134 434279853 285251131 633130966 6195086 828537448 293424001 325196892 518738668 132387958 323603349 649237792 553254805 203804910 455414949 37944572 880694038 800582343 790140810 410759752 890595570 122745092 175119370 283986849 98804075 713833000 972821316 223185743 519425369 524488345 911809460 405584902 834565660 377389764 287206299 639927277 505287237 928400610 520772234 553956934 297052386 404356893 584194647 212795468 740639417 413532649 164900376 651219770 19748567 36155303 864617519 654726667 494848334 860418193 164091010 787672707 589004590 959117087 830548653 674640711 166162779 494886634 189990650 756105138 632101372 869855636 456802864 812131848 101879153 998317948 612847986 278163082 197749772 578474907 225534506 846715410 465910518 984441609 195266306 652645057 277511902 427251645 227972625 594756387 195587257 974175808 129059979 836397725 406158488 932097135 257781801 962760982 250615 599471582 537587466 967328329 937702752 589780503 939695345 301438805 743741880 398964894 548877330 572794609 966009943 801648132 482660083 347486800 665252689 477722504 753934070 299195328 200723501 164336538 744303960 181746302 369641979 161717359 22314746 413380203 202357326 27580955 41643164 505088335 446908904 984397102 986577288 258468073 824750438 325997524 580537865 546065462 298627576 967374574 523768016 887908541 992683616 333406889 482839563 174248518 425318988 428879139 902061545 196598971 754163064 792303956 276928249 943616568 676652349 181197057 477386119 805053232 817271186 680102824 119857018 496834884 547800544 134181851 624791766 919643274 412526932 539815115 878447347 618698368 543851830 433346532 31007023 441733121 358241641 805345695 706325957 163618802 194920961 804751608 928193924 227942429 336500904 139253395 833500793 7328280 277408936 786173567 633737352 60928309 745736188 892933429 756286585 625099100 187679390 798308846 683471997 269822199 978005178 305468729 760325983 176936859 30916227 561258105 483982487 279812024 193626334 388908853 720701608 394376720 125407867 167486474 938461422 562247008 216760602 499001557 420928043 120677122 317016071 812143443 597787168 924244235 32948036 754752977 568593102 862391636 654783666 770285061 569886679 292294423 248901265 271290408 104581256 422332217 818077906 30331315 51695361 214714468 72789875 676138833 170091733 789504418 951445093 843974277 975850110 126479449 251402352 673803857 561503040 439141817 635610200 229844087 865801138 834045602 488058075 1735485 180484776 838049053 786314506 482414669 17950647 401228208 490461074 198346632 449467427 544587732 871725782 351296975 110406453 313025560 611948163 765411359 916346549 742114809 460862156 400998107 346234241 605513025 331182218 213081334 479775509 370111513 644515270 561829230 854434001 774962458 216441250 981305439 214018398 170807601 469827969 664091178 116047506 691379060 738249296 602127557 794795847 576670964 130081792 35727800 50640292 940324683 903405166 686187266 193711134 223959498 96696104 465989432 522687512 17502674 289570768 182141359 96139135 393218837 280724124 139280181 77177714 539224228 212034512 763734122 729875289 499446417 826426469 969156405 752147671 244408457 36348441 101912890 662693061 308695213 358616062 235475979 748678043 386468900 63004422 458634499 133162108 852354075 993763771 835353965 332633415 521072220 555007692 718636710 639873556 797664309 638270656 420163807 335447821 258523999 390555122 185878003 231039628 341345547 745029193 781220034 929792682 871876775 544376258 831802980 193831408 546917774 701429970 951324497 460523697 900834816 726576995 559894420 861891007 371094770 330266112 740531078 48056824 895723215 598668893 443691838 818133341 807528688 257561244 143573164 324832699 870070636 322786509 916799471 12747311 889580244 168635110 798109549 836428583 829921093 325040429 260898331 428533108 829339081 293085116 906890534 380445714 236454631 683995625 425302405 677236774 35993893 20125450 523909908 565591919 804599531 518731093 431624099 740534036 434593826 330827179 328474737 487299265 241241822 163113745 236655079 603527053 746900091 148520093 524110979 128247021 678045684 881951033 411943344 980241660 805297940 832227921 455818837 77986811 753456453 531584743 214310916 36272121 86448660 957758988 210943645 407942132 665372278 804722794 636417340 892372569 424720894 787927689 563510255 609722944 677824035 725329972 580069781 869092928 400092292 456935005 171363881 535230896 510548585 19475711 468232695 55815208 640016644 372828288 136151997 157176149 316220954 487373872 435401303 670836065 445206307 111109618 435932874 922998960 243819548 836910938 612871413 182286045 593736950 119393425 133112622 71734343 722470382 889273371 501341640 995691239 981327667 941902118 141196594 834433536 648474451 271202616 299861792 807219152 258687668 541515873 265065715 867501101 28366379 986860519 582164965 835812734 989399390 163640578 797926121 501155321 828112234 672601253 190010144 640458614 136530247 971858967 443161567 379132532 376371795 664119418 223003672 819729526 753160714 179063263 557949498 3927543 176999240 217357134 571110891 218830195 272092108 29164717 384455059 561266574 372390767 281577745 253312851 239624120 776851913 615581151 527686622 550909252 408561667 401079719 607317187 581034609 154251122 863021064 863232507 916522446 673651756 914219954 671507367 485130035 752239822 103126810 240399332 842066775 791918878 594705226 389721705 519271083 132100450 887638254 870852573 793848344 28079153 256755012 18419499 125579606 753148680 622763450 371619205 451354237 313694504 793844206 243805893 75471707 905178047 209710186 895775540 80062077 686037043 10108979 4535492 526132669 165127629 816256469 362527388 21479577 285946113 524730964 927365102 367478774 987329471 981229731 877904538 668087089 733609284 722848358 375959384 111523253 150617198 432587062 813455155 938522696 774767985 355278933 926404 721177657 615147375 933742279 893848299 358262786 241115715 170167986 931290735 668983557 39376767 105148084 966306502 630153658 928982941 621040338 83271486 661961338 819479943 403255328 455613451 602254034 139001865 930103212 544761121 246737811 550694748 31869613 211260436 567684446 397908075 711610042 558196114 306724206 246129601 137948609 588622701 365838382 521354972 745005099 534499148 116566594 106645100 394092260 132600279 787403484 303463586 607684260 371080931 289737084 357906130 391780534 670141998 908562414 104201970 439071522 93229491 544057227 27394072 747786061 710725446 859401562 965496760 438651626 68037210 91860659 735754120 789015846 954493079 771886280 237654767 647345704 853639944 451266633 932838099 230162207 610184090 18374237 935693996 21064218 955897443 15499953 243291645 965055798 662395806 973147102 398008633 376067498 773640436 646578250 818263836 250003100 530831191 537607226 824241839 663738730 935186106 244216325 713001294 29482221 273367918 262231175 556509878 684332222 840695151 50235798 236427304 199782453 246398255 45827700 963044738 629268644 322218904 353537835 750857586 120990158 456950304 706243142 21830926 307142627 893332746 537393651 301851434 671009978 389299267 580332869 447523 856456339 361635779 651469856 448605503 54402483 442482589 652724470 67467087 366887400 712933600 394591714 959208968 455071898 187684989 935266322 49104881 406164629 388951099 196274222 566341710 80212863 849953935 639379759 197104050 926261588 383078117 338405519 582784905 185304665 204502973 526143957 309802276 245379975 271580825 309522291 718271132 247884663 746608531 897823101 194971736 82202767 340623692 250464678 457960929 138300927 31260476 371372694 259537576 903277081 139263806 224357242 240666958 532133674 789595013 352290424 401723130 4451078 37885851 723599821 871479342 606084345 674504343 524549989 631751111 714417065 355440540 535346415 774554168 968044109 307605632 560678912 355007708 638799552 21118583 238767581 967648087 612883512 174234238 727651359 609057677 613123585 930574259 968888110 221799383 573473857 621221642 449323860 568380717 694977483 720340876 930647343 496167977 606693023 60955213 719811347 371115907 818898921 581250570 364973263 734372513 486153819 795749261 306928219 976517397 540732384 427994053 503650325 161565844 747179874 655813244 972578587 240415641 165814213 569368872 308452903 996524315 345135226 913544263 980574009 837292684 221174045 588811351 644214597 692748538 288477428 620687556 593296884 18277904 732854282 754638789 797288040 471948977 184903387 254654250 121969991 27081168 934367320 910115728 376477639 45303308 21918017 97199738 149568747 26493890 531821046 438262039 9498091 941877164 510972893 399720616 796377375 940870897 128853875 883487554 580979577 833758920 11237784 289556541 660531145 909537025 34600729 587683117 792956851 511121201 12572396 215388638 121350416 714384412 740525083 399216954 160963589 375779992 945905278 845174044 695236775 253736079 602267464 74557740 119948100 53894784 361172156 477360821 733718443 490517143 253907883 8446844 571658522 62668893 292130879 336345697 610032008 741806885 683818843 166014391 912544781 180012297 601130266 271733585 465088392 649778785 770517079 374111150 546767311 851646879 181418892 989318380 699010996 268016954 74720602 371379795 926407388 10610075 257152551 613221620 285717802 874745839 798301712 958409531 592516298 183428223 71459898 818413090 717960222 287538214 700551292 7470239 613623258 786298925 935332827 6359725 310090810 149430854 533120159 591916319 801982033 447263701 225171569 338621511 477766828 426067361 648367700 50706892 4648070 822775683 280786605 664116277 203150374 720684487 566642472 471242194 682869735 444432468 713130526 579109753 971488345 401186747 72806453 118297421 219765018 683722408 475044179 614600714 55687709 998971575 843929432 49100895 729589820 708940963 44258655 344007630 536787130 332136 430021367 421912590 709124866 697434574 786659860 37174470 589158553 648161695 71984183 525165200 245879885 541289083 738815463 995485263 184974717 423753110 708115035 376546729 92987430 966449023 468060837 14303462 366631410 438418543 223524851 279558958 892697368 718417327 326453517 855222302 840979062 408294206 723765696 97646914 667853449 540585692 466561662 950730300 847300532 845608523 328429450 102444676 835046781 987085438 831507284 759231417 34874403 358963371 588847807 54887515 942829231 546855935 591665514 292756191 215267820 926809066 356814000 742905487 140193261 42225566 24184823 341417610 339514539 963840800 823930170 348275176 842377180 905295356 605356433 203010317 145316683 723268917 21209630 431767744 234229981 335160066 89603139 300225644 742245131 916838555 322091871 572976011 949884756 880123384 574523456 437328130 219086550 54199393 692628320 692779288 425895581 98161360 47451798 731709755 959720668 45566951 118256208 623709853 259824801 102235475 384561385 670963103 666008351 81631844 477772152 496507323 551587315 824023799 554006433 699699869 870788953 5263972 77818410 77191104 684662981 124647069 791125160 539744656 940065924 437730390 377240558 782813619 221016616 302252869 730899312 866828895 493406180 650247586 96553178 783604063 442479269 42414641 389422756 744515205 841677541 752398597 403260387 485389598 191595275 714511970 97706229 579211267 623418981 841389674 782498202 735090029 154443233 298602573 114861310 25639435 347675992 966967291 991133315 845165970 717672378 372388316 250580563 470871462 876412601 982500231 62167852 757094293 442459477 235672146 98000678 568558554 319632223 217240046 676959640 354180728 105963601 629213031 652561075 482917413 110544613 157847815 878653020 803964375 85160865 588964298 750098697 223833493 476479016 725757712 86338949 483445330 796815828 371532014 78476332 995708899 164246268 430633966 342579896 360377576 434095802 701577847 730635491 491387247 226542033 270552259 709659010 406569189 729349885 788073128 926443771 662739723 251039404 144690744 416881838 493095743 136934589 464419705 540120240 761873702 700167090 994865830 469215842 483614391 850175191 306801177 41358452 122586630 207172533 442107870 389242086 289655908 854377711 863052692 342220943 522103123 844612813 663421284 674726990 463335537 609656956 747210143 341729379 339507449 542082546 275603344 314931400 534764255 556941254 467713405 419450221 839501230 17502073 7765053 268453561 764976843 292501921 340191112 596047757 275036619 613855569 895287214 782085241 337441167 691176032 676139657 807253431 111930919 903327194 443296768 767061314 344596904 642611905 219207569 604024315 431903477 97823179 24170567 384520433 497882191 813280146 206083005 291893045 714353169 581154644 616354190 610687174 314225734 444920422 438997600 863378899 625954422 118802810 815736589 990686499 343231015 41667724 82979879 975997546 891868621 719118087 345905295 491106327 538663598 306346118 881231093 247504527 239653828 917426186 657871681 171302339 625659933 439444404 201497881 371738871 611268599 334650679 877573692 56556832 844273814 381659854 613541506 594777059 790359484 538766884 368127193 675822542 240090495 668575105 645688802 38064903 359854808 386306502 413582380 631312968 64223471 444657562 560949363 381690322 637909114 133577073 583406936 5446706 567311384 598350815 206574730 819248700 91900990 232480790 501998974 738122873 318436400 945622988 56886108 874919818 841218851 902283272 278166654 825618438 891100426 654682018 802958346 680290807 351805226 653994153 994338161 839175530 882282949 73045638 116284171 837419040 272012537 242789719 435263945 226961918 942346365 940334826 895597818 59290491 810521309 816104836 498346123 467376660 386414355 520748829 9346923 39540160 485967905 93347154 831317901 610820092 97692106 9881263 222990730 549493134 723992304 318330706 16177932 579595332 564630330 171654500 88366108 187266148 124995921 780763713 523728783 512830256 263940004 523687021 257763805 589143171 53531268 392559374 90248411 468504683 764733120 920654403 140063724 206345596 554775655 56376329 31511756 939682518 755140504 26705154 846823889 493709547 559196274 86851382 666912950 637261252 51005844 726129329 721265395 456996146 7795961 54620768 531660869 306037018 824308785 511755025 469014745 421443880 44994940 399300379 831646502 618852571 569494365 508682124 970688850 804598064 672746049 42248621 214003672 53362320 186842809 937700921 97046602 67436512 507779175 639955157 268558663 701622665 226804175 632437323 875670649 168337764 251988115 534791468 942872132 407716081 972062652 450634261 753172795 969037746 6829301 867673242 310387102 339043676 796257800 328165920 38901393 883819227 783377793 676489781 812858948 597132619 860593780 279554275 855605270 407131183 763292887 938914529 58322453 881167098 236829407 350432474 97153581 864565863 472779855 489804023 653719890 334151760 702904070 771997811 774606989 952070515 250881308 253090912 860080732 626977859 39889128 280657993 587871591 589842660 666926182 622118360 782976743 311751794 964744024 80404972 224515756 807544426 338690628 786086130 825509999 257660606 154590639 65893071 435472208 981643251 807289674 617593739 712554693 218511530 578228516 649444030 715018661 585838670 908997166 365213718 134624561 98647183 188788116 392802353 34313999 347523101 860774921 219526259 374230504 682241595 369708642 697356660 304194803 988958850 147687694 122938457 545701475 397807276 912386457 177780681 782012126 726481652 796157766 415765369 378306126 845054171 78189813 355942496 458115553 583822303 708289486 843028656 769178411 975841993 302043307 647335670 264204197 404044649 43650359 553466062 851120191 690409150 71636803 50221272 252122839 967429009 750511343 295870570 36806929 448240811 721019393 862633217 179573793 395017036 890134470 911759405 288986714 296028757 765342626 410562834 458392113 759485215 48765055 869290223 264260872 859957430 557866531 19532030 499230534 775094630 658018626 99408601 990517030 460985579 772160583 734578605 818030327 349942813 217973134 449788968 945776499 960537274 884352583 680595046 232611107 337664968 831187162 787748853 616154305 528652335 75067591 216406216 988748189 372294154 832282644 379993943 869869751 828677313 719470566 570293682 853533057 748485496 696256767 781823341 260251353 770782634 164822886 123213992 807867949 37924436 375462415 774150023 643110617 740689691 712656060 557626550 69781585 323944408 761391103 668286571 401142271 911195264 500291022 60761071 593764319 610902559 972703025 755838112 29270353 454266881 31949538 512447990 331650695 803562690 246984777 145498731 680084795 584568917 474727980 598456040 479353313 792882626 432529863 798146649 199756101 877452438 135924518 981759574 870217089 670160987 415118828 350949804 494406612 605611094 658981736 53859032 79714628 32905548 525691849 202789732 461863025 473559962 213546902 989114433 838267261 408414968 737916573 459893237 179006919 936659028 514696178 379078225 887170785 645616205 63763750 971688887 279134125 839971005 291145463 476188356 206556092 886997272 210026117 515107562 299637553 987352742 306978411 843031029 532836036 33209916 105269127 213267304 208992730 909039105 248139594 653174506 781690083 505985895 45383521 445487332 756180017 519188502 279871053 132678480 705533393 300856264 552933442 821132936 888006881 337158557 96561116 872290009 283775838 432061818 902192475 357453966 61879452 862690189 895258087 561270588 642449895 968808389 847578554 169502743 707001286 18060328 12467660 306062568 364995074 625188132 400698148 385146481 605191768 245860337 263410503 237429006 5804825 804881328 141769445 832900099 214398438 469974889 774932396 481833654 475057801 425238846 444016361 250649909 536672068 161295529 310776093 649821086 806124209 936430270 819510254 805271591 754111860 646198819 881489378 59688965 831948400 957352957 950302812 926246612 110968681 621111811 992343031 767549787 730558286 522880242 735452473 392835936 746253371 645554338 233896194 192793131 326129475 78871759 279069050 217137637 993500855 998282681 850514570 628695842 955330469 9251785 312366457 759313970 113375224 729526159 279169542 45631155 257527376 347021151 281005802 140375004 902753655 104815984 223734881 623711296 836575470 545533288 564554072 803768171 62528941 341045275 765059385 431548868 551691348 103764783 743015816 703718816 988199595 226261642 457418913 377408888 329016287 671779260 641303736 401815794 955806025 872904869 429915300 813772252 859103638 674743756 778832480 558511544 749508651 331325068 291038406 353023156 400904049 994290869 681247532 795418474 293519511 216872306 762000862 634254130 233704493 772406726 20361986 614387691 424954955 384184840 563901 591449043 94452071 216477235 433917855 166588314 360685368 722933996 388806893 341501359 273033401 474124917 283196857 976094600 91907572 746768346 140687345 953428138 206339814 292662762 296646530 791270784 698347422 690623485 253579401 647221469 238096596 576468996 967557875 466913425 333793362 179147402 467152198 471074837 367697894 202464654 539278292 544340325 707112844 291883203 622603474 597178342 310581503 40918624 288699805 350526482 109590223 159638787 788613999 917652847 15273384 346665949 776476999 492685351 739818594 864702964 896328354 651955615 805608341 503380055 927310646 220610808 257938761 818792565 414659451 659511418 914747562 104177774 284283825 487344780 409794618 17105549 835428535 33660071 338057825 951816353 704251299 260503440 679534813 643471321 400843204 33211767 690286335 241693322 21120260 882200416 949759032 129341437 1198480 751405810 190641419 100577321 919086997 953046572 331441789 232269152 228522095 809660800 467305768 533744294 591374765 527243516 812942285 378844380 495165146 770540479 739358628 822535468 33318797 745083299 22951438 297896233 197143237 234249049 355402149 211818894 118081367 921298644 202307326 946477312 754090416 624327422 21858878 258462974 194056272 123534172 12425205 680718898 177288050 968641469 144523205 178003842 466366371 791895246 791436263 533984842 727117153 608181047 746820232 13462258 833147817 462699477 129253774 771526467 703061144 80707609 4265117 167650712 246069494 176844482 969452227 307852627 484673927 250207831 869336660 544886936 127176691 414381382 60021654 227538325 381939074 243941786 106684970 95279791 293924701 727369877 207623831 671114884 643744181 466447146 891067523 166399059 694944417 538232606 143057048 188783333 476482356 6362866 57397040 537637087 50211482 285818996 765526438 82092973 718654893 355813044 259772913 752765698 481500586 563076323 643586013 373435489 337040049 104381867 52037716 437190836 35808165 500779394 740993733 332129857 49921368 605344291 474912350 495188548 791396708 378276291 156811222 13143218 883055353 197905649 258858387 927131409 805900632 20681380 664390500 814458011 881657229 186992702 922530302 770694596 914510139 393436284 30663953 797932368 386738438 750314336 891804883 617431789 745282923 241077579 895672885 975460659 243319721 81382035 413703716 343313345 253411630 742529715 315576558 501094867 216094340 42441848 132152261 680687330 351234601 403713992 207532388 491207701 200809238 674225406 529414101 71750777 474342120 956665081 849546256 352995970 309154725 175413904 909010084 957116903 881132961 15264529 745144089 653411135 807155756 508986590 693232043 864004919 900836786 115191043 461461300 564985511 844321504 247220004 165998581 45256570 620683751 664076538 38832887 444965859 895310797 917863106 543659251 639149128 516764469 557845588 387839455 948829361 445228882 588690860 174207646 628537795 788606027 956952421 941599301 98269191 119788690 322459632 715320403 450407194 925682254 554564662 72673076 493542125 194548804 637232840 627619954 630961236 561600434 275104685 485865917 335444467 41876178 51806446 911169435 636391126 194779477 151978706 157582515 948198672 557854949 606622211 779745993 938955933 292633088 371826260 626061814 786178959 589927575 302093795 417456595 569851143 159996237 417416288 207822701 125658107 127195013 989039890 416450725 412354705 493570057 919209221 966234968 40872094 137881879 210982468 474432291 477524181 425335417 903036825 414911922 738448728 527134705 297000588 879465537 318960445 436470541 559150543 143061291 360620078 272943452 40401295 62437748 287194578 446016686 505256509 273852956 173196560 353953517 751291292 128535149 432053150 628096389 919568155 75050377 254603978 830325615 451359638 953693637 144642723 289963295 888984718 947925559 831498955 257421974 259785960 607128065 770763485 408781329 791408774 337558651 895042787 792241493 778315824 338967643 589395877 639166311 648663790 454412717 330088872 227957769 498688925 241862785 632916173 654162621 814997755 145963322 910732120 905662315 60651320 94609773 157917942 714551079 647623485 367412707 620129789 804639199 158455598 474990264 879360348 279068470 830908192 979958849 621564436 531488017 726819460 85556197 267073084 662142283 250195528 457901921 195260298 767306404 434429529 146365442 378664053 265544663 295456750 584644488 558830883 659112905 911778619 472254194 479435501 479391294 600519231 65707015 269213249 647441984 648327937 227823010 833127087 433667690 788021964 541160298 488346835 104139182 122556848 570080337 475068706 708566445 338940366 146595432 719569358 612704974 219103232 892512615 971048634 373782952 424595653 178383768 447026241 96773830 141967347 521942574 364613612 228286126 459209098 135412839 304469385 223419514 257088865 880159768 814717867 153364839 573078441 508738620 202085510 678746193 454328606 909369708 818201010 269303475 925163900 672469058 537040407 51295001 45974361 274113034 27920315 595358838 389982141 565164138 659962349 157854599 73350611 452640756 245315205 650681632 522506989 316570397 849672601 626191958 999044863 611468854 983209117 155250751 868650039 648850172 862331239 46507670 290080002 986285626 849505679 472156727 87522016 459826420 761704564 918636426 584523459 509422517 257192546 247257270 823326793 455033568 844329035 76862141 678371420 870191084 973774085 842159439 239659078 307967901 413662741 375723384 444528860 7552667 286389847 522982105 43792021 258905762 483117197 509450346 645445445 176926000 579745499 356431317 950668791 731489684 760148691 563501998 171698980 838460699 573158027 519191467 339567402 955806482 948603578 582092339 72762545 456933001 836516167 677849219 290589266 696086822 670511923 769125967 8491074 935017455 557197991 551902931 730269771 338965690 470337587 340726476 572434255 317088583 592258032 218148568 244858882 325112406 759790313 923516299 729508335 283556100 569758940 253988904 239426602 370566605 749976226 384500307 643405011 507944452 697683360 24693840 535870915 714935108 119559957 743470549 973681170 64950826 584043171 273963061 885888613 545785230 632057225 889590321 141051987 713561521 407497294 115965155 851647031 482794650 413667876 200392580 393302372 212096703 292326671 994887475 55416743 59456578 233140946 621178235 948719829 353571097 949104273 59634087 344955424 209661533 749296247 890024645 938436989 681413393 235737206 772076219 753981678 975863104 833254 6604460 964338026 744486300 991248145 397703867 282262246 222240781 919836740 873401355 678077598 290262266 398558998 93189314 327207244 939667243 86614549 338825368 265595958 62658306 741874383 845815768 717210418 795204823 867808247 438996192 380990432 388675381 427307650 543397017 945746109 954619215 451193643 708172619 356256845 639422152 961179008 160405647 745254282 272027933 806102340 371911708 476062973 137078776 131162889 333844340 543559868 777679030 183608782 979698677 36132254 512396496 416343986 191133087 695519083 699841676 409939084 919577188 581954823 299549371 75635320 405768774 401326293 668464464 564511291 592333632 401040445 719435148 921990846 878852005 924720805 644075318 719480557 311231939 526035940 963723399 460799283 558682576 696489894 527845665 853739195 258519919 415987354 293505658 517169786 462283599 624247453 599101417 806688911 503005568 597869468 296384021 700956377 957316969 844293551 842326914 14986898 73847191 567924963 490653051 815242315 963083545 738481795 126895440 618011057 201258037 580115776 77030352 737761256 65718863 138363828 870520200 98727382 504476821 917623240 138512864 135391498 694334004 719900906 418766683 949521321 899762181 370563150 534907437 644352320 408477159 897053768 907348037 223905848 465516647 377645415 289721859 477385931 361574246 37866818 282614151 316063395 65950426 73712010 16747484 358828212 223032315 447125059 401018577 657428833 333468610 394507806 384966514 825774148 163233042 227493303 226518415 839864321 512951359 936734921 129646300 616234903 678656135 232076011 138953159 170640445 281151411 206625038 932760678 58600394 647181773 791880524 137796989 376746541 331697958 485426121 195011712 274543953 216273457 121168364 496124409 49659850 69771325 369641146 188642443 48942557 661913407 756337569 502565671 240442910 603800088 808259654 996373057 185708164 911568179 654265658 104364369 875242106 826609698 698248130 54850925 391105311 460571336 109326288 335953062 88207168 987782467 986068921 454719701 973849967 338174829 213187312 382782689 18022692 159831849 317922722 118973945 645276406 638250401 74595873 100058636 204912550 494532706 412912764 34092545 41885062 386486523 516139316 48259118 883952369 822280714 919561914 169715137 737425972 627099115 536544720 19762299 648183078 832855648 197059148 64721400 199950437 795006397 759604275 944751386 179932986 512741701 470478256 883574930 501344497 110588850 289529982 396996407 70344408 747968076 472475189 60179823 688988149 728492032 687499293 672215387 559570303 18257108 390188461 748181221 101659373 324126902 967414773 277684023 183628117 617312320 196655610 623266999 115004325 729841425 799053901 527614078 872732124 108492628 269011317 349855102 338355678 28826258 432637836 474651194 525184847 903455129 66030493 568256941 959182246 315613573 627879363 511814941 146101342 832902316 364721459 373993577 468991320 389123199 672712703 727638001 324889599 616747423 957683624 660806639 768586632 256126956 202917656 253042110 607039160 696750798 219382588 350478247 919920173 181941765 629130889 994748761 559159312 538127154 987875815 202919036 34047480 208738466 984892249 58395212 871146171 394236743 693484827 874760872 996038678 190140615 940115109 800335939 840435262 681974424 48277495 320076877 334905156 433498380 172162606 975561417 642976081 984383057 884208614 858040189 71404973 326035236 482642850 737273999 926138769 728941281 891971539 589695705 841575073 51178622 92603497 23363327 897578483 421230219 568752775 928861339 883429556 413372368 404115010 651346705 29280124 788092633 141767297 980972110 328935381 773167831 554137881 698002058 179477820 256022362 762137878 266784632 595271824 944667409 241963724 643601332 728488443 778169026 922851084 352930685 56159537 331841826 597530483 782196608 177696673 405009489 659672154 914353193 149277192 745775033 835413098 832597143 424212800 881603027 970446991 664939665 382614651 885797994 934638383 939173786 342422893 569521673 579297448 647923840 946645366 150858603 811819374 968092449 339235526 632837640 197056433 267938640 766205104 985993865 897419197 339160438 517654756 802671179 420949683 986497007 554235464 336401020 718801790 852758727 407516470 90251560 440814482 508189020 446004707 122893356 163172276 36615356 920540703 383104041 708317306 759123576 559290516 739169545 178687572 338790357 424474487 60670216 491882471 96332869 801752522 466215057 410186578 633033602 867564169 877123117 249501396 217513107 117188191 442417649 254237665 223197236 648453487 870343089 723771207 128015789 332433908 408108284 439980119 596663688 200306850 809126422 736037726 467781410 258832115 889691704 923647580 436850733 914775213 117270595 816078939 394975895 787051966 13533076 173468579 785948288 867006334 483230032 229447680 77609488 99875048 220648557 968047736 154973490 858112463 878740445 710176661 562045887 601765328 546475226 857176875 915817561 693248032 506994431 839597204 901549606 214617321 241285077 627985829 263965061 955467041 645666635 718761933 441987781 423698046 629883384 409215845 625090709 121303051 861993738 589110482 388117044 770624434 576934366 251010324 896872087 249478420 914494482 680207481 797824930 927443710 31920221 749820557 836466355 809085228 72149993 104505036 545102884 874564200 307714320 172337677 441156174 378667906 278889554 48246299 768829717 319600889 613276138 341328030 829129101 230626038 985682975 947558301 631226848 534121976 708906126 46939155 873648456 732894748 187428317 783367045 43787920 781758391 968169874 166461761 661421626 856480235 605041578 379536274 215052499 990415506 523247985 546638886 322625151 568980579 195248404 326492297 847508509 94700664 718941329 5357637 913936126 679035675 521964794 920258232 707720951 112171190 220542546 798681647 154477825 114092350 841829755 833406805 438863782 834528921 802033550 27824004 979836013 938224765 417003998 449442376 502481205 47591987 792136398 242046872 587278928 439780060 92992801 749655695 441997150 94256001 379114951 150331504 507903382 494714063 964278826 666485450 573776840 771628447 757180325 395103490 652991652 788633957 248401053 110375441 572798477 144701095 587279666 205194246 909072856 711529879 728223665 789890022 497506098 693953055 621203329 939340251 588575634 343414565 312680280 948447002 236667832 730486650 686270121 763968587 290438344 981641941 826237122 950932465 931958762 561710137 22026472 78430068 850299863 779650927 137998187 864464532 495431405 632642114 430694536 999677412 63939837 498830419 907526359 793053083 750004215 337064259 652339503 141589397 565645142 700076268 786198773 815309495 324453423 613069768 788711828 45568763 759360781 218412004 819485030 24669266 633366322 691080497 781141724 449534539 243833874 508061991 577987476 511891176 452749290 162223179 812814642 665049556 259126082 688771426 188060707 215537133 123454493 527992899 40543982 808728289 899730981 194571251 831657261 389464514 425293911 32474190 595681454 392576784 340159798 194868845 344159175 480389268 958058936 830549017 165388699 266158254 781856326 95279728 779058883 962467590 785701076 18330394 511390633 696472070 428872353 240325510 473669816 605318921 564747685 130624023 204439156 840503504 250596005 245109972 816305720 94040848 194208101 918542674 455376438 14408021 601312142 563129805 924174741 992144589 832675153 627580886 414765097 984344123 465840897 821422826 19698956 725420471 498021089 703487791 793215203 251532891 916412533 610812838 957420217 658480168 607774374 45829799 853996880 947423326 402345344 206261265 763395463 724502555 971552390 213369577 68418187 368094621 774513022 634310621 637328954 295495556 349136964 769783515 460918035 684367852 125481761 121092028 207584704 144701357 754016895 929183356 119179854 257006374 562122786 251207023 263927787 233513264 165582356 326391806 732619014 643940897 744721241 851696087 239417892 803940233 706510519 635568043 490790740 322343207 778374121 740750738 645529195 429449978 657971122 292952907 775905368 415483155 192272665 35442870 345764756 798142 463877661 526713978 310506638 142366477 246029501 569580269 756513293 507693088 690331402 941812650 240476483 501127363 68805112 99612466 669930612 798538058 528957586 741236022 992796699 347383918 641645120 518581329 59778758 856068182 323122787 403243712 936907003 112169860 151192751 718975381 220368184 52668047 342065209 345212953 376343979 135197018 317548617 106900384 734333164 138066318 331395951 281666090 86006148 421167905 963597844 688860480 58086715 7524041 237771535 602996018 150523313 899112406 302222880 872774102 934424550 339915691 755998367 785346985 917958350 510371713 502679268 320021057 252443114 81964966 106665086 928097623 796566470 535748089 705262896 231702859 124653179 676406035 845004032 781187366 542189250 325396069 506855421 362456000 805133937 569076991 914808815 132649335 537882815 997138067 572072998 534729804 112667948 464162829 13724239 257289994 56113179 669559804 181381060 993753376 515098307 876035243 294430729 211385986 141758786 946852089 353102634 357505358 37234282 538908382 453450963 632266680 625483700 838671091 807702124 343691074 608177092 236358672 678979516 171174232 743841880 205494808 764523167 958011697 275104092 735325082 216908049 228916780 528309670 745817448 803831231 480167191 619989920 452121505 304769436 287994775 268815265 161347370 679075686