24261 92451 246507355758803932
491771660 630149713 688652616 250729676 898531291 264711516 65433110 404883285 955517742 43800849 899513320 245958825 947406048 303897167 397474165 504668747 188234580 446838928 901768352 853510651 805720251 672970535 513671092 187731695 920398413 924469377 39252135 573274907 82506636 110383462 144398425 128552043 281952134 110866486 937811924 856962566 82845202 827070509 275951499 804593546 716207375 515968673 433941148 134281300 86447018 701926464 335863312 319147191 241178518 836597333 216335896 47923009 189975123 491460610 467345231 928187387 113532521 629219717 331529212 520062375 8027307 795175796 40963918 164291842 574776183 983847938 415890592 909017089 606242290 217086010 65876148 357494037 479747407 866507584 696624378 332584041 43078150 621993877 525552328 71384864 958035742 824196177 364686496 311327897 653938533 697431657 10682223 953406893 424725684 71904744 45243337 457702893 853030701 790750519 636953904 880207590 910264446 222761559 282455372 548605278 412585758 69647906 240795442 217770646 413519757 845878672 170576031 939006855 856580501 446621422 456110908 186816551 748959117 105361702 839726553 776963747 674980242 517416699 464209843 867329188 520399565 68283467 852955055 227361932 782567090 834892621 64330654 445295799 420841021 212174802 666211706 899919549 636619572 272647814 392731813 156369068 746434409 967903790 277205294 912292431 974654967 611745001 918236428 571782251 418308738 98058097 777392995 450357759 140216441 418472025 400988092 356065665 290415189 513425742 212286798 255083045 667669209 314291799 383005754 12554519 471211601 511122710 793254600 717634237 384234965 994795014 91273388 546852343 923546245 335143869 529541701 416588129 660512971 297438761 657037786 712409742 120824222 545387476 375591133 706182476 297093051 766702370 931989289 689368803 122545388 942487952 933216838 443080023 494940995 851704564 383218337 165658276 811831900 377165505 587486422 825254911 850223776 551228737 521265384 933251353 988332671 165268187 644379013 69568348 114514866 247771468 646341956 399038765 799620737 660431599 433845736 808184106 11195640 808209911 564433308 698786668 676227633 304705458 292587062 186261187 381486991 433685957 790924406 71761918 422688766 150702964 421873989 715738402 248974134 43043032 589655800 423042224 743402743 672852008 140895885 853137121 845929548 326917875 102402282 7918315 742019786 18026850 876725795 29045307 38093263 653398904 402881714 455167929 749916613 258640979 823375550 824903433 333628254 899908970 651757911 195962310 671973591 240997838 185351093 800249031 76761911 440358763 923611261 133806428 857322382 845591110 857660158 244878992 237709880 40214974 404558958 923199078 973176346 136851916 264942895 955113245 404598241 798218308 87340046 239351917 613959495 693319188 953681791 713076937 617737296 634537602 272264932 893607580 421759110 371358320 24351685 576051598 225261122 43552665 948810007 979018175 643810788 366702546 411230327 941427976 596991767 769012812 688270702 397954110 437175312 116085454 531716780 695067248 301356750 153588476 89935182 814813222 906501209 70856597 525065753 1617569 73557508 238361006 499377854 598021920 268699308 153522682 901051158 874581526 735927288 763453955 345004646 194471542 589242265 896787823 265503898 884544234 511447689 931306301 893744010 52925716 179977293 596747015 135708729 636821717 66779701 365000256 160925714 487156612 48386200 778338165 566280236 966187828 197535259 382646157 794003077 616717809 574458088 677449995 230278472 675691776 2312697 620163912 313908233 714688548 444065356 948852155 693708036 71028437 520532525 581529395 590734435 612724104 185906801 415610136 335421303 353762028 502569399 48104111 366496252 604012329 234646951 349256789 407502679 258993440 10742836 374525633 41751001 817991087 320377563 91797060 233854458 787562732 412297188 428112905 27292576 965760871 288338845 915803479 880819544 365857642 143798180 65538252 53469081 810806842 762241563 776609 889069574 855998805 888462579 874280170 321073834 66705843 437766948 667220180 556429115 39719686 905922032 569085415 869590617 780779260 655605797 463755332 85412045 910794361 992168281 772661990 483235532 445660896 799187246 50092770 700481332 377556809 843273869 262240424 176512203 750943177 158241004 626001217 37846405 951038127 382043018 77160849 922690492 380237762 246480559 485303188 753827191 691473286 695962351 164262818 745454501 895154806 556899941 762128812 902050657 434987592 741014010 903581822 784961325 283054382 693330589 805695229 466035769 977940753 921686665 308554088 458623386 132081878 325976196 159912089 329243541 902155674 120029980 548677955 613852371 80667639 314432490 156491570 576437164 510841151 43414736 731865232 823889759 478224573 405306684 803716380 544548181 218346233 821875045 817028466 461313123 901897458 792896394 819323976 894774790 546813795 380220728 469315500 721498534 727859200 22412418 129989193 564098517 541481144 766260552 597690016 620291471 843772658 460873331 773781073 733332346 12193489 776756532 429997905 574659365 175682674 734770250 658438451 693301322 500176683 685456186 154227298 836657677 383124683 494242711 140258658 229188668 246519518 845290553 828413460 498488462 168329704 778660999 65417968 157949926 740285607 649196463 957224522 443604368 146460498 184776170 305481615 640267392 589189854 323738043 531137159 398882967 164255285 920965422 475416210 646964191 163543935 191302427 144316909 138417100 706309979 805217377 671265516 557121658 726346788 289427757 56335167 9829363 602288942 390352947 285749551 608042856 873452551 269169137 625131743 15718005 406240184 787306480 332715405 597107807 585053188 906457092 831682768 16830806 657740454 962977161 497547737 256997301 704190612 628395686 107963572 759339839 562157376 877178763 936460165 588412514 453498834 689380276 476035021 690627445 270582385 346597157 799730085 355813882 890176889 294495149 662905087 245688286 54273732 709902373 679072490 156015798 273076963 58991536 107042508 756025602 541426788 497913082 920658855 363622252 892781323 770873723 732762966 212343815 620455194 541125299 786382798 898295697 248241291 981028205 467043424 232299699 126318674 272972542 58629875 911547709 203631517 309528708 926441804 562456941 878749973 602584616 997679687 942974246 790026781 623089758 132893468 11271995 278474767 722602274 738821277 767961251 487198084 308006203 990752884 278375364 659308426 741873530 721836647 600927146 786388717 776161785 136266134 443116366 696300400 152064349 561678777 851475153 89705235 624815637 834051171 539157696 100881740 835813787 675421251 264520527 571834959 734547376 837834848 699756960 102570569 565415329 690048858 759056123 144629918 200085894 16486062 607606293 696220464 759705471 277702640 566492235 342874520 966010615 866631183 237741285 714861164 525648867 994539670 211103829 36375674 174202881 736790759 745083255 450492937 392763931 972351872 669634257 767043612 931050307 509723447 158325201 872406959 715596822 676420223 458482708 455128826 778106363 691231907 506868379 850910891 117809763 283580168 142113045 410908974 817274888 29997676 722765593 159073254 246485551 515742763 41438570 851312754 568059368 318518646 770332979 860503019 704699722 572271259 518880587 795949090 28658362 128881730 760306032 521713892 448217634 395292844 87733645 375917367 427692091 861138676 228627701 263456412 590988230 870607951 457761191 384610893 465761484 700541773 219319690 191794813 303507939 883175703 484683184 629738909 155124585 301800113 846010260 133134739 634314440 904951863 192651869 516459266 613420467 442832929 5394459 96554118 94384997 274112128 989312774 629887990 372034534 682887232 632709828 197916067 54418247 583935078 479722914 150985109 675338466 228533586 727860183 360244434 70226589 337916923 735321286 485038745 993702949 535737143 812450873 781196192 803199029 64669426 548158376 551468379 847882190 16525171 281016178 400218934 125831038 15833244 690214945 595098071 838876315 126343465 393247656 611344991 265108615 60615661 548281509 921611175 698773995 977756954 901140897 277152645 799621629 787145079 312942668 186320902 861611964 467846057 88547524 720581811 373536560 326542701 394084556 460806606 557840556 395871449 383295255 722819987 838063630 578099104 682212988 425691514 468712955 61328972 390360384 419899249 935653157 710240132 925533778 618458403 943367046 283058501 411157127 27758389 474463652 484069419 839756260 65064069 35524045 984301223 666271442 319976300 836954 647534151 849737065 179880187 749976557 972899571 821725351 945891390 74530484 987336235 433437112 665941374 581879206 507415628 184888109 582536056 726367938 769823690 101302854 172059305 354004309 656511605 130538539 792281731 971907890 32543414 683631916 921352886 518374393 456751312 385575430 500475498 105463890 319662113 37160734 753002881 603026737 9272928 951846341 627887063 539554577 42480350 73078644 839915651 72064315 17236935 498875663 69205781 647083774 450922336 316920868 286577880 411348725 985772872 857658410 307080207 578997830 355870136 139586500 399268153 817129439 311629509 803206141 352563278 529716153 810337690 344703372 975939073 304416791 500754369 91828751 932746493 183162053 105038424 496293201 368838954 172268634 97800030 828066949 380910824 894335352 647653605 482850698 220283984 898668553 239116382 898368039 584964216 738089089 269576147 673371469 539476653 15246624 829383973 639124570 378011063 233662767 846044500 528511058 47208730 583986240 400111029 290207014 179617361 141542767 859233595 667391726 776986131 565778597 652475824 735674160 730838416 724157393 411851514 906371609 752265139 947407407 158141528 952832448 866185822 960435075 504376740 419700583 625625010 355577692 878661265 248123579 720823110 57598547 841036780 571232529 908198765 44973387 786269405 772762281 876042355 475524272 432365604 426830828 333591518 796217786 933566814 358878895 997146542 179380649 939552319 419882352 807952798 724246280 733297110 774772373 280075363 363188971 865051598 668904370 155346666 44154418 179762089 641052865 446726555 658686662 224086021 459994473 12511642 779766489 966917081 260340281 130675202 628731432 294974902 647606251 681678634 13578554 158074119 295481508 289241058 811998879 472717139 639842608 431039156 895090739 126099320 322455112 510786853 650706010 966794479 382413261 584294131 652536643 770150668 167117835 206843734 274100264 209527869 686940921 646561856 708353161 485044040 451065205 697078687 247333750 84662415 868466315 245940376 306765508 579196236 735667884 349104843 872430676 400129751 324586232 64395155 470093649 92755421 839985270 924047172 707964784 886180776 337063257 484479597 984795695 541103451 478685242 967097622 654719512 636435765 880410978 71399424 926284797 745268683 696322559 272028649 824032315 636481871 96659307 344622791 430112249 436913357 336675434 584059658 689537639 681337194 484205674 505485020 342137345 635448230 853347522 966486882 633769932 75813016 934860277 402719225 418924181 633242422 595094766 281333627 741727798 791568268 927112259 613796218 488522451 863171585 145896308 26884993 578745366 1624727 907631659 563580504 434590840 213053994 924092284 252895038 918564985 807528365 308784931 906559790 626207716 137084786 190759114 177977372 464401678 516418144 859578690 784944695 242563606 568323388 329430470 614492455 333894180 328309731 44176189 885577037 99750059 163652747 346444151 446189319 935596712 384488711 83036269 756761067 881148386 152299010 918867330 451248648 445637162 782337600 618373318 549516586 19580570 336100834 543726127 32726549 961492184 605199776 910693599 335777223 94516305 618476046 12243043 904606903 205934464 311596249 634916848 628626458 913350438 374120457 707895206 883069722 575118737 417986367 308582862 524881439 768457175 674455797 95028765 298421256 664251161 555986370 685844209 900252016 941811651 805817749 629674640 680682475 802159816 67128055 68718 877381960 225978087 722792012 4866661 393882830 75965931 923915536 240583164 332301952 770915812 221444379 953755554 816255579 730685552 431665118 918926833 387429781 293189110 113675173 521380589 528574941 466317543 235597012 377658692 41172639 446379774 291930925 108912526 589244991 499373182 876363526 869217165 184564570 728952 748931221 292913003 537563658 948859652 154327333 134222080 837633313 935766660 605629536 323350794 247387498 13465318 796991876 912261236 961169644 786117600 523535536 64856978 362178600 93592372 317690902 756252001 946020696 69542379 278412103 897689801 788058544 201534876 459568749 499887580 672108191 675571107 782184841 717491478 949423372 1668716 533015995 183625884 38268570 467209383 321591416 371258751 966383846 30113939 282018515 512390904 19989189 503204149 583258294 165220267 960333705 230945695 46671911 95087846 366818875 835302444 697472646 663111648 848553695 111715775 233560011 588258044 132027317 90865929 777632202 627382021 380607091 750944194 98022768 720647793 281523598 151179757 31939588 733193377 304656240 757811990 303342697 548267804 584600512 763343764 90569304 371486937 37336735 527495113 787343784 773066611 250974695 563970399 97383816 319013492 380844652 376043658 785957313 320465549 894167868 825706314 317947894 954419929 99223264 257164455 612852453 412366879 961694363 161116149 839829924 783158799 240121767 231934480 526099686 473512065 576156285 853863582 776849974 756201147 977175051 121848145 746077497 446787241 511553789 647620900 291501806 848912933 915428086 971681691 53298926 490894382 422069717 971986437 877267629 906405938 688628979 94926523 423312569 345603910 602105441 443924576 689069048 652191082 748704812 92605216 313047788 168883399 719987611 763407859 704415472 598658290 364062828 855397848 627684729 612397608 646027804 482104604 486238039 499453074 311275806 840543379 534762995 179862912 909925408 737983195 734830737 64265391 697955659 780107166 208635277 878571397 500322689 109918413 491570079 946450513 87645087 803622375 502855960 962488205 18665402 349332274 621959461 73743646 872439395 923274494 362677513 573953424 920445925 262019815 375480676 46491483 620278147 267103505 316706160 266981411 112471741 495618923 677464127 834150897 883531401 480418031 768340480 653153917 27661467 870683869 419823418 983423077 903932575 287817733 715538445 507499124 352553339 101401084 844886389 424988382 346836624 139541603 211797640 593629824 405712632 388690468 396533684 669542434 653297350 653948086 884671492 748414390 740304971 566857558 670157914 829091736 325891405 12986446 552885427 573639629 80287311 1698864 535482216 292553030 645584333 607948057 454262377 101162268 557799806 130885616 544545922 802465235 271200659 674693029 741615255 716429464 449262068 584138868 21662953 451894917 92196743 390924066 464668752 716723162 459030378 341696572 564641664 741638979 811219510 125196124 83324998 691919126 240964412 792935013 777141962 619674771 129785801 674289860 17972429 576759588 631821411 520363183 263621865 620918684 260398090 241081959 851550678 529843578 765495674 106457975 890585504 103738405 997215334 434317812 598893811 342557742 857256636 314408380 544968786 853483667 994986981 765460921 872511833 253933560 381472771 178165533 561745408 986767853 893229362 445489318 883169752 782836269 955079881 23940569 114302285 145555930 970415256 151678535 923249892 208279236 246792745 227221196 112626812 899526817 912904706 241461965 27302543 365420115 755708639 204477815 963927407 936654631 596060409 284298501 430858379 435816466 171224387 80946168 223164841 287009524 251594409 581997150 225986091 921446870 951753041 35540237 414858828 364863533 593697243 942744806 966537314 873132054 281198755 44253716 427762715 592956826 969271035 267887436 186575809 433521129 84157555 713759501 532135288 315480736 701731859 593704671 126598780 555968261 532882845 167372949 520283238 806495559 746222285 115662733 67674214 795613120 805863066 601346540 66112647 543326772 795640436 433278436 417404655 942791953 313590661 229975791 3128094 258748591 39612402 536986898 576253740 777358479 889608217 97330717 189781773 814417054 504379859 594724584 935061454 272410736 157071792 372618389 359932630 562803335 679118911 599779794 920131880 869858187 371792709 693670421 251211421 560731024 385967875 731459808 605224236 348177749 864699250 36779772 977830948 24809345 551898503 967908799 876188014 336632806 247053937 686619720 759947981 706348224 421425368 13307071 815742751 692499956 447826974 173647768 760296859 862043731 917794719 436331726 953166610 535054038 209414642 929114409 795593007 677821921 846729767 502517626 340056505 665283202 725071624 234966492 437756878 90050480 982312538 833068275 883848999 140431758 632607259 192471853 526954841 90129063 749966275 605897221 119230735 274627377 515086724 303088957 925236562 352933964 809520524 806318113 878567619 460090178 609019712 627237064 293330141 545308358 292553856 206945620 330222389 896612407 859681512 811171630 44669116 853880027 345236234 573614157 917640441 146643238 773316534 786513006 768492880 427249139 511280947 742432858 281907775 242623943 31339141 661524260 752370334 893946898 752138407 652391786 772762332 669387374 502996432 801910930 438541382 703108064 799261872 279563276 561188929 313963540 683918257 360736403 551306637 716560036 498704952 380389741 864099714 704165967 341557218 198053288 874263891 614682179 793240009 145452381 880600399 274520405 778716095 30674159 632081437 490712388 342346640 405282378 856267261 393436668 888088129 721116710 524210699 864803023 595889493 988479298 880140157 935173051 658233860 160868267 449999074 377957032 202552963 187695604 660979554 801702056 785333569 918900350 309950466 943599416 153932325 400855727 68532959 59230075 103039443 668060220 178330735 650739587 385128678 548016225 121479365 932619145 931937588 154790692 781062860 466526002 892173071 608947351 67158920 139648714 171321984 87489045 572050778 479938697 427567244 195571586 646880058 122847699 67791985 176813197 470330364 872046705 478629095 29570032 972326286 971685338 128357216 579311275 473059894 416401519 343097674 316046670 908223957 721438904 631632713 970837293 163885864 689520297 511447167 292053419 759887107 316631265 191184326 260187506 248782742 367090151 197679347 482046903 462747562 943499117 118269458 819054968 93161442 247813007 986215086 531825855 582385660 292443666 150051591 75235806 618708495 77822375 250342235 500021938 726411213 665605927 812617504 287393249 725737408 305566934 162155589 613305886 297456782 337076641 953444470 977210210 552751670 544036450 395730007 40861746 149401937 570715417 404808389 600328925 161936980 850710066 704640026 87101116 545722059 146979267 418907496 752106354 783233181 138145484 14973370 312913964 758595404 338756727 593125720 78564064 170238259 311253335 689236225 113283983 902527176 529956522 132372784 953294212 215725017 628011417 40647513 357633172 146878160 137762933 994654506 765405789 293477361 700614137 80020941 356836745 393416857 882496652 561401122 706383114 624655998 619300733 375966983 438112605 933229811 892082247 483194001 768453065 925606434 628862412 636766546 418019743 945005137 756811676 566790803 727921017 997868832 144010029 803450008 757539964 899861703 117473057 922868705 932952471 968724314 483074181 1424996 879689412 152887814 644538382 231280854 355531332 19341907 879102811 68704225 512782309 725138785 374498360 849781612 732276797 287571245 360015831 938853848 650305517 706552267 522799638 803571007 338135776 343827115 47776957 640329397 478099339 865247701 938990782 751695241 769223725 444810031 5523317 745542274 631180302 744611763 469442536 754093859 978524353 722835643 530987014 556822761 847917411 764547383 846176745 310064777 492312027 436988147 79443221 250511157 294958618 260533204 805921720 739255254 879489882 794772249 519385578 390680144 266697057 228975771 813355244 995592898 91610044 42270735 495805547 509376709 908027142 844235840 728462779 188146346 869218848 679722071 621531933 869718206 237478264 422353173 26754299 773620360 487685188 962006037 960656681 229168135 364802501 688697612 664681508 256878325 968178823 982448395 743603284 796214792 791194013 604379065 157642571 368380462 582932455 977348762 955272452 567859662 988648269 31714381 409818919 515968011 834748418 660429255 899322433 549595650 907956675 519258010 226049294 668721672 645053720 761270067 953935793 3306734 979315856 974752277 876965624 364197183 275691526 419587872 446093722 895089790 743104992 454737870 355089274 515971691 589546060 993814386 658953443 844884540 760117890 334419065 594516427 98082277 859066375 629767594 198634770 688355154 870065126 930554727 322569154 902495658 699852278 823465708 774242382 83756684 826267160 233026445 562698196 999772498 139117944 165915641 668577117 177893458 751594441 188957563 90430234 480980505 295341195 199100725 443195302 917478576 903147590 432695140 137851208 301716697 768337870 592154785 677487407 247118161 422018430 909227292 956122294 809506829 341912703 760306145 11488927 413913982 698254336 656203796 533846617 333811663 795626108 269438518 900172092 116518947 662691577 804594527 910638026 844835289 157163077 961652867 852186350 629700042 794494009 676234672 941326141 927392647 727484152 330370380 225359929 439227549 489239598 441026392 680102794 731289042 28802130 48042161 89900613 8730727 176317926 920911435 973495335 711122773 470551732 528032886 904456409 657982098 443562256 896988699 752866603 773966923 339955482 273799678 87766106 986916905 508238331 966112763 347540299 479470734 669286180 182346 365673423 237860823 789811604 732308668 920073184 94270361 333086480 555244541 558839008 873952229 70897515 78145234 226729182 294306437 255969725 268563802 704898513 549391423 358609325 218003535 900260060 556992527 310141098 915517507 611136907 623793774 830346539 832099045 150209810 891540623 866177011 423705147 623659410 905827742 168090961 157992424 834914645 919328769 823385177 243267173 961099791 752740505 747279918 663205448 492577821 590686207 815011642 733738370 857314759 461550537 775901809 478996122 980899967 285960132 534920340 817988085 769153568 158276921 242693481 396720399 31919666 951914538 583583493 440959425 151128354 927491731 466765572 714065787 714027916 571678123 346177485 472050824 680599411 808622882 74463696 935249230 213051268 993138786 967043273 689707405 374362713 122075600 192846076 175971741 263703473 424344586 117761144 491517362 763237818 734076201 102362198 218543385 266440778 655035902 551616505 275465594 468319774 60785493 99016270 91251733 74772003 204213558 820311819 821776647 256069291 589575201 869538289 640358532 240606901 298672719 837378571 392242204 229767975 888913142 911633645 266844664 640115221 201676675 688044024 558351387 587890681 744865502 958225810 764145059 648573690 323787947 737343600 375635974 346047527 90836614 469771982 980718680 174077115 395998020 492518835 961424001 907481944 811825717 130904624 929832073 209929550 149290598 82032799 320045518 756080595 2388441 313251301 888959050 93782345 652542669 754455218 287475663 408986237 555060474 725041853 741227852 665209827 418349267 531235850 428981767 159258845 27893443 818804774 372736738 378189043 281125490 610730343 177030040 782028570 476626944 845338158 644583934 50006767 717566278 158626854 630760772 537192955 531198233 453161860 326112051 619048686 613884552 883506758 490868079 947680485 787660315 588395382 514171060 963209381 166410516 387840102 296828955 689412575 574335151 882792435 955712083 224366700 100662115 475689412 467498217 483490704 606678048 656195978 412618627 112842041 611732368 998796351 521808158 705994047 636442456 94506857 662877013 196278435 749003605 139475029 89110427 131898065 75837666 424119646 532728957 129912032 751283214 757108517 785458402 857291470 641598696 467480024 630043468 441499334 943218357 226421869 345163543 57209435 940847925 57883621 846884279 319833548 838969315 117369483 360614395 342536000 625250611 717685556 288773454 471802377 456055764 65796223 114521842 642720739 107713518 214159892 621872965 694530099 705827938 751364071 266339581 581799753 18832399 514602867 427115117 485067168 574601992 897051392 518590144 112337179 636638688 941499615 853429050 11403336 593821408 591726762 189099644 867271582 842338637 298440327 870219199 992877760 796471973 907545188 50272789 539580857 937069536 180750649 646778284 969597503 753695408 963105355 291435276 569194738 282632899 133001317 17060950 522427547 748675838 590562078 304845445 174762863 913008321 260305943 991733934 948837964 732406567 522365500 710256449 484342776 393336900 95457024 627449671 79487079 379419751 803512227 191683491 844240371 360680791 67666541 898249299 369104547 983535512 271103985 809462190 417210726 367856037 768658509 317794214 712658263 900138292 493504102 647115013 551986936 316475511 345862446 323162801 795961720 225261911 299762400 872403689 232469487 945282745 669257791 736050311 664228511 874065850 71879644 198278717 220144178 575895796 167519055 215153114 219134720 29574585 751533179 805229444 195868744 303576916 149269708 142790910 119608179 165618765 677281401 784353505 399430998 767915427 952750532 337196003 277565806 535970321 213107766 989625365 632141091 77473611 442550758 755192350 13685511 722520384 454198961 684596355 134350358 232189783 251620736 55362785 325844726 652944308 809844615 279610670 301755190 784586865 637094785 197523197 410157712 214217959 692180727 438157496 927661608 3328741 596481912 303135462 341193164 577395189 639660512 901716324 373821235 337076891 93857171 919272109 198101824 591161239 259676096 362862868 822745919 946466080 261711520 506038279 922973732 676932648 86692021 597748043 115586000 881060252 638640141 689652292 39575117 299415459 112169855 734521131 764353294 330875100 756317163 79800920 37989938 179111842 79431036 418141047 482085312 185122633 591124198 648173268 544077034 379231583 162864809 188405393 522706252 86822638 254818894 897875948 616817195 313195446 915587494 326745724 825673143 134528885 197431312 589617010 232760907 127200544 715028402 880541402 722894250 164965929 651792572 685447897 17801281 920192441 911809194 988146926 79073386 166525428 932219776 40549683 953812388 662699833 761850125 738615706 559501277 468408673 59653162 297690418 459445418 103099646 699828730 693767009 98225291 265975451 778429226 667394345 790350890 953989119 936081711 112467045 82322842 595964267 499698572 396338954 39807385 747953881 113505547 777520232 19631312 207463741 742186753 624895081 676807439 742707141 176557708 778151630 618804884 573549850 883637718 1473655 629522242 848865439 191859537 802981017 447886316 432162222 869154554 179036678 808064905 408745184 169522072 528239211 431181438 931742019 999472123 15736203 697129434 544328099 378616383 996350598 754865811 81055171 23461640 881378582 583983819 28489123 886774470 600310478 196538126 9944249 583272688 468741723 119491987 56039226 53011786 665451717 406906233 946461008 879888160 641536684 947922441 700790882 274043018 57314700 833040888 116950609 770730408 891199227 688917667 957550775 850807781 179689960 457118034 443727399 823857974 671653852 136506487 20366194 163459418 858645050 655425262 565161182 355451161 696662911 443578685 635125614 682950534 553844356 203383506 158188063 884814654 177015737 814355273 118407974 241363368 625764458 802842022 745581876 595596340 251294203 794802580 483971252 977853342 14187309 230386350 592027913 257718571 550013272 716326836 870961106 884989928 316829105 427251154 772470824 59723248 95725699 599538143 582608348 662744484 800544887 180281241 732556475 442455794 800768974 686016747 682044363 862081680 263856547 361020712 866270349 677936447 283830059 777520719 666944059 242244874 703033590 192437319 875988745 474071174 516717101 428005409 51447653 389015058 98690515 222993243 620734776 869009174 191905799 119005977 467382052 946995013 909299518 857441644 302760389 70399452 803044234 772963468 872425715 402552034 122097623 494409759 576436988 665214056 112143146 685404786 935571947 805048776 268119010 854486460 228685510 352001256 719698169 739218272 702086857 660423542 821848898 934019368 990007469 196793898 761970346 355916428 25227749 412280841 748403576 808049131 919185373 325369245 427637646 730251727 413990203 301550656 298978727 509164075 658333472 985234768 266143385 295303069 887883365 945382265 305528466 46101678 401306336 813415920 962564701 827392270 886836894 998122932 101978780 108634330 487136040 464511693 444580620 481803224 153152704 646686095 859465670 795139767 401320355 785861589 31693946 310941778 863734086 753827912 171498931 329048811 255212442 924418966 708239895 898123633 936969801 269283261 881332134 23197372 813971448 143682368 380011768 647532238 795719557 964459629 282474113 222739985 269652809 654006431 353378255 623789213 433889877 137820536 301469383 310987632 267009462 889148452 534791917 608760757 443534258 530224794 834620058 358532096 245476105 615420124 192234566 961472910 906385975 816628787 129120189 634498439 289672366 427841653 241477483 582175294 175466526 596810561 257712531 862853740 725539759 96690496 657275793 916306554 345438019 215923555 571246364 74038710 258140854 859754537 531363208 820246938 946622751 728223447 735109374 930130186 924938766 443436223 288561603 262067604 797477582 803520124 66026360 384412335 145898914 324175154 42712150 95319806 744826633 367480272 270436463 276739980 680893179 886873167 954994930 437442832 134688299 945343729 720730981 449366312 976504645 47589764 635156714 269952927 681174575 984873631 524005244 131281832 70878025 169328354 354890033 40465186 415593646 909756471 783895927 892886996 690030451 574913301 916624472 171698351 882588901 48424889 257235384 511306513 198619085 868044140 356486803 321599486 378351020 856961474 716051522 940399974 730742273 908326871 422399412 113911140 64559487 843571089 242803894 545974651 607041881 230557923 334112558 242615768 664151161 656276741 658119257 96042645 277891266 451763134 232758802 803708145 41316434 356667036 405119500 257383066 107358404 791084601 213375764 485156581 390097511 230219125 517194322 656009234 970560906 851701440 249523846 241387146 969530802 491461454 672535884 268953122 908507359 35822690 106460762 129780056 936818381 345765510 899224255 40846994 404281390 735361231 239910948 272589156 144234994 430728731 599363596 329213384 980737664 703151699 870081300 385485157 833387260 31706027 509330485 393606346 770998913 299397087 367846399 670641329 143812966 740186998 679419870 572849982 186716283 263048448 896943447 634493248 910449738 692199513 399025992 814813548 963175512 839540709 694158125 203514791 893592675 968138196 437527639 660550202 520383907 284185437 841917749 629940509 18716682 829985796 72312460 830911790 41649030 336220885 625510592 233222521 972448060 978490792 966540043 434821231 182624972 332320861 163236546 270655280 203683729 788499999 497419413 929925315 927502304 257268899 67375566 223763802 231499333 94672743 185208718 974493585 287589579 450993397 507537428 35934126 515760178 103643679 662873591 639869152 509794104 234473282 877818729 436214401 129152979 714345349 540690292 520419157 792547443 502233625 775870782 910171337 877856066 82193784 463585606 578112567 315062117 455404199 726723238 428562463 485806649 530418293 646410833 501120877 282698904 976741564 869500500 109698743 622136340 505240989 442803478 336814973 486493241 603993798 155659929 693601129 100117964 102361261 289387448 414573967 230049295 689688019 681883497 740423595 622334460 869802499 353848826 896245607 369436040 317688210 27378262 605157268 836152543 393555102 396874559 225276269 72595372 803017297 76572818 176336345 767127119 71519773 422085768 415155368 431300390 452305664 229417713 372081618 48304583 260924607 290507896 497833149 701431873 512081195 595173860 359912822 102743136 935426913 949576530 361631732 373214952 920571651 78123390 193008473 565215447 782574978 876425465 70685490 693608101 17485141 116579185 825511604 315261316 470101825 786901230 190330879 196132513 792108432 504205072 921579868 836114531 89367899 314052692 111885952 550370729 573590467 16060238 865958345 243253006 803575601 448791022 949374333 545924646 154502299 47020221 297181456 477377216 290304704 446267422 196633180 143942691 573069672 208607119 182891239 227410515 856047270 783129319 426844451 450856266 243975704 826838935 915854247 119197761 733277219 64067563 342478968 840076007 155974969 570248776 564308036 604246181 708800788 759975021 883775395 964888546 941515770 331858100 545425494 579557691 958598137 936518479 310799498 811065031 33841705 886276493 513932307 98401627 953680367 70644500 183912371 262726593 557302326 442013478 384651346 282575872 642470581 303414238 455874117 964415641 363468589 363961202 698673289 569022918 534044842 203407216 44033542 968801467 735333055 133614082 31589070 211002599 620842188 246057260 704041821 573581617 463459129 550297610 687927256 647967548 347381434 643036181 186002768 822145701 670449034 839877724 861779710 9972802 109293745 34752205 127160710 353525602 655486785 991851883 813471286 611573009 285924754 534921622 437181509 395333970 949632651 361374537 314977302 494607973 746755802 538672212 366106740 176722944 886697016 730036647 208359893 188827288 382857383 761228425 697039257 445037719 793071541 706250714 154509642 661703076 813418425 711855447 956480476 291095520 644651794 232224980 390036203 888143141 785492845 85861249 303611905 255639623 694436605 86864166 764727759 340998740 298076098 272488296 245402992 397421525 347146437 416354564 987801003 335096333 852868951 934138129 23292976 345989174 801082455 520353856 420199639 983134409 739391339 896116765 519043814 353564340 603206211 291240012 742876745 95628963 503945690 292486094 84366041 154774073 813832118 249983548 245438872 51169622 938300710 372082440 667145201 790010704 577166465 844637376 825920250 231818811 772926058 655170124 18258098 842267171 663588623 685581357 844631877 686478927 890690407 137566142 923464261 927233662 699656306 392754804 419598832 629043242 51741307 93303584 833610351 857062345 888772182 338329385 294547218 787048456 59891363 798203859 470564246 481087248 589098251 716235644 422929761 488369092 962393984 338506460 353774274 669512958 631690623 395906626 434282547 443746006 328464206 221995739 206383001 982280669 87655744 528932844 448549760 604647003 89556205 344064533 618652256 873650583 729231485 535869069 368450525 944626957 267209180 997467242 870188032 116853686 245114884 83856344 312783489 192030533 302489656 507776350 691457022 212053350 466036036 993903391 686305602 889075968 384458432 617879060 565023873 522154865 857405516 304450388 975029400 115260374 772280531 838099789 80586319 171524162 300252618 237721866 281780632 858553091 743807599 740747117 209279695 622649826 363121932 659547763 11367929 766902113 136832563 228956277 573194759 453650940 113191937 252422499 796960786 760749930 737345884 920620552 962499230 8463836 354047799 446296395 567613144 570135354 63948235 449010537 96205786 806181482 489554397 599174974 99880420 782451851 471212541 495363451 525464994 482852915 333988802 49218542 418445674 898672310 23792400 597840063 360809596 457660768 268015443 148770734 503114818 800408759 260709571 883317080 677106575 285892540 517356960 676532337 60525538 216681256 506139510 153950473 256622241 207850161 472196183 170767817 602110560 23232068 880705573 425955636 484725786 702052682 910707655 478152424 160711284 85821925 55013488 867360476 129499902 842257969 574503645 521121954 529217395 912318341 77598357 733172900 9996021 817495985 72164649 223665511 653800788 543535168 121272179 237254349 527603782 303993269 417247960 974045004 306814125 936403151 398636680 924762938 743124438 616207302 179270842 958697986 676993206 21844877 931282418 887677806 185452333 254502160 719419965 878026973 786967364 61902453 317445745 800413323 230289520 237143644 290986864 456860877 434395854 386129697 387166563 161031508 78209127 949176342 535713024 700281959 274712683 390680267 882254021 44338219 667856503 786101832 367344700 845638108 592121809 788286031 575333688 170303763 727514792 826050204 636089620 846402815 12634966 498205734 491886072 607449006 730404255 83682397 796157973 278383427 325034481 624044652 676111589 926001982 351877284 295159414 654710382 54024633 166942521 352549594 242524286 266376359 317462429 675263344 205697517 915074837 773578596 339323595 936783840 824800875 261693712 143831414 850883841 69847465 221092169 978206009 967317194 31304876 301470243 27601492 788942521 63388520 989092445 317386944 984103322 602753837 368324766 503747954 667245251 792348131 872414392 782713241 643673936 739562832 961236711 275632605 120645485 797236302 286947088 603742624 822396810 748615703 766969348 319728702 203961253 539957627 510133436 221046862 184881286 145198630 719121308 640526560 394222332 39493597 516173746 462821054 311232290 794940863 390662133 389190573 596223902 873531269 917236360 585597867 85406430 911395523 178370550 360283696 771517019 327667239 601619061 463868783 366200791 85108919 364157221 223149459 208488608 636922133 919366480 656827396 392663757 630814908 47465385 697132705 997241981 760083777 709880719 956172038 898830109 494059924 799836232 356021189 243608224 344998718 159790152 617952174 956842694 926387619 811460201 773525256 30157911 387155775 733579058 798863063 743082087 9415402 948208147 302367766 49094033 496170774 129158820 38042364 673068350 107456781 884786155 752032825 708599005 692305461 447610772 370230327 521051946 440287053 414879032 729234011 209308521 758410159 568109977 784265795 227434665 691988622 423814626 320936199 906686723 869151799 171139304 374850681 502029529 116498257 639609965 740340839 585182233 932296223 258590298 715108821 996276602 436686266 864637953 760691782 663398844 774657881 57131363 186028786 949273833 137609098 875257957 983260174 295011736 586598776 802806298 457005577 260541990 370111013 959569918 855563978 587678716 315790766 731108663 426249973 416600782 774281868 677830100 959309605 486260184 238429903 913526799 502923569 735195937 606079330 988092813 210918248 616473273 953086284 587571866 751202774 309132284 800761579 628566894 656872319 201813710 75019064 825186668 490007969 763538142 946440455 79806560 703735028 95506661 533925445 568813502 719678186 496906214 372574010 874156520 74527985 927548525 438202823 361566566 968373165 551920594 936023719 480740908 338918465 684672373 315637423 454672601 830268293 599081473 836845071 903497204 730330958 119121578 198978960 264979247 833580458 259038320 799470037 731599526 588639267 768289628 966994588 629406238 917820665 80882624 302217724 47693384 66305642 270872953 7613862 209898493 819109356 535685934 457072166 595941249 640041326 865328527 16843809 680077249 186875548 465850008 351385494 638849943 336386074 907599565 297627935 914041603 793220294 785160318 895076143 761847409 598693623 950045954 66615634 306499575 183630274 987668477 805931378 684364437 656673329 327548571 193200910 927116148 553742988 401552084 358300802 590753066 26153362 883169448 390604867 851951346 498896318 719165282 990374946 573178358 516676740 108747991 801678982 362758278 113460114 913824421 557196212 648802144 112699922 229834614 915670792 699363048 307908068 163481148 518842427 17003118 28363494 715751284 660920477 902588781 923608109 74642021 816837209 995671239 67709771 467974752 746602421 528260620 344784777 484204031 463587409 386740914 258512171 154142311 366266981 957974875 758804657 493876872 931078661 356705556 20178962 550325337 822631518 643278994 959856640 904968222 191358712 40261492 66418984 203169188 638282483 178956678 800415601 744287105 712633420 121813497 714770746 437777494 951926039 537478830 816233117 989509646 221880515 897890154 227237552 700791582 982442843 57882912 920068801 617489349 635029697 570708268 748890007 744852811 386409459 400838292 990697141 999436099 917479496 386797383 655124888 837123274 442039473 116432735 516826870 380548551 364670202 624049760 862592510 175904811 970999048 788985976 645923740 570385712 887187481 676916671 260462003 991693980 730778633 880948086 695212131 133772285 310208649 571021130 152607042 746842091 770792552 398902415 826501284 564429130 492723404 834275206 367273174 486602887 144798839 229918873 466320732 333175512 716733700 869057436 18483768 636671871 742857256 477439756 60992292 840585477 421910771 169449297 873173716 913483392 230691598 863022589 78421558 805520591 893121533 40513291 154866099 938776026 482680412 566253091 74240109 11921876 947130660 355330002 934871425 627778171 608360676 820235988 158523716 775891028 925449993 981504844 910259335 199416305 328264984 376227848 674491349 510631212 370827249 733100991 610576562 19155051 383572236 610894420 547622107 102798300 427312060 396310546 59677577 791200952 544158832 509172463 736320176 98579585 897986031 58801611 672880186 857482821 478368921 505661871 896584526 598744026 410561450 638674193 107974541 730611490 378501752 6508300 49978448 297608006 368311730 27283626 690077677 543602685 551174816 479872027 517784817 240753347 804599399 517626365 861828453 599985188 509283140 682094228 723308556 324049648 994016206 978556176 247834528 838946694 912958006 126354124 105697305 392688907 838783879 291309194 428475880 948068529 994975464 539358137 755459381 993328371 590923479 91963313 470795558 991357653 111411821 184984820 906663194 603739942 937193630 221898348 704392167 831930815 113934711 345724081 246764833 12921538 478794080 379663682 300965460 154614749 320027226 631793608 4383814 423964039 239540032 272720216 279423544 696743487 429778695 627737007 91962148 711955922 650661375 877494389 872815869 450926227 830856465 324407933 59104755 892273315 138509056 960919809 987387310 708456232 491988394 390823143 218441360 303638935 656710470 605898240 227432694 396417771 845079974 186850885 759239797 967798509 21888372 356708635 662128414 368605548 324555126 247697550 195749052 632390532 214548939 169798806 161181714 227650777 380687148 113978454 546816543 36984538 210993710 388040538 886225755 911632384 658170493 737205974 606896889 556239118 197629472 912652523 348643365 452690512 119109305 707843043 807089989 643215070 937567939 384371058 808968506 691624407 444127444 130007541 27899037 960648616 292958938 515269556 804654852 319773509 177934176 52145697 587028028 401994604 383805640 523929879 777112974 867693031 762569871 302062109 257373436 333800647 43737741 642476963 778030210 136476587 203884084 755659330 209118551 657932025 568930767 320893950 357743403 63093025 32035266 3961220 726365033 111753695 791481806 486039406 262651508 73959287 674173515 911864187 879847147 796711929 106361197 264211417 553852646 490661500 654769281 432025693 480179512 691251812 182944047 165627847 454238381 706475677 227681975 703862017 736735563 73190111 620025654 394784862 880084882 24132842 453098720 354780893 822806973 290603977 535095108 407759716 525002497 802750737 69692045 963779079 581526731 403754016 697136317 788292928 54820356 218275168 190256882 517850934 564988493 263698819 407558819 540166904 304816453 897062086 41700577 854543809 351416768 298499632 816169368 916119091 517777167 197947089 727252173 636616094 58874428 962737925 678640607 303608632 920663372 247485361 731522247 904921443 903272573 944320898 596921178 462823660 491033479 323772466 342382723 510767687 211261149 3643332 558697355 762472662 882074347 37518277 462980435 224916001 314603862 85533835 804479894 373661469 802302017 975007351 590524970 325598567 286297988 614384948 308057661 314231943 659047925 423001335 100213145 910376240 269584032 220085183 527789026 730565756 851350544 275337363 668237268 160163121 37339014 832952009 645383815 440210688 562992702 997767483 148275885 88361410 608865455 432255377 561355728 440446651 453772745 956955516 781289366 551258585 876052022 813851638 395672831 186563828 379102107 254331524 825768355 477691661 469406166 723961974 130122997 372016528 290691135 657335843 654636932 54414740 850512616 714891311 871494711 32233751 747834847 762794695 209452942 211691076 991378025 637747937 794138853 574290094 510442566 726076287 21474226 901994132 873563377 25732330 8623300 124235293 742537951 132534264 756443524 556054683 287733436 621504328 696389429 888631242 521611443 395147394 855963700 596676367 610549157 885420441 82901818 523125434 826027118 480740874 120431767 705407302 176538916 237154844 250751351 98616470 43352665 961160224 979292958 969941816 206230614 770138033 231074861 813541795 108616800 137489138 38466012 280807290 303115765 537709524 231100735 848731336 780475405 965276495 123479172 899800899 904551002 394857637 358057009 290625418 690140298 412058276 453774951 871297129 8378242 732990690 689518627 460621842 404771490 182055169 274491001 993966436 724220677 334545386 562238425 653104933 591608511 94857491 566932300 189167433 15873055 855156155 683458998 596506666 268671212 842915882 129195795 671061967 86519722 344378100 212068283 207493927 822073044 717968436 397079455 880290637 56182817 26690771 479940491 965234371 261843904 752004544 562264164 861978808 45304221 351442742 478163562 889733188 674636444 475358203 416579188 366384041 123383259 958391453 328579384 843250065 729738226 83779765 942058626 404989524 10963507 774548005 634940537 77097264 637775339 493903451 852248799 766851985 81189281 830921614 71384655 599043145 945132628 938940413 159252863 690727638 875623615 400286005 61524605 892452512 482336918 655631177 152662004 811887161 348124616 664421913 618621030 739796637 171307964 293885069 914500464 822695026 651130518 405211609 910507275 672074566 471070321 789733561 326619335 419060438 981335203 654846643 157499151 514547779 932935934 386565977 31877225 492546908 867264779 749883782 36677301 253035992 149377870 876191902 445427819 372502170 36483719 117973456 153258975 516646125 991428333 827612501 893680254 148992968 561682802 942442416 30777872 495702793 170482435 450602733 360271349 359307451 410640839 927561699 576745578 423619665 749160541 741549428 396038083 627178986 156484896 697085386 379930032 637098381 221087076 567752089 812833402 75528300 314836663 20338530 554848836 633909794 282221603 378234539 21492812 151384567 115416936 390975305 647356969 909368344 275664964 299635864 943892236 279943393 718755244 334747326 455037185 585893909 379922706 153159150 35750445 48732705 190472095 54048672 339470351 986987359 71611767 534165468 738407616 110840654 392703738 897111150 884295221 915784156 586746366 869025840 785587065 946175646 264738072 461259845 445941749 510159892 679685330 46490969 564574890 963106536 486052083 406329572 15207795 601818925 750744508 102101094 683125318 361683873 432571687 389085354 632625265 639292653 187875368 519555844 626910174 826892001 747383277 843979925 554694225 926995386 645792544 67071875 565011622 817741150 329837345 240057411 681583638 77784733 186965326 907312337 597387632 96341103 77144124 538650100 162786913 17276217 429904636 724117628 851689647 87348234 143923801 47444101 814161783 805315031 301121559 569558708 170532980 736848581 925976627 929076086 467230521 320967005 865868327 19945029 447203955 944875991 595426852 781062372 215355689 432203090 492308055 769772192 930495998 951618839 121819174 905646991 207551083 21046747 146237810 289697746 586583559 166165755 318199765 301091540 34794945 643453375 130577379 507384970 906476833 905142425 699209834 343626930 220473228 279461989 825187763 864378390 320707967 280997800 31200448 619797960 534927825 577669075 431134350 512098405 14383859 702086783 155099986 445693780 855531568 732689072 408199613 818810374 337730287 397950484 899598394 900751157 415580654 678735427 877681196 1668646 404856966 747444734 163630899 644083689 460101099 787761777 219439717 873897621 435539563 104461426 200791446 392790158 357135020 418973634 556661906 854387137 184543471 155248713 557886560 651589860 848539217 136294235 552921726 389097144 347349511 291042551 719155753 408499017 581432479 376334596 913326484 363791146 292764483 365317779 152808237 898942138 91143926 732712738 479928029 405254499 183681494 367505877 390859590 572935895 501754970 463720637 347279109 620323924 898030228 336127506 458158575 99952607 953226606 624853370 135766613 561012618 939284974 455176514 752591425 235116207 647223411 378285985 725017785 826410291 88525815 764471289 259760889 833027782 349995852 243362327 38341562 225895968 395293793 326335856 567430255 455879747 578362237 206012004 720526468 39299005 511340160 398742397 585825439 175750628 481681958 380296366 22245345 142710809 766498629 917118101 131866404 100653320 568487947 45303739 736602171 425070564 349214019 886229456 857606454 10534829 198099342 557235953 337704349 452180075 526328492 107528420 870677938 94766193 833812658 638377560 843141554 530346397 322099539 654667816 921070866 181019284 935883034 831314070 587226051 137403400 498480299 187753105 173519215 100335603 340464647 8113393 461587644 160060635 913400262 654269879 273307782 717415694 961231452 150291792 153564966 516420581 428003158 958861265 479447983 492778754 279975068 565484089 23540525 7204755 906064814 537298355 965360614 339365262 45990121 651884243 363714714 7116533 283942081 369302230 331545029 961224465 826580230 478252772 902197977 614755769 193203233 272371023 486173062 435554442 245405781 136712915 212136692 393977901 855676160 94184406 916446981 539465622 367438809 559202215 37302677 41509696 325810737 919282624 144460731 106325620 712712756 36279045 81709319 948087937 607485991 229874436 17309892 190149122 730994601 956611892 273110837 970677789 922689268 417195576 148913881 457369536 98376730 446243611 936682408 723879652 389636682 628878996 413894229 176098252 457853706 568856129 221295500 258918980 71907708 941287917 294645555 368737507 466279323 170854091 393735082 854351435 735042940 483086522 468143885 775764582 854539920 110134656 300410478 970445736 886280414 848260625 114627869 833250385 527459403 272869320 942204898 207429034 675305939 728048042 247264830 149182276 153029326 317168039 574167984 708467262 250588718 796806106 408064748 972556926 479532989 277286342 491649827 333497844 624700257 305753496 681667391 656371676 360659546 677483369 453233957 652998650 200669824 680488059 308799731 164455901 335254407 505010809 165603905 527181854 580315708 437354169 517098850 149522848 530986438 259635067 222950561 22402767 779290856 615078184 951952774 160776419 603212091 786450325 683122192 314353948 707711094 639282496 547652091 984729092 235250088 521776783 591851001 750645426 855896185 663123222 904897274 962189827 975297646 223845071 709493606 394168289 170554404 458735457 799486046 306099326 257596562 131790171 743267584 867568535 125779017 366203255 790032290 846879666 811773109 859438041 548730644 743742306 618013530 860939088 671081952 626685568 254687513 657445009 702699403 93989233 163504490 928561025 872852435 49948772 909249954 511999593 443363312 926576274 16302636 805206849 608873941 962446718 636806097 881398503 373832557 209860149 908547826 70729830 258656736 571964557 121999562 574171698 153498317 775743079 730173102 302700904 87856527 656389358 769189198 68938512 43075707 786245590 843186163 48532828 89200157 142316704 804895681 985698024 268071552 944559058 927471860 598350330 496208485 561080897 64624676 56251328 317145736 663245386 973022082 876282262 124432095 602161425 860529179 756521023 119706076 32095178 558603538 73706281 584462760 209938670 883780839 234193836 80073576 245482882 84908212 611415113 250502778 329339478 237940587 848780780 884005302 463330625 702876955 413153067 27181742 771266663 569181739 956081542 134544624 663157621 954368155 2996903 485695296 751008993 760758599 755277217 79234785 552910124 65999141 796567603 389644491 624685601 738269315 591955972 470535411 619747861 558045772 141409766 680169863 262509351 556699458 342824212 406960689 422072447 19050818 673649781 151306065 542700944 343728773 638844889 972406597 800519511 147531995 556880696 217708963 574715291 998600943 23425016 622928507 532595757 826267015 295206950 379662231 888913447 629530819 824436665 162470331 5342511 414832475 227443667 538423271 919110834 509399011 171376641 529112210 806813483 348774921 835281272 330590958 506473819 392070098 555689560 918855721 277233040 920993506 480452330 184237223 437600480 871860659 758503651 314318666 647563884 599374042 198681761 259795116 954917535 193641031 602348650 171102817 241202799 962416259 372372913 160372792 667014808 877095921 868051027 39310200 222129381 498507279 113094611 112520229 939946857 205215924 839468196 120825402 808363455 712513873 33543005 292189933 134678607 131644466 104625667 838371312 143540618 368569788 100024132 183498924 500905258 662910382 594371000 455299461 358945141 855902817 145916192 821956891 230667897 46819850 546540457 482920324 369928015 175526389 990634279 963075477 488974681 242074057 519030876 538094104 419978117 119369928 362424880 846849301 820227977 427707149 953058040 55061259 853310759 748234957 18675121 978276916 903987560 774821273 561310531 363319239 979163106 386639256 726155200 904241455 22301172 874001615 678090148 922928470 771577862 21970010 200247060 603424735 542162636 955230129 308866849 356001380 826852993 204064742 666129668 909833150 99117102 908536547 131504481 230145851 856573154 934558895 290649990 360730599 860687608 80963751 519143082 328684997 723883350 813017286 952365872 566036757 134212778 108818655 340383203 621554574 94004909 685368287 733102905 140858786 14026594 201663246 949106834 15689150 887962709 774155084 669993848 825838984 740174813 301755990 256586974 474770721 441265756 868061696 859455075 730590819 635250555 578395001 239407502 438496290 959730033 393639564 540739345 591454572 915302971 711685339 433630727 927066827 377469666 466650916 583211319 872851839 867420346 755346046 302868561 673446086 902913694 947598234 965754157 74958613 544784439 228965891 267736337 175627613 6487860 273076576 899838441 423359049 190319761 471503023 954800014 660556668 538419666 511960457 177063170 1586902 598413382 320201571 493098928 571623341 60604486 815875784 837209262 980751893 633427573 535145633 505912827 875043355 291672319 521384303 786152387 339715843 407121628 469848205 241330072 905563791 932760843 219860336 368342968 289138232 521791961 843216104 812939852 553965172 518151194 323420766 634599588 195457008 619485292 864815382 823172733 169795286 539376248 576128876 366477117 535484934 547757618 989454872 525954867 804397661 970765078 574473580 931132633 941223411 601165675 997036690 260153363 543776598 159170945 612484816 835478896 469751505 587849972 270956229 292201317 911514026 543676392 139724715 22602135 910825309 244212812 901158549 615327247 667725027 487777049 369359792 244965509 600624624 656739218 725941123 726218647 426651182 540914820 727288880 41316368 898756228 560966020 715743923 553316388 379028562 930180149 258855455 921864880 314649780 732622721 812330726 518606972 849533373 856564957 148210191 633260410 399099323 646393735 971345023 804613638 989818999 459649481 150379059 514299941 718137971 962068021 559100801 186200264 12287019 949856488 914045020 613004552 939959639 412979913 327114127 638908265 698586149 182422728 11735038 834747160 914963584 307380001 543578090 881043759 986063694 395437721 370930219 101411822 243860907 131981757 305768821 356888577 574451248 751930407 425560982 708488126 681156656 405609914 845726899 445777509 859532535 702634979 776854160 913487712 695922955 648705240 709685191 218588034 869660525 661731546 183370509 980176970 723757270 701516660 950120050 639290654 815056636 1096891 982309535 227452562 285930956 357456525 377008151 181719456 515007663 952316372 520225400 786023151 313116615 683850178 393331641 541617167 373078320 545442068 86668651 330865337 620323393 228191057 730841082 832665616 574700234 928421898 816744939 853175780 858311254 418934809 343816989 564155883 328571752 549830884 854327818 188949767 424641215 439463832 404498692 75005573 495177875 854407792 561052026 322032986 919268823 710478829 704549682 757242725 687885687 896386589 115612046 254024882 903775129 695807446 912629961 385230515 331450078 715125241 787847481 467097990 453961631 1394353 620722828 124074803 697927985 715407539 895950605 136301805 488739107 547919998 435174621 449068622 647768701 881924506 364208956 666881181 159142657 934228954 377652671 584193545 226440811 618136219 812595609 624104684 178660274 351472645 774472404 424498442 582333510 281200198 57410454 138421969 237315922 982332636 311137631 928875673 964370169 838223817 74722375 71792611 926260122 385114334 139276354 483695772 49118477 860199155 797020253 183438424 395695077 171677482 980737024 745285529 5820589 182273073 208720939 847544583 959327533 895419262 926434491 505460406 95580581 237051026 866503076 876262757 805597710 663417401 901003829 716993467 965546846 515781574 906626649 630326154 438390978 793809497 721733586 442331918 917246690 922693658 724773246 932420140 787493154 437510524 532005524 788567477 677247709 452546685 179885541 906671266 824705194 238996962 977702685 918638423 700964249 438832253 742942208 787909858 248750196 689113193 884904367 539599418 178865408 376254025 209005027 335474562 650580283 795466382 385415214 499602757 416231581 767806128 463450431 69125049 722149209 531997810 200178204 968303102 194334106 986102048 712166246 600787806 328131272 210376913 697573530 28700812 104826563 192020391 907567437 943862503 211321124 288346891 24261229 738090933 225921152 142224627 62308228 176309610 519151014 415804190 399719926 736246496 293865182 511227477 635472447 546915486 843046185 203815849 80427319 695276564 343974789 937923001 453743440 593561306 498967592 428552170 14992852 867717622 188569026 425955758 226491945 213835028 43562685 826412480 374040334 875363277 627047550 113119076 411698653 746779363 651024547 590537641 936301001 997449089 140465220 420530344 446393631 514642044 347272499 57410756 716492422 476453270 51907390 128031209 823076928 261302455 460408170 975970510 710801257 466311476 816214327 4294709 694885172 143775499 481803744 716338216 684600883 346096674 725534617 107753787 384706957 960299404 170039505 826197966 966139463 967542981 928687472 723156810 949137022 242102515 32749591 796960609 375485609 119959077 316206948 590024015 401982169 437168277 522601261 268701981 766400505 941264359 721257922 451895514 129587472 166605418 277331757 773666786 844557947 995805267 328654450 890348569 871060278 60407558 403878609 747705134 386403346 243542607 267132673 233373658 773752061 494185890 629238388 584540960 188493887 69810529 798707864 291405709 478792633 894498324 561909778 36909686 192871461 688908719 144971778 554145598 656725594 242949841 751942979 290302095 636277895 466969089 815447465 52136862 880941941 998278385 180855107 260318569 455555016 910972861 392333720 255843322 26706236 730896426 874019563 787476386 76257257 667313385 447029113 579763776 343593344 382151891 849878200 64789114 668649613 322305068 362831512 736979713 255270325 902619105 399643843 404419534 640706807 218424524 243479517 463671657 56349933 117598444 936628934 538086942 589912073 812269743 70975957 606142279 433653722 784816683 134921756 173892231 561732166 415816798 739128488 595396363 580784847 415682162 869738944 374941897 464979408 361243901 768216611 490170818 918872511 937239354 968938060 608411969 526381162 913605715 154196399 579371802 931513916 101613208 90760187 65495790 378078071 103093959 402291287 641413476 572172152 778900804 491206822 375710063 639350263 286480735 43432133 596298124 61884998 470634131 304846282 96283906 793827472 937653698 545635140 626157857 313832729 477065340 185718399 27735685 994106241 784543287 404228542 646761043 146340866 795762069 954041217 633381752 339159727 984956835 462901695 699301871 702174390 56042261 765977386 442364409 256396188 387890573 268249199 777907555 1804421 845954260 103521653 967420102 980922730 256092700 928200859 820008128 655693922 90730822 541272572 84691773 756756700 583747095 222850220 618204338 156747489 782250370 336819705 462606685 302894164 294605539 937695916 498822280 663074867 319598912 221030472 231562694 962681301 740568712 844907591 891486770 309813291 241060565 477211490 113488308 589431552 844722603 229022919 343767613 479363643 63704888 597645154 204592903 664510234 946631572 853691158 913997271 412774775 957358080 961979395 726708797 673514756 95257640 669089727 176693969 141447312 865392483 624596127 124728437 406917441 39912943 585590509 625250711 561530840 256568375 116649008 792600941 838324210 756164111 180709481 370134840 724128580 275310580 199951698 729389956 869722332 15359566 64370591 669672804 394699876 370166959 69430334 415940535 547982688 601556754 934256536 473008232 121907308 127094046 971112143 260553639 21721728 189900643 451271936 841234226 717848110 294880410 87650432 575289745 941250272 886187239 882471457 846830418 262969372 409464600 622273643 972965971 530111169 44334564 280300773 995701495 995053641 254303534 257297739 126334316 94264839 526987073 89970903 43015405 920740968 823937555 402165114 749312251 376339507 712381060 943068449 19618980 752309195 278372253 87126770 208991167 92931177 607293908 928944782 515027499 551216484 12251204 988394318 741952789 419028842 902854135 360735624 451295792 268116934 969781021 172204490 659585276 753851290 819235924 581165083 786443265 813711140 746912736 844238654 61360659 614063354 675848945 170346991 722851213 138264399 275417313 310327333 40557976 811868462 788608117 572494417 457941859 451518395 992424217 717866139 523512681 427002743 916890662 643769386 632902320 504100218 809751070 655904346 479559174 67689145 64027627 992892420 414401348 489475391 481283109 67414203 533472909 699581813 677281867 649196555 94128525 825378652 636102150 733144762 585091259 858266574 382077035 523997705 56064665 379108291 412566327 231990002 908312304 507577223 896222226 755456872 602884119 401575942 554054607 791469980 405498923 117248003 32399272 421567795 143642709 748121434 880556163 63483026 926599177 710488131 922230321 426955285 283173955 253521551 672411307 707052881 677518537 884444906 264065366 574854743 163277678 835637785 469632574 877664498 281693514 292513851 131161435 64191461 274109956 82979338 563476432 578922543 954120458 601052185 855777577 251478600 409378517 89332244 48637594 755519843 267018280 247108613 506827332 201942700 100424015 392473483 378672241 490369673 690039138 169945890 101393621 34334683 987591041 278991200 133421005 696563003 982492183 935271475 264738209 663602239 588791320 254170149 61609410 627773620 264588868 584956314 320396814 653993955 582201444 407088655 931845129 863567822 129531018 240957274 879391268 873182321 743862355 814494446 390824184 400058115 69733925 168832277 212581513 46894900 40007795 616516150 5925764 829777519 873905910 955716622 619726979 215223063 274793459 64232184 705384773 340562891 536197497 218253095 193692152 268492451 276039841 683208680 862444657 716573810 41366734 880003811 347426672 822613508 723253997 525608281 397652959 5912415 851664051 942363492 451141649 320661763 295232995 534544187 910166789 541359916 797966215 305582189 864667041 573224716 396947252 216147235 875288057 477431315 111304776 481003360 245524615 645152041 822014253 784411714 356826482 729782256 151408277 12267840 401467337 968203268 434290365 244333931 723066055 31760444 191275692 769490607 719955214 717942760 436944755 401000720 534342638 824609298 912377196 225914351 388271260 775253695 607711612 423993669 843288445 578206765 902536274 584774372 372930906 427007508 994808744 154284475 858425515 888631527 566381951 777692944 961068751 317091602 410862436 56933317 97751887 633935931 931658671 577959317 789108512 742899842 235963072 510639701 374306271 622737858 434750019 765593398 72326932 553639632 330529386 467201023 548368242 383326393 239433015 127089748 972734995 554192389 250238897 750364404 189029821 413481464 87799083 743066868 299062817 424935885 91811458 991795975 756894488 916449275 447420765 107148983 138307558 50035058 867756397 313433002 152726649 945325788 841681836 337721055 298901673 790459358 495803296 142099952 447710583 521449558 41289366 198773840 155102799 801901980 37724905 361371276 87797832 23790531 899532602 364637579 898506080 210951894 62725047 236068816 514264514 920584733 227829590 174436532 41129217 34978647 677395224 481509294 689328988 733081599 280432456 776175501 608832250 324397706 117061819 847432633 880590125 452598181 805326864 359218551 760248241 396274040 219302127 268838180 857432043 28038887 944334155 285513079 182822443 393224397 137170082 436847809 716283116 285981505 11821369 834202669 578953233 357217490 576072546 456544514 7833640 206066636 559581367 1891806 710503848 264420211 818513246 269488122 188234803 99350341 529686852 424726634 342477782 555297338 811674468 457596763 417882694 549427717 737119999 785540949 203493411 864242769 682774755 624413817 778078775 354642950 408733351 576479170 115763893 384972931 355254762 349702213 522937980 203977955 310106008 782876274 171410514 998277434 847570215 650871122 274841131 731301847 879900115 412966345 685766753 507293314 156885992 130610643 297129723 762599868 592431094 538414536 103786216 531072003 883016732 115342233 228615491 448245517 622561087 21729810 472302222 760791817 993025105 683889176 203674616 150600675 111539084 523936746 626318489 562596991 725853622 967729250 910250675 371268603 560422749 474965555 282155248 652571375 88063514 146711337 591562664 71957677 789105615 122490734 312092697 754086019 919654379 188153025 132337583 480056053 567042210 599539134 830582075 337763077 837253175 36319003 710752318 269268845 679340083 792667878 292790301 302260705 348262573 674044362 698085227 577386576 32562561 110499912 233356068 61952033 877356443 891337216 409824749 480737144 239503915 46570215 527875415 248076912 375906288 11341456 398453019 171302495 562733168 493991782 934335582 230422295 800538939 927565293 932389099 383950881 913545004 638177798 769968765 999689217 664790441 136236585 411494900 87862135 712238048 184372906 794607772 661083834 759844362 535973622 359042412 10133180 272668330 287008469 676458562 600755307 687556556 452887975 109254441 157442539 629016648 325306793 183875476 12863966 553993470 780866863 193888674 507185310 322426392 459422185 822775130 219736959 154329165 124597791 789775854 989103632 620188186 992746999 733729529 250297176 180142857 363326124 98562499 341566746 864042731 252557782 849852025 391319315 312105247 528247462 337310583 703404600 767280075 776215848 973547136 816274427 467065631 443224960 513502209 380157829 144131735 928108335 939885651 350171898 546335287 67340366 301439224 536508090 481135566 255389903 145907675 521922715 722677813 800263105 659183250 255324978 586518159 824867466 718989213 493754633 782544777 172268588 968138662 146933223 611088024 212659330 248556736 691783181 991669055 100339585 550996393 153073525 547611720 142272634 464797450 991692563 436912904 559286100 363764915 676238870 951947421 704223700 288273121 60630309 737544497 343534806 20925306 589569955 589553974 379745170 595741517 399306477 313003177 258974938 426331477 452103576 406928976 401228888 486517748 763042998 435010302 976002514 728014905 145706255 960421068 842578536 110942492 421343850 184256607 748402642 309773503 945779395 534837286 115421091 856653740 76257172 871193499 127603338 488682011 696368398 157413503 361172366 915132202 598793566 275322399 934866255 593813029 215420906 376884883 266735946 614703549 540812435 959943675 522486035 247375699 690384627 204189634 242374041 435102252 427930526 262838749 195879015 661939899 946069858 645305867 977721567 418438108 48241288 213754643 769088383 400218644 452600850 420498442 64017693 307827924 552187133 518086029 421239852 329803189 813102462 673084673 147688439 778653115 862595143 582790615 404292067 50952852 506509760 768263371 899381422 558684120 235139408 164944674 696761268 607073352 183382163 483233257 168622118 236265744 869335202 879363899 398956626 814045446 712158544 897701241 409695968 208061931 857230953 576782992 519009297 323616166 403344116 787755321 827052288 29913486 86919280 807998002 367280354 572559263 392224791 999335303 270302279 292008896 223428127 804500941 556185688 736515845 99691765 583120739 694928921 796474089 821090946 680224177 800361382 271576721 53584744 22665322 269175159 701134349 975953476 929637579 669908893 908019096 190273771 748482779 355754244 324155605 342186926 680117419 488832177 625852433 897732760 705384853 879047940 349938566 768861356 472770431 941270260 953749139 757345065 147148822 271105367 866817798 776252615 472903189 626659353 792841812 822892282 362617469 407893377 909356765 957891371 600583132 794623345 634452779 627861508 593720200 33802405 597207857 24138402 818804963 284639216 137702285 363833826 194879638 173776260 567228104 228267414 173710807 561321000 523803282 852175823 829448101 171976321 380821256 534665746 773715464 671737932 461720560 232591524 875954004 920918431 935135737 618776513 699448164 152348717 391834622 845599454 737306848 154022016 494497857 910088684 510650489 387075391 479233969 333347478 764043306 625145959 886902566 182934911 502915190 997949076 442829473 806664582 782541742 178278967 577524367 667504899 320220458 826136286 225282821 521179401 638981260 77009521 132505346 638493860 468954370 951671408 775616945 455970330 3098755 208167224 655507878 984430636 130209038 346541373 868897310 420391763 818083824 268871247 180539457 427602181 366742780 89623767 933792353 312051439 525014994 718242072 476455738 658317881 22175002 14814832 468546866 232722631 957591496 119473302 869655448 535865461 417782872 985891035 601659366 833329752 488357904 749587819 882722048 738698753 246826050 713809547 354382451 508864698 866369417 528523738 387962297 48527560 202855177 909515665 542849906 358297769 872173489 653669829 698377386 520755797 475649913 68990369 996633623 18181759 940427430 908582063 707140442 940385235 154631427 85938701 446804538 873993271 753330984 572160442 246898670 401179659 735705524 951261640 384947282 790981483 674469012 708446120 780660013 778175337 613554748 645288292 553019251 841656149 860132074 353051357 20024959 723663863 126923239 47677715 348382550 568126673 992070855 172345179 407993320 568576351 167634597 49093800 542003792 467724376 234723178 691886276 700041745 844165868 116504837 435466645 925820760 658052101 687536306 377935962 895318078 754284936 395974709 727370477 492195333 298978707 562061085 787607809 115085400 593611198 852807171 426266467 355703949 906152540 627014602 314553659 575640804 56220600 173107422 17407305 484410310 945598810 231373943 230168874 508712200 932497218 98502101 754450066 195269416 936143145 641303427 855807632 595594380 794789828 240874645 594335951 423366855 598685698 566878700 168043217 160837590 890854475 21426542 635522356 47815516 557883840 696436560 673016047 612116972 53646720 668468046 271805587 560219197 425783262 763127279 769258891 188259956 986790317 899676099 497331038 750447967 835534198 588136102 238670570 50772406 91429566 245884668 696353704 117064539 683425603 240893685 631212268 965161624 385644605 640705992 832634148 285842789 181467039 196966649 937052438 295040160 437213012 58249620 461456676 911948116 235106436 223949681 990339720 926411253 725747406 141000816 844985498 255277984 715376014 546505148 163203079 487573853 630578966 566919434 708223513 138427230 956352502 910844376 106381299 343669311 873695797 720073904 961545684 205089862 631953559 394346084 116855377 495019169 700249047 738278737 482160028 913177772 170551788 82839710 46227649 672448810 322265925 219685243 628357349 659622281 623767566 760183396 5948039 342588705 66043243 983322718 497495233 918794867 858159802 449061430 533151878 439319147 197888723 786152391 651971555 23416735 595625288 818021682 291282239 438147983 831980455 384166948 100782236 776844261 525759157 100453141 984257238 686508468 121509298 151567494 270508256 196673723 476312473 337993280 695227660 653663393 580764766 764481689 462326337 938357816 335384112 190092207 316083012 663188155 439775926 923200684 370793458 429350161 834932820 192199426 244658305 859770634 227676005 167976878 991607492 166133918 367647615 251991160 76118886 526397747 682020532 300260142 493542187 145971925 793320653 60075757 38907956 895589246 935654542 197380954 112197433 718735949 561977079 990013923 930905806 876327120 820981887 158576896 75749536 739588156 736275544 961694581 501184695 826098353 202629040 632815503 484223156 808867960 229471979 797915236 854712593 955057478 639703276 112663830 167331429 255987577 655632970 423870478 300024991 257078615 918288029 894094402 434322504 661019731 827398576 994001009 166204868 850490954 750170317 753026659 895827087 364618431 314132471 118364203 538939520 213753892 394396457 312101222 939206411 918051091 128696729 629637244 530530937 840834958 720382713 807509468 86417199 704263748 634428594 558018369 255875311 930765 275065128 442789105 359952399 227942378 77633275 454830841 668694725 976730824 400924226 251327604 974544988 459821115 198347727 73071811 876186237 465931525 203791471 932196052 972285545 669249550 51630633 18220638 258022972 476584363 98137980 499162912 69334057 696036569 582310563 771730983 660117441 115742336 71101138 624152838 277582638 995614898 180277623 513321757 927524465 620750315 545772411 68231380 342952106 201494096 85917313 585234654 864698190 874816754 428892195 541840249 75352944 569239306 794377018 609437098 709184762 948684092 54216980 477540995 330650098 686272213 320046269 301694559 590737336 104900367 10677817 270819874 790391364 230767690 214958021 891129467 936225642 349196626 148312347 667076898 33843223 47405213 932177580 281142300 669320594 804231051 582584549 377707764 325186750 736259494 32197997 383149058 332458836 751790561 930508387 410930085 261290283 870653915 633815457 2830730 268055410 359208731 994258941 856273380 55670258 268265043 839273093 313020083 786466382 792924830 360603584 195373312 718468931 89572035 374039281 590968348 645137386 646272113 528144213 287234790 951057139 51200899 666113377 694994691 842038762 627487036 197835782 122512934 292668532 786872201 57533935 32002887 638980496 130955331 382522047 394121197 868041943 428436076 26867798 444992870 872552381 187771247 148362250 984673803 994528464 127480418 500499440 559110783 345585910 519481156 562750482 602526958 378265265 786986561 632628663 744431696 210354011 619914987 938426016 52823461 707823212 30603136 919742535 927067959 546403505 810955304 469088031 704989 548975508 379593270 151279065 195362868 235335769 216043364 731491483 777666534 883747676 929799961 260879432 397431525 198423893 192411556 203497404 303551661 858947221 103615359 351189263 447164295 451655753 680393870 615403215 368831426 214414772 454197599 928806216 789453050 554258806 880843882 946196413 689754963 332435657 517329232 760094125 917038781 99273919 903198750 505816593 793061935 284610951 640160392 167620250 905046253 975809960 929965872 705894133 550449603 770730306 71105758 458660360 55875657 907895633 132431815 236256052 296168991 643708651 858625736 562151826 300009520 693981822 71188649 348882232 299942384 785654037 95265628 410457203 352700064 515138450 181623100 97583884 737483398 652753906 303022161 290622341 568635959 685470862 123570569 475141723 741352911 432611158 932769789 612686659 999583285 416083733 426774579 660365934 388569690 889269426 239547736 749309895 349245560 413020267 566640260 696687665 235374420 834353945 573537783 297317579 402088317 294268784 654955616 194131501 549094029 605011773 757025810 790782890 472069221 392168616 191672910 781758094 165887090 312547698 161228414 126070111 406528748 394783285 460505973 183016734 759992851 118370729 982647474 285186180 577657714 386748890 360416155 445747015 707628830 92457332 658479300 518516564 237329654 961378554 328865575 134162964 474944482 66296840 318070123 267981737 745840917 448957078 392730400 646117935 546043212 282842677 573515774 156161277 610222094 464396625 206387499 855793636 96685804 6342767 200767603 456684140 274637504 249521006 914638736 908519707 33111791 842187464 864047457 266676911 105557161 701545679 611666228 905416544 41850405 190388466 123464190 484964897 366801383 867980535 551930782 414945758 743086588 498809408 858098208 22495421 745320250 368920840 422509302 80316767 155722882 120386981 515344958 310066205 357421056 177073093 256070144 603204173 203131495 268192690 340826479 717295996 58201654 532737936 78162981 424975538 574617847 780003483 115930985 119437747 190065277 601371244 216530282 808335419 249541155 491675699 303946882 537575231 577191441 76275195 365915765 317684272 266900088 177957354 540343217 124000312 181190866 418192256 370035854 552280444 71362853 400058581 641355917 219061850 722801982 779539933 586938779 736321706 704954872 683108773 577352524 652687615 461237876 551623572 888222241 978544101 76653408 332492973 10815172 827896098 52671538 883624649 355458889 904184566 16348268 585523167 699019373 39605084 521858263 537784638 739296472 151882569 497353417 538284239 230132828 525182442 774919009 267453013 243586357 753870823 854365895 405597358 379188040 203703460 253184367 11958544 207028070 703809404 664793940 545857103 110403208 244939526 785773375 92645907 901581586 197098066 722134527 726390308 20079121 495905834 110712751 665558944 912635519 420700243 862026997 953727552 982525564 845941963 962803775 217298841 2554004 880702730 474389253 481307734 865346301 642036547 39194380 287034752 334982359 289048482 767088543 373919672 187316588 723345292 509847253 968053369 789129583 684690660 579841232 228530520 845437503 920817986 574341881 328343365 339384610 754939195 103555911 421215178 50681484 377942942 91738487 903744584 738011479 924614323 770298962 419517246 866315274 930581371 720371948 431225732 866830869 447452405 916682720 343994249 706393360 398510932 348090007 813206682 984402945 165087051 224712832 322378780 332093076 262186307 16662103 722802895 879332450 699440801 928173407 882903563 530326573 255188227 777771177 762647299 279794975 71755137 416864845 682151430 525615120 315190766 640564910 335815611 133948607 840760853 223827384 795969634 80016661 224400126 87409699 851129111 410130023 523706408 96954030 649709328 64305331 960864974 349389158 166243548 866760159 936671524 169565919 409209763 273885438 88047001 249241975 248963178 351919500 333936149 682395799 185880910 374866095 127163193 193078259 881174725 819384438 466505123 49305799 169944802 737276699 95903529 896590617 471632528 483190850 626892315 198741756 490451667 711304249 630813827 73453000 225678860 922782008 652982117 95268709 382130995 975698080 562950145 617463679 503214364 344368702 984231182 735120592 86725045 382973318 209146367 375897179 499477828 433296601 109477951 595356844 733026218 966292162 79243382 415083803 556360100 761622322 981304771 838776584 946300934 693627593 366995713 218917661 464287488 311402510 372648964 258150033 417831771 470453427 353831131 163561569 507311034 732401876 392576781 162300567 540897755 670017078 515981022 164371333 697095125 956550026 103710856 904881416 559258970 978167209 152821636 718757831 572335348 224964822 794548673 457011314 731175241 989000193 887438569 970694917 528370264 218341889 776308128 543170564 744828602 471538390 879028934 639966142 249888484 278058222 936896178 347339661 896531042 627166815 891991158 551751442 954387227 471987239 123280160 299677050 333931665 448253296 60630772 840529085 140071711 360772815 377189044 725107931 205769019 180183938 397995738 360878367 935917235 285388976 315277530 460632414 300354033 971833002 942682723 713088310 319375161 450149934 208914588 733779793 577970664 871378848 168438632 21975713 35155380 304636496 720046244 265232291 956513776 799825337 577579366 262849438 508634310 904667837 241857341 971577827 102553212 559657195 647862645 953135884 137271474 862933435 452927058 362196542 264376736 250599375 962638417 694392425 48927578 876364850 292485996 56500612 713858317 812966297 294459476 646625747 265689665 764247974 387652534 539834147 809185814 616002593 836166009 831146506 2559113 828253247 633101308 297368873 978745774 579178461 534700890 361266795 201334517 895705284 132203175 626498117 882772582 549729252 52720945 792725238 746814439 978459802 867046849 330262470 381851762 270960620 506754010 208585800 762192737 323979721 544661238 53522329 190518692 900763211 413509070 827894176 56037127 479508726 959049104 294399566 386708335 167406584 127083304 105111773 234395163 671917929 415081081 869958931 769575140 627704970 106989987 798760573 430600063 307691783 611652157 895078838 348859575 878201911 524474009 643606943 31088565 117607512 385611524 984125094 525325114 897984981 831797508 590399489 690645729 219318402 769802394 505754354 83849823 773231835 676737920 521920002 726245573 474978634 22324842 889335879 443531194 969228128 500499526 342533280 947635394 472033049 723699581 883294453 901863036 285061658 823533874 962322809 640470493 572645108 104962687 26511850 553012599 148556896 856001980 177753293 753435831 442934402 674414010 857602228 527430432 787883047 325623553 404799353 7353746 725441545 146716440 361612674 640828295 757597704 396285371 3079421 293083730 615253104 46140964 657767714 856824928 466690359 862309956 635394422 111544440 186019133 507344904 249244932 162700540 316884363 141123222 370129827 930437928 160085654 715722639 260783413 912060496 301643132 85102157 64512739 722948387 523578180 697162531 453990499 663563500 444763167 785460898 191989044 167657677 439717035 773540048 899695583 7998723 227799852 723907696 804400949 466627111 759107282 470050366 992110485 112829033 378982135 385365042 422282788 329357525 985629280 192634554 166177812 188981903 434891897 72010753 416471520 429080 865825435 290219309 419158668 894114440 780121928 848364442 715221222 181232851 799879530 345254945 124303561 605581575 948529049 8549973 527852631 39449994 992857940 904670658 495519548 660113501 371471940 759922991 651206128 554019421 45438846 58992090 784778994 934308990 17313983 544253120 946948623 623278864 13579183 251132372 881012122 520601852 204536097 136933700 517524915 623525638 13958223 547318457 105747331 392012554 740099103 373482645 774621819 28362560 449635426 695110452 75750810 923247993 493130001 40383021 599009446 794971233 728507792 223637392 393217391 650406589 581864941 640260904 945982225 287279276 930114592 470748600 62719280 231815912 868518730 671697983 551957819 63529475 255784183 129414966 615534507 789863340 127481438 101842894 384712515 473634793 868502429 623893811 149286991 386150492 350495487 631649741 683776486 976916353 446927416 775503996 716448042 473910763 484856740 599659482 622645893 625365900 336269709 838395770 122080492 914126059 861511524 452191532 322663709 279659629 545214725 901555768 970876129 840293774 846887925 534931104 359232076 77074983 851612837 926405728 882207994 101446056 850996142 806978735 718346066 71296092 803260692 483064637 941252036 404871337 55759236 11390325 845860364 294585423 148939159 42375098 338992750 960375718 494226191 967844011 117075194 125604066 83564567 843147872 190638279 549037392 897901189 278395308 131124025 417880216 270558489 169816923 632057148 835547130 654719165 526742387 435461256 148139411 345315268 960744052 909331165 193068439 38546220 164605082 392017222 223682966 236585438 950940439 88124248 880246713 524089323 50742619 448588913 622947843 83664334 66428494 499324667 176243602 355960750 198144402 372085672 238738908 484017818 262512835 123971253 586618869 898278861 541961912 743282472 330480069 206780393 169052865 783941652 957705556 622565949 7025640 961243090 659456000 680808961 485779506 85057863 23052227 793489303 868823517 269253411 521579631 88036297 206258337 468032285 131660531 18260751 919926513 603390265 402045077 890012872 901178681 417024260 560401463 785719421 606636319 843416788 824432020 623451939 471994563 861476106 713301633 28425303 430381056 69117777 811536430 772666785 164719531 860095454 628978788 857822131 151108817 577183407 292213959 360334761 713854458 954792654 422572051 949821513 764303978 96128397 348405601 145131330 316073308 354922442 46340448 435832430 126086983 805432106 51902365 22412561 447162651 472126302 165420478 311609625 672791938 969614691 898058432 798720094 82842145 358047419 666291262 106039265 806163670 581866167 445990315 865557774 895196921 149944238 457916308 12715771 72454813 694970948 316122336 5658537 329823181 287909030 120216081 700310336 102872017 278653898 142632579 942229844 978478696 852403377 240395690 110846500 123278606 911762343 627960917 987711959 583157813 798068607 58611183 477498303 966777997 543345368 401420218 674358167 846596669 414246236 812964372 409194695 582025257 607011070 70632883 110440860 433881900 233697081 372103914 725820562 272703837 208070741 68484836 35591052 482447180 577056419 591297765 697051927 6376259 849643965 758948238 461353901 84144774 323088841 910412824 894733549 934203029 401752757 782077845 585090277 261332583 721445753 603858483 276371274 457277871 519055194 327895674 313532 103813656 126111011 939302539 356888581 595176074 752293483 882625377 730752344 610343012 8656595 378257425 962501523 294276801 191150919 35114251 415032703 977674166 330652474 81169240 488214797 424476559 951309292 938938843 823774360 41699351 589715365 564513426 433249319 663370702 813785849 540250068 690282665 941209906 451542019 735423891 401431352 884032505 415618475 72023705 993366105 129858131 154711266 404217292 660122936 537354282 608084451 234735467 258190062 385819746 254836594 738887248 436237756 369008667 368382494 228556077 810681423 16839660 177352575 41901521 437372668 564665639 181404026 136986722 630274306 250868506 612001658 560828578 187216333 26960457 20146614 163838765 543905838 119380919 731216496 832057526 874967973 986988059 375529778 703034703 907181978 44540205 502021136 226275231 550107293 578436824 194254058 603868203 891109803 608951943 29143208 348406416 17372009 639096922 698919550 739034820 41027944 414479983 733094696 516790362 137358177 624211483 990535212 392400316 922812536 647999280 919669020 851603313 382435963 535981367 870488275 366902614 450135842 805371573 733936821 757928934 347169614 648585831 968551409 316683636 607618635 503741063 345837760 97197422 775968016 819102726 613310884 975224217 239788923 330046930 834466988 380086617 403532183 232428559 56070828 304909031 52527831 440783711 422401159 542660762 694550362 236453916 838262887 59239457 412629287 690626970 184947968 646923717 979231600 865130344 307598546 507803049 950762960 246649997 512301926 993201419 531453838 205307596 718728334 193583490 784349402 337914338 5734311 778614847 81046541 773756613 858941143 173300558 478676715 647595236 822263888 361469140 695893985 789457771 921902477 866234448 131412808 362017405 95529618 229251036 815760546 700175482 297040175 822957930 636532186 976508217 57782843 443929609 816795270 696329036 459542234 851653407 566971174 861832512 26845624 453830574 481631331 336532700 687119949 504362385 617618515 915488351 254189593 661387965 891529137 177281987 619377126 971666050 694309159 8852990 475834123 478701770 872545925 397918270 279058085 52574038 531749384 375409450 327710430 148805894 987084182 537720869 188615208 506249999 26143230 934645900 128741504 14315075 591577659 898878708 203829421 863236687 51789487 132597871 485037951 697048310 631294057 960462789 859650834 484222808 164878945 543470781 139579915 257082159 920263865 394473811 487174871 843293198 224903675 456519937 723934960 17697442 973755999 266262008 860971033 859169779 728077571 126858853 731761055 800131233 668046643 936785839 677035928 707057192 534186912 914440116 157703717 562569758 652004266 369794577 592654001 914600818 210097305 257666393 779087664 859121068 26663645 802681434 114194787 838866482 636623699 789408605 131202065 141755774 551510144 228087653 176282701 305187946 381342165 534290284 355357364 686032230 666396395 169481642 207782573 716360126 121232070 12982480 261513129 759353046 330301716 722271046 608423010 573244271 246005613 874471027 729122845 185178337 587624594 948602355 185555434 886027361 751617455 127501023 513295840 940704314 914231706 468818187 270967907 122301717 240060947 197978177 237573472 209972531 127625476 173606792 550305677 851452847 77152193 224993377 875201963 92187582 723726406 396424709 897562565 610196976 990140029 343714986 482809456 368178542 159104887 903707325 372151307 475557179 358486704 346794023 573542910 291640181 318905677 662441866 684640764 937702036 411940702 45205891 481046338 821713063 876633374 880996327 627870168 424188571 657716272 99911943 106056140 214382453 621922017 636559086 100923004 220990356 437925227 17254559 979950026 597192178 777073453 653418329 945711975 148429666 753114101 164373973 522472970 408534993 392864568 263339396 663916216 255846790 200532822 492221395 49476604 275487331 115826393 352323432 544738605 869978915 80074164 155901795 806596524 679709340 56451717 287280800 677456933 934080764 250229716 505473778 333620683 803048206 320714580 884413543 88236445 324280180 703468831 188396680 721067430 835536363 170512636 296034711 226704438 586602636 679674778 469549520 478646059 82509575 21016532 156837034 559453485 7655399 796324844 395115029 277431019 534915026 201574609 827241916 850507360 135738568 417536859 930018882 711371282 980785505 195043723 294560390 795470927 644352529 893357518 338692832 647804015 500245606 316287544 765968483 815142423 739289157 36437963 707969563 609619570 344518450 529583023 870553166 946377079 970948998 851646585 576165309 70484776 545441209 181974374 613839585 127050958 708872087 939521950 525182768 517895232 959551372 4075379 812194391 498565914 534440923 685586337 734268287 123488264 501744095 259980430 351406217 856499194 23809362 409724296 57221460 321536879 652568965 400596491 528228084 863599532 320181922 476866299 69481210 130470403 915905774 617630179 825894064 12216591 536142346 874367550 276671067 2283508 790510127 359148204 243882105 97782177 794535279 129353273 400525058 729100815 947783417 579164571 11470505 64720768 649314899 326537843 22581786 770463171 237317791 612429960 226923835 273157484 320614872 424815377 412010093 48920862 569982484 437637609 89861065 343454402 455528641 688042202 483136612 481297615 543034857 758255317 372509581 57410946 292744560 289176886 91304460 913957412 250719826 403189506 840528739 479117385 675491304 942295081 577168142 328343309 343337761 848078534 203247044 59540566 534180298 556806748 163257525 370398743 784336841 239118104 4092619 929806217 670119515 977836307 983306731 662267505 871799131 706592143 322948659 182856286 915366524 181559351 358791995 53131753 851179659 988215393 501561174 753925109 333715632 626153549 621760720 931745518 786523051 677570148 610691374 985241100 320561432 913463419 558586995 179086990 409826989 229008655 75146839 790491393 11516281 898395273 518133647 892657785 659392805 587669113 389211914 440237012 445885236 522332381 342488880 464551164 367196227 900734808 732308771 26847778 657081163 416522364 862563839 35058437 624057052 603779843 308001307 621173803 56450658 39299855 995043910 961861157 552821090 987831663 254785293 756586700 313405626 370568923 636661233 276803208 201901030 676978996 933634227 614538117 873958967 851407047 605087882 449164029 98156060 819857801 798156137 362194547 282349658 96223321 800023868 361835764 277718357 693383746 686155560 363916885 608075847 231846328 220430032 509362297 785921157 264687064 59097484 608756874 789375167 676702634 934725553 285899325 868909631 783599456 703860174 181113105 950144550 435067798 507546602 214711693 714229427 334802065 982396105 425309830 428350077 978299778 520045350 352344664 665814454 520311746 489802488 436107818 14684008 158252053 159216814 1047853 263379641 537119209 116109429 613477339 347807272 394168470 780266350 65084217 848072399 530274973 917099770 672700951 828196257 837006058 894534128 384640076 381063338 872887315 679575523 33963516 70405716 358171544 999550558 952500948 415292574 103652131 622469161 702040906 872262756 835735495 258827395 159122399 154555036 42397507 440609383 332725854 180375956 572239166 622003657 878690076 647155767 288413321 138497752 961679928 533244743 425544802 276898619 888799961 648596129 80867757 584700246 408472693 141464702 245283899 468115332 37383686 877001902 140866564 718151515 279771988 290216924 341511278 633178861 41566768 748851407 304311685 639407619 333982132 580329892 185577795 321939298 35812229 346514199 577098439 94455815 780660499 1424825 134265247 386885740 364724949 397454648 576890112 296748483 516929424 17996700 548847882 910653239 922458511 756221573 700368390 636560176 599782889 882280048 854178729 847582349 54677439 880822257 581982288 843813353 807313788 990695672 964244036 737226456 947269653 517158414 344954613 490063656 49861193 876846486 528353856 827090979 748159456 500518158 130182571 184355785 67945709 245600845 539443109 277734936 383119118 472531140 540529865 321326149 354916008 55748799 883607321 99875842 791217709 734937763 68617028 515306168 914951511 356076079 769676258 224188619 24880748 340877245 849200820 800646875 411944314 487271807 842806759 380485887 698370457 645865668 701887823 861359625 89910318 432022322 309323182 296110278 283954212 526183435 96407532 268953405 811143474 414033258 206951005 442570221 384552730 45697413 864798720 794170641 315051237 116693482 612784573 451958749 502135337 303314627 604957092 380332479 24504389 124140052 916423217 969333665 523492769 585328889 326839180 182712611 5760241 127708395 21077699 51502563 295857264 276392185 956844304 911502006 922240807 648562449 881073943 582469358 601917989 338755894 101993509 607599507 931945925 174156488 570226548 655899820 422275309 204951489 180012900 782593141 796103755 846727156 668628161 134473384 188310936 730188878 224369665 476960182 863110358 653367831 959445636 891567116 447785875 66897455 326717396 945521489 28847142 458280531 329881316 684399012 929880303 870027351 702898003 566153439 771042200 529597803 711435944 22416856 367902296 99509079 797265812 953098653 419568428 359569856 414978357 248599733 827965725 239374691 731988559 598573155 702418815 182170455 600794258 916249060 724940589 500864077 645431769 271596973 329044432 797457873 193378151 183697584 620224791 916452231 943565609 259197845 771098622 52316272 806476536 390033411 509996553 665355301 471838678 292883414 404120711 180062232 875240750 921052264 76996561 42614999 915060757 555494858 643465865 697534794 521281677 59037705 640926430 369322482 378094271 375182955 182348228 126238762 652041790 342359217 728787518 572822887 948226376 348487253 859929750 607747194 28079621 259469259 582850976 334254282 967164360 698509249 425416701 60692379 918478923 569260128 179074899 155887435 155875061 459112074 895354263 836779666 342885909 727753500 105977925 950100927 773138981 43417643 710515107 498232319 532504329 949371976 652681220 612970135 848812367 392598462 577174273 303886374 435259759 487252432 149043391 23197158 177429258 656045053 214028077 742740714 825495597 886729022 743367492 901694815 133538956 540093252 993417287 573459404 329344713 58207164 829862658 792615508 744565676 408880012 860726029 696648176 482868073 295278101 38899720 914867127 184194271 860747888 506992862 881156119 372167382 465054899 464477444 358734875 842850622 906495275 58168248 345445029 139293299 206064033 76248388 416367026 270768253 248788631 928150074 221369755 112465481 998123658 530195639 483287120 842505971 296188719 69591458 401654428 248533246 648274103 203500011 682240358 178637720 924153101 775126990 575057131 966700505 182766868 550749199 751157767 133763585 815985131 767422270 28634475 370653886 901499434 869945586 251849957 750000230 998762788 609368335 845949597 733461559 352379429 135958786 458884179 360453020 610367411 228492033 560542372 553232232 277658831 43152205 610037316 639910169 583374899 314598257 981557059 30487064 47408018 11300226 822731338 925020918 762724060 448665950 887543260 199985838 667635577 501181423 925869975 539506663 7558539 772407911 350313330 382132785 665282862 909269891 927774975 781350212 212439994 360454346 440672424 613405254 122539261 367776205 103091954 385906947 634343042 451572070 617310655 392757556 993583310 286598906 141786501 802128827 476378783 327517113 823866522 596802019 842201646 321737178 506467433 444838050 368268395 17087970 841530556 593903063 441847877 590223323 698266354 388210062 935321057 310039198 680637767 114817849 238214624 401340172 905817616 296334070 397616283 902382926 382447358 962806989 294176616 125685274 433495640 887990769 359579604 486664175 782922819 796575740 790166760 882598485 52268027 572182580 463730789 21748511 37919001 356203722 577899530 10750890 174351052 552995352 799500491 603032093 277753122 32380896 634140185 691561129 93621822 634713233 582046494 157754569 647528352 16486019 275737087 890993280 236455266 490878263 685014810 888960927 490097015 716625049 704284743 469846269 85616876 996038208 50084889 484370879 148504361 97089194 805585692 9952400 706264366 919029890 424003350 721061095 522546904 444288476 505111111 357845573 819270683 294176629 430196394 29909878 623010375 778621429 10241844 441534413 598775620 521795374 941858066 365600362 382424280 636562268 43365101 500319605 939660253 995320932 619066406 950583649 89966989 461322007 557581851 28441644 490648248 914870894 141972322 402164891 109699850 263033037 740434187 885205888 738402888 789173569 57526240 751547637 687010193 560450244 769473958 740151712 567664798 298284918 480518747 73308655 850681603 106270179 866333047 473664347 483450222 328226881 987964205 711920550 101946597 306452912 105652137 736927262 583278090 470235002 504951377 278094554 241795160 686859346 195714821 536940025 29087076 991097750 352485216 784848104 928545310 799621263 572247031 814210970 333174287 395892142 60712854 475054543 736872603 86057934 478922376 97062479 371183678 624175990 563320270 238756910 223625168 452612630 764190308 763046408 729250755 146098502 284056192 420961091 564220769 972889100 288574164 333622097 873755152 199007764 148699593 831644909 741713039 509851895 605711556 193596763 226444344 96065399 758109027 569992618 144345150 544673982 962600638 480347635 383668974 97292196 485489832 223105688 698350319 341515240 117585644 495981960 846715012 356271987 379118226 319873399 627084486 321301914 52223257 877420840 947503852 920376410 769158588 880978597 134902148 490187676 831258288 459764866 712267193 506293872 402506337 169826079 931577485 948589139 331429562 902569445 566165533 315340907 623667291 993411205 17491170 798233287 121402338 489776190 97866988 314685857 32795941 601362710 376091942 529528989 537068148 645572381 311666839 795900937 784504281 388526511 344486813 640046109 584120409 648407216 814653233 448885818 276058417 155930575 565158439 473977901 705084699 478112709 985120876 275893098 931127689 257172885 352242248 806872658 870039014 881916363 873810332 693323631 33112794 261137855 674027811 473833141 311939972 769576657 785444786 55845057 235956927 415220652 13944185 342253083 909230687 573513092 306518849 824173173 73669235 899367770 782831533 614932459 404777602 484643636 314553467 487485506 172465872 159833447 771256258 467212843 606843800 436223951 502867763 964576894 97713744 924803347 230251866 931388289 544439530 965986275 750672604 335843361 918082319 49744443 679579576 276956981 292424035 980188832 712450696 155434688 491324102 873914719 733224895 958198061 601798031 905779154 522813673 54136466 514239184 800151964 855262704 580035567 84653975 923096554 155674195 703273070 79348776 80300721 5508718 362031778 56770885 816732660 412184246 155017674 637048168 301824253 471862012 34175245 359731717 877070753 700037031 823378620 715481803 927907711 534274300 671083925 350238433 386558270 33017943 757192188 251520555 340992468 20074865 623279937 481215107 910292411 50099097 8797406 116100354 563617851 435705085 222435768 503041334 882729636 709326304 640717147 146523755 583404946 118095331 817815360 63905509 844092970 69761342 610379785 800724257 605249881 185702405 449975489 619308313 351803162 959894373 954768413 169031038 466018222 940862181 191460799 582797054 411846370 737852328 575351151 983664509 324745550 139151271 431117922 705819485 391319443 522162937 429570677 919116472 851786650 663268621 762568049 172143266 704989657 189330412 685116998 79381609 683669646 942367609 186541137 940027095 826090243 202500274 470991000 52492652 314443978 892412654 419479818 910294438 653933313 82155806 179530689 428393018 96201613 683644686 8392257 371469401 696744031 261728930 678842552 115343086 159270068 856499483 521256766 11735517 691412046 979735122 776594708 439079747 133044414 144716793 334661606 505255098 929105051 24922847 657917195 292827795 652486858 119245354 911876289 72987931 896188854 884438684 830352755 122245592 123656342 331301840 176436469 542492875 272282283 130394491 224861635 49621934 395951744 951651501 928598599 814140213 116116778 551222031 982744082 417883214 77967240 507848229 329050912 778795874 606808450 482307723 110999318 838389652 798394700 559644986 50854021 466436606 518833313 814627521 59708966 126060281 717785097 426388621 949601821 756887891 460483605 250152483 523647799 490295704 836423840 495625315 442643502 571894603 658273293 640156869 118221537 980713003 951822989 736764060 462353310 40823665 660306776 836820567 920599131 614087438 850316272 684518589 321973750 376393967 24547683 820381742 267256185 161247290 513890184 989723110 184839513 964716176 346374206 767147835 266788020 750889291 588288178 793271516 85359761 770981055 238295703 791933969 487678753 786006906 469078893 759013887 505407745 406365061 671883196 454679267 343082615 421716386 796403800 748166996 955490995 708399758 686979484 687168387 78587661 578708030 819850416 15441531 327711819 752918819 11079878 806187875 443253209 378423656 704756822 570859704 577122576 329765424 38995047 483357590 423154289 645395674 946359239 433271022 375922921 869596735 253587023 126532302 115532045 274797040 529742369 959699358 730717789 75812730 984458475 531783519 921892994 304749475 902036260 948729580 851109521 790880171 224477004 542200122 725764167 732246670 268222765 690836633 43270476 136497727 826694942 507194866 980589170 139490540 716500796 663045128 411874037 37083710 324651696 380648633 14688187 643513495 381388526 516344892 214759571 187806803 816662770 559551587 295064951 274228489 11998850 520622552 960659915 927274698 846985072 639303009 720695197 454134110 653289687 896434461 59789029 740664715 989639259 33618885 731582660 279202895 758837611 601869294 831755974 628151843 259981952 974813508 751873058 295201336 297779293 748574158 254520054 620662203 81985358 512724782 297237389 186119954 468482155 595952095 599210907 498758429 671274708 335000183 463580028 707784312 58885875 173670116 928027514 398398645 898957759 917254065 67097862 74150308 354817013 766326592 34273276 365333645 323407199 576721166 237650913 333123442 552066575 165394163 288560934 95868495 891254690 772290657 929716836 975004764 590788222 488187811 13107102 17436487 96534 850698525 577951108 122182267 60168995 321289360 714290348 255921757 538581738 274058836 895893721 70526347 322461818 801731741 177524278 535679005 669371116 914275000 431628953 669755110 348981155 698065484 395082434 213825202 765847947 127632028 886403483 111450503 963604060 4508610 82453367 266613734 659506646 174977011 134282580 248553992 960084740 984727230 606580251 197830434 148306299 116409934 377945053 55006883 756272281 130932389 251440405 431285619 834863816 758412001 295648746 151352116 16961722 552791673 100393835 463270786 736999596 476620926 731272915 397019444 93542309 1451740 826452676 779840410 177241269 560515992 297908877 871686590 996663352 909310481 522349926 707019685 801805587 147444800 485867953 641507725 673327091 413040122 27185720 353746735 328100499 79495210 648791923 661773563 503125748 773437465 278724289 790244192 98518179 826160808 969521579 44930051 397762552 493181842 206932774 744057092 225522515 62173869 424256207 712208959 838229087 703284519 316188206 409648262 993275729 937192650 276374005 439316201 576261672 438930234 282284864 885423600 266363884 635068723 365897941 446434012 686588912 330506701 113381987 511930603 265287441 422748090 386774980 752776851 493309174 722579588 717969980 966213316 560885072 793108945 897107385 321754152 227942681 329563809 209275923 63031908 824899542 722121867 777475147 627865430 979066071 732251397 191787469 95536726 871359091 458807963 307817903 758679415 780112207 182730805 670785522 264876228 331117973 562668115 33687742 638653829 777240639 316139089 865895847 952448890 332368971 901474213 706134252 869526044 512082437 521891102 641166516 620567008 716939330 151690789 931898961 581559669 33260961 678954493 579689342 275663618 417153482 5137667 587648931 359775595 112165552 869435888 740432653 401134987 393733072 451623188 995619384 799187833 402857330 135337370 204317447 737840069 195123173 982374601 579443719 310654649 815842500 609898815 27280818 812503962 335565364 990052405 252523943 528834533 201865253 278731455 85105652 419022996 9887631 369508107 693593678 537759065 979377588 743648671 562507605 276572639 934324578 103733404 815852499 691945742 338365999 965047039 225762811 696906821 935339965 78595548 707020459 433771167 153196789 721574307 579875500 449418801 232972621 31863133 557372910 549457223 705016836 829147630 956998351 572200364 435613027 793437522 862075219 700749280 834831867 973842913 249432682 622979681 903990762 960357260 77181742 883060965 687850008 844947231 973765156 980549020 173107060 176846207 658072696 178420336 290474553 162924780 541060419 89531973 601432365 494024253 564110022 982988347 163128030 595054120 520521646 665818857 374236389 586875513 250237520 110556065 482865444 439215447 314091499 986804657 53651209 530343556 575286762 267026846 179514059 388474011 216739105 634391656 556874409 2325586 762126093 732276426 373923376 900279735 525985047 368473208 658291571 161000821 515141071 100302688 930353746 74302990 949975090 627716844 739449270 244954399 393346277 192388924 167397072 154234529 613598585 98321518 46777951 691223075 609186727 705317336 780048360 359557651 107446419 506724681 686778622 819656948 237050891 768788557 945973369 332765863 194473927 223463272 770239936 512407972 324454568 730263895 381841409 553634879 370205690 634295380 319993205 525300709 295604 898249041 55600799 996917342 175435444 657230649 929329547 285091594 890458117 860148787 933162257 607800870 240200730 644425952 285075984 247856134 996104466 755078042 134182069 284777050 899791604 551117749 200993204 547069291 966433522 394717376 8651147 665528668 83995303 681142722 399560643 11070315 345551706 906745471 196005936 341800239 442279739 123874993 277813294 929969113 304692899 152101713 182165988 445832053 166682453 513257933 11833218 213954600 430462913 974383441 567396484 406727537 84825661 56894465 577908974 985851241 95959628 899833914 125682319 887669765 511736281 56360406 751706176 641187920 171540090 382309734 759237924 425532339 80751791 504154999 405064167 114553135 856934689 572108240 621445121 802696351 626920421 298207408 120674034 965092345 922869689 508178450 639192965 375943819 996308803 158976745 175444751 854160959 970740311 103899750 463204526 605448409 634019119 843471151 571970188 48390965 791580082 943242407 861371162 105555083 358731439 653924907 982457431 683798445 563231009 964853328 63854857 200867397 158430570 150075432 105211905 438298649 46324889 3499644 920650073 256814665 197673382 25054480 976913334 167834765 418280627 142963683 421721991 656550009 79477834 854451310 15343174 777246394 148107427 369027298 423157172 458837591 865299676 232412524 762499358 936615923 143211585 805431155 530538140 330315015 376838531 464042710 823540814 15208234 629190658 476768559 349293471 449578314 457050374 157206292 33188996 662433522 994498815 285172562 678634683 664386948 880487626 714355762 56153870 805762430 662750956 444928183 418572943 159930807 234923222 236125659 359134683 781153952 650632225 771621335 184290905 504052100 353248721 323384153 645797754 561543626 68292500 102893773 161074168 252116016 81828098 600198038 235587865 74270735 128994012 618384211 382164458 440410267 135061582 104313629 358091397 983124514 337417774 384946885 336720206 251220298 689100348 324746776 24497199 667758164 950752866 531156508 221228001 396188253 463027188 576390738 817201445 943283353 466260206 437510131 135732740 268579736 139209018 755875125 380292884 45744260 192597481 468144261 192115379 26407006 402123895 167413708 372641355 315018565 285368841 127088556 793057679 699276208 325558959 127788738 607513018 618543537 885768868 897840867 729653460 225170994 630683019 872964192 920097006 274566201 842267569 236892996 306798946 635481125 692925775 537301138 327265814 260454128 86664647 259075977 449766071 254772588 26329828 317600994 104486912 663262600 457569820 833074190 745974002 23714699 811218895 184457850 866425883 656964949 779369606 712141516 313052369 787492770 276493878 736333861 627545206 409825608 544825725 319773022 164093363 397247605 437696225 958158925 298701246 543399412 458796054 410639103 422533014 628328550 764355382 114306301 316825411 794841483 871334920 567378057 535474968 582614392 859476795 670986207 57938163 930713056 513364905 660230262 222154105 443807566 622325655 801294910 371529564 658178662 603914225 70508770 539763351 242478889 708688784 769943301 619521453 773364271 198805621 753123206 829768431 918185452 336967949 12663997 81569205 112350701 159754092 685540797 407460257 140439578 412247700 800201106 907387361 937381875 770347949 726366850 305963116 103750101 125830988 893389646 761728321 594561588 702896814 179711087 773194157 256496864 425940731 409527131 754822019 299856450 515309701 35115455 284548195 817063069 183150600 142558404 575282933 416415567 71270377 629125196 620127277 544007183 349019513 607536179 942769798 855786542 107376177 184345488 514037577 224035800 884111605 416202739 827772869 927694674 153658707 828414630 952950421 158731835 793860291 319612398 910347487 299517645 448950758 261986377 212279697 934482202 8474056 128817584 66630308 93581905 306609951 891093203 789952091 874252280 273825163 38378081 443895938 81594161 789254870 753337407 62720433 508923895 566787124 332699854 873006215 342029919 473452929 777829415 524824305 758731738 323152519 219816287 264802146 493234287 606637623 16024005 910977050 354501635 56920045 424863265 157707874 384383890 787962030 536196597 581935564 388609652 764590698 903335613 668780404 131320731 538698044 274855216 991577923 508729041 618013863 615720574 326190888 270132732 787492568 725029777 973282399 785056348 563393000 205143630 138485932 981083081 470866201 542061779 809958302 724233719 830770710 716746936 567588814 809782707 557734453 67758160 918711839 457579044 960723381 785031143 193347837 494703629 688613122 201906435 121208736 381222663 886234606 732706212 79827784 535245513 720279287 815641989 610069120 667065954 510985350 271437147 835054684 250710394 591406635 175246354 803313596 252458902 584410595 912191509 10972809 580625747 92855636 817834117 245598965 78898600 827455757 28700798 302561981 742601510 615520201 94649431 267333736 177921849 152864170 742546656 159049350 676013413 709390719 196657827 572395251 441323147 103186944 700465445 875613203 179276323 462784270 784830499 513807381 938160514 264688374 64585943 791383603 325144851 482614188 368598835 692325869 988774303 129465362 470690083 306097747 624693127 386188080 861961164 831402298 772489222 235302267 979692241 819131011 6577777 870515728 679551370 170663769 310649720 862354935 20359756 484569969 494762084 161363298 933266854 733980233 44661849 241007341 839808927 13129835 843023763 622657757 461712635 602238121 607893162 643318371 637475957 278597472 667209679 636450008 892149764 946212279 830280207 806753536 949357080 752418526 62492301 810112073 472275675 806891345 457204681 324514827 437330289 615308309 778734301 590783686 28866362 635891191 395877563 840826729 114444045 838932177 695136626 147506311 898241661 948254919 953268585 860155809 235614485 555898243 746156192 512120929 995856285 423175038 933867507 500813786 547405652 776460088 881288792 495646667 988289845 493951612 598595613 578232283 244512052 648981919 23988781 221406427 667706752 358129856 921179978 608748553 768382912 610819847 950150993 106851913 312525400 720683495 85383291 54486379 877499811 446735453 654231704 300227434 111571767 89787952 292952147 914104745 532620070 699338033 462636146 56269877 38262073 593441402 216227093 508107527 976103477 647436721 317426420 362043713 149728023 776940611 869623971 926304878 480164953 447847083 978169296 572292548 513861421 703600554 813872256 43292003 611161790 43452302 140535383 833397140 362951028 687258477 316171727 373783564 694686254 262165096 338668413 455931176 92158855 428247787 813499217 539809585 987729683 89596905 822892500 566846359 754430624 179780129 164467049 737529399 87740792 644701534 796990350 482889879 637366683 882181552 931724826 400730918 631782151 66191029 722813054 106845823 92368626 592501972 776198918 828024996 440873227 765868158 62696471 734931012 534145726 604256622 919164784 243995127 959708271 794088423 117938026 566944638 7125691 885125114 91410490 271106310 681724860 855522495 706283820 52519011 163514435 925688216 815593447 633400919 88316702 953439603 341131693 177118154 599231569 38532614 840502937 591756560 259672670 593007891 835955424 69068072 736455551 421276067 805234195 868401913 867963112 449462605 488128601 696850582 518274567 43998573 200191415 103771768 184371654 281827951 144019273 766742728 513019845 46972675 207820935 626812052 642322850 274383208 364991107 58158869 633241650 734099619 523950887 991814385 426409159 315491270 974541946 966822261 521338985 198577964 491906009 405992921 506805023 157566392 668666175 947289214 987843365 779736091 286217855 242887216 987640885 242364429 579389574 452197221 539640000 998645137 437495964 144169853 508610868 433419315 405093281 792458242 226031925 664288842 183794514 178135527 83107557 86163000 998127491 900293835 682588702 970177447 468417379 404761653 733038516 471674059 22026429 600022742 244026549 725356964 692502323 283164620 848915370 712420666 838871427 256210907 610373077 440486113 267937476 483529395 553477747 551253365 740243367 396764207 699115513 288729244 597537207 881066386 887683929 290443272 600284827 651443401 328558907 728347828 964389201 359396269 190385990 570395172 110322546 452199232 103950678 111430055 363532403 647200492 854845637 779265430 29960927 952478665 205138852 855847060 492484511 913380822 934397952 737574093 50105140 498241341 937152799 710150457 867300089 670210961 731129026 458765016 270716515 550221072 133643363 643377652 544967234 130534370 139696246 686356836 176127487 427143002 708051369 90504133 168978654 881467186 645994021 178515649 900305723 117805264 896875724 577466953 953498062 854280838 387850363 422817756 702970089 878469323 825614663 965913024 643599286 823891844 14224321 949023813 404713339 298588479 569142324 693117191 774977239 333481588 749269475 608150570 123463940 297573572 469581901 330622365 102103317 653780028 775614571 220577882 318303543 765818512 42285550 453274529 420381681 616869986 199307395 859600450 645720421 857497210 969446160 257504210 443610254 939385100 310565622 389383666 378444930 323059959 476001103 945933196 338543536 649832706 124449838 746330647 774388512 23203103 343533027 543655632 760675767 658738090 863567926 618150913 953494898 640384169 94488489 134100540 68289703 997402378 589657785 796831134 771365193 18397161 385847067 467059470 226331683 692488137 866010880 270549885 519152153 223990232 709575251 476870949 434570092 131904301 366180855 320878795 737829108 72241675 251664139 11100414 802757989 328575773 654928936 444366679 578865805 57740986 507461791 348929466 108562065 65403936 317239740 948072337 36254005 11995321 691679752 691549461 859019539 562166619 765092992 7062150 261711072 201104257 204461025 649922927 137166508 610692245 394435549 13304293 375034656 319489320 182165092 479614919 868497599 448841269 80577758 735301628 756445479 345825891 598026093 854781881 144116815 939757378 148549678 115568571 19465672 602686090 596865654 906099079 16758270 86733153 578637334 972704430 673428854 132569491 659110552 396874764 702324239 49192153 798349953 558969094 952768579 592832533 657549967 446009545 597295204 156750994 266166523 133501328 581373921 743715653 476577462 462120924 86500480 577933840 629533356 623275963 564499363 668028156 449958149 671951363 347835269 907495292 978717793 975696277 159805052 354171822 127399193 521348252 342240822 329610138 865815683 22194125 598281470 102592115 312100908 171713959 46208245 993226707 146426653 243040178 98825563 521063680 106198296 815476673 556402629 845471787 693301209 234728242 123463014 635109294 69368919 1430058 30963272 16716619 848240130 636451547 965293713 995764593 729533956 92059327 371641793 538966648 201843842 426174940 48397296 325096417 487730650 959415807 979424018 1352088 58865124 592047107 106755636 222149940 356839219 627274505 815836350 831945523 762470995 881719743 440873904 833788480 677231882 889867163 497517799 692124783 71934360 342811167 288443991 943259261 978093561 782192148 409559887 208482066 607728415 891968720 437487546 125078528 264354362 763554674 777383258 715212163 601138674 592695842 986722061 528828288 682917288 623198548 489913354 684155592 392214203 23936259 715032354 993998932 210671038 929967095 535697409 625941640 89962436 451765505 792386155 634780785 904207255 203978300 26786689 299008265 997323002 989944908 112014588 460066415 715662827 55322015 851075182 754960690 483498981 348029360 535184518 238161797 823851799 643666497 253698122 466909833 210119088 230840478 340501083 681016711 485174549 944589534 730664502 584073013 542113062 856396067 467867504 922690286 207558526 661969110 374972663 787281916 918039218 108282350 407894613 216164560 878556046 491833896 17645806 581630533 362133085 368883277 735647550 568507106 945887776 730584432 359117853 327265302 602099667 660233775 718092284 703958908 523117997 224119792 215059496 753351703 175055453 838470691 11384836 93844372 849048656 449137027 983135824 403017100 558187751 183673174 646483558 736407745 468622787 750318762 234581369 593330781 628410875 898409368 800640982 305035576 624862562 46006915 707848228 945930001 450615235 841785175 645960357 63479249 172460070 957608140 250532981 940133581 43397130 429222817 41866439 433704962 174507179 901207523 548488237 30084441 916590139 812443173 500301262 509745122 689354025 514031816 872201903 849244954 29284703 823110962 869368045 848440871 434178942 579638552 978635007 753539352 879258146 951690166 153622774 430995495 703052577 522040594 836868541 527877368 770583757 25658174 46830683 374567385 298933551 751439253 163412269 783693058 479621452 388375547 340404015 366836180 852039265 851255327 723162930 198899739 390326568 44747963 130959140 393531726 739484947 462563535 357830989 214925259 793848717 921979115 896885645 719391261 825677630 416867427 614775457 563588152 748383557 282589850 740593501 51318457 209805437 619055162 512519665 935293992 82230970 537351288 573556006 384235063 89396747 955886674 873235360 212325634 686796279 955013586 592849179 258664014 638033602 597992778 907525039 366653132 110077095 504494743 437261069 549506900 84454684 674464351 854264769 889174060 961428499 490397013 62327408 662605377 195070261 821603698 201989401 915267178 6414631 754043195 577963094 314215594 227574470 582857983 308206233 564442988 30833772 571150871 122004849 106442950 651001130 157808166 18367172 584479160 514317326 943841881 304334868 119507308 443150684 233279142 565863868 519911541 123501014 558124302 284423730 548811794 808693750 168834268 389353796 975929193 384788784 222587877 862148445 130790606 423025971 907655111 143576767 5072635 376830758 34663212 306625735 914990167 509404909 866441990 645344045 702470194 777814626 157149138 603222851 741348868 20823198 133092567 81872691 225717427 647985456 857725286 4593476 119127499 682423649 660646425 339199763 610377925 444972920 71767061 916400347 761968707 369328625 149070922 190859951 944965455 996196038 877159087 392750525 409327265 739541161 722412424 185665418 73854936 979465285 434199202 636060986 543148733 623083393 732463763 895272646 251963013 933211838 892679676 709417029 333497613 398014486 588803272 664797990 122176542 407514781 542547308 278324082 331082408 875380641 771073063 187964684 572610568 121788908 713927745 787039986 964926276 214873854 790111053 697284219 19070027 95456341 884977256 950339224 16128823 891637414 909949305 124311316 24195980 223014179 48913009 558023126 987857272 390055604 811944586 44024348 545327891 3466048 919741322 240638912 841663390 416827619 925001982 969051764 415343813 488141623 718205825 267329287 245255647 991317645 390082548 687978143 440327466 213693746 698923717 168813565 142180625 392412333 826361130 121901246 72857447 257770749 608022116 169876631 349656747 731650524 89069823 98305174 10055492 244338688 329332238 69418597 557902532 547261015 546064497 86840712 568308519 214440776 228207632 817968795 355175954 929855990 714775838 793576086 651173398 394375549 358453592 325342731 257550828 560307253 332148038 466941540 328624568 882104556 448553847 179700519 11122247 236629038 7683526 927230259 396363347 915646846 10224281 194942466 660972475 321675931 172525598 986298599 339849933 772070590 340322701 253387343 228640638 276706776 70724203 287202561 257470126 703864790 537784771 992713056 100639079 517273055 774775660 68068005 11796508 844980625 415136072 687433767 486437356 544026697 200606848 37139092 406423005 232451162 493079754 564683063 985393187 777645650 273971621 119038770 962776920 880464954 685404057 815772355 990513603 849581780 976597370 629535360 257001108 900598493 142680483 976640156 197901603 112646730 512988477 519918114 732771894 867112844 221399927 871832118 411871545 902667982 128212685 241430361 281331077 861897011 619211842 886057635 26741147 355833882 661122727 824987913 61460584 240621660 386909140 119893654 730301569 778072458 630372844 479179699 353180005 171047729 603459739 111036000 818325184 32365591 619568728 546970490 576299940 38460285 610688933 368190453 222728655 66052700 199653964 82746401 330943209 654006954 416989857 418033895 501978564 667784852 785543364 801318155 647452060 734139331 92305374 631852649 924909911 349820057 423545696 780960057 910117572 473277810 838872649 277790028 609176029 661005798 345957471 420748110 117671942 30172163 903075698 808954884 718418765 465230228 438427293 520341901 336149418 682980702 886702982 662424739 62881342 154983519 652843932 516742105 479381 7808784 927378262 598910171 112272870 809580194 533121911 680711091 272422991 762740802 83998286 737810944 305147419 668778582 471367407 798727230 745520381 960828350 373530749 430955267 615956820 461850902 879053666 690098237 706233191 703422448 755775122 615200374 827815592 807004701 996681934 168017938 171973363 717772002 809867740 566579342 591821261 167802436 96491985 667729344 182236583 242511935 689380937 788123931 452913433 419134472 116531115 481629929 287459881 964289872 148066407 114887569 966864772 577459585 547124281 440709840 804392385 68190976 414945125 354668289 57575075 399896683 787990522 254598743 747133525 898913243 151671570 701263391 831698093 655086624 224100877 296958465 127583851 108287497 164881371 397603646 298572409 567742875 713560625 870820336 22923050 847517527 629287120 756257870 919092092 61029238 677685443 815986663 610746968 233514798 973653918 133318372 731526606 506352108 110179522 6141256 313122908 850099864 265805461 897969201 364091430 88997590 474493900 113981206 654921276 578902081 23181987 736989960 485907416 406898608 229074977 406596083 496888223 12068467 700371287 368062427 987120349 569057173 758482079 670807585 555768011 950788377 8891102 144298686 952513995 211873597 462201540 115115908 989364391 717267388 866962952 69873506 500287959 26089733 794751150 320785310 971720378 550262151 935790659 672342298 733148377 491682023 726939933 939039121 869792041 172853061 121181597 715886808 691321159 733784701 191479662 255784480 230666939 97466721 271454917 711103280 100954679 706527489 165008800 425458092 7888087 326759909 619866889 49874003 922686817 517012814 95635538 885829690 78458244 901315707 158128728 531343891 965331738 198678495 528197826 773497195 115029351 214174317 365044033 762934757 863391833 44936911 211285711 594667649 168924104 238323879 578449650 656719065 47137973 154685398 868522231 325842016 663416972 663040947 344175929 611481507 758018147 996640849 246187097 870474121 443437115 874792892 672798341 416200853 867746876 899963705 450287283 494496800 441854458 156070539 908111844 176405409 51684276 707704618 554136163 418137063 57807761 794177419 560282886 333093466 538463459 460554845 350898281 169657919 602579813 648627144 810421815 940790771 873703550 833015469 288446563 876122157 92665470 153665514 662051944 382957374 466704862 968106901 290493070 979525201 567376002 324836926 368576294 908022445 84017399 536467503 345504714 219947247 458964406 807049901 692294816 150501459 24335457 929498933 8108438 67874282 406793987 435971777 524239268 679146978 860010322 735173891 801511951 342098115 582590446 531649959 878310306 933577902 418829729 743106450 158489588 330577054 753426590 104167975 804248230 902054824 625694659 597575806 936087716 806946364 191455193 803449004 533847393 852339555 369180880 124631296 483948061 234520065 66552582 916464961 569684768 624626706 917032575 936395763 894283517 595461102 363171883 435063185 428101586 493175174 194632484 250777553 573759108 252879782 40967151 219337957 133999621 455373619 739370936 634329270 481709712 118932588 293153688 302905385 894700776 990332971 441055184 969013339 727776158 404812579 685497613 976986086 825440330 289390880 547970468 209221148 79687887 926150220 945479892 827354696 137374361 649987686 269959688 570029298 619839455 775758858 177063444 496560921 692721891 261043182 471622773 508115320 121657134 784765472 787554452 779095491 794131159 212066123 65467649 451820009 318945723 674991088 536289977 230882641 890158787 793771439 903558241 340719134 178618147 341145213 560422282 483376749 797402518 92448237 310253549 229104532 360743333 15135338 81060014 710812514 473584351 578031736 363174299 760260451 732360736 352973816 821207148 466292251 315084492 721193826 960855042 793734727 728446482 163511562 888132521 865896481 117225003 632046173 545319511 164008091 276184473 78229795 360301037 152799392 450331243 693326012 508798067 143276632 99827061 450366821 47009117 822972002 370769818 499793778 492914378 330880281 90733316 393432723 657775809 195665873 474489447 324164368 191277172 743735832 508722243 202266895 404988798 664151799 424316961 76692939 468734758 217092145 974781395 305992411 811125148 172210560 459045557 832826739 684433721 938853853 578750192 948640668 44971456 732060854 412009139 746986875 406539681 55273783 818198394 67307665 143511858 501906820 263238473 838530295 464574454 737027066 752438255 310004383 722507736 731150451 239362118 342246552 204326510 932476288 576835950 10064456 247813176 274885039 107198487 564761265 355648479 516141764 698310069 469269934 724061048 39121665 672390603 580148532 74026433 556550240 197160227 462760596 421476192 951618517 369837330 594858933 217860649 662827662 137760438 956225116 543810646 284743476 760013881 997017445 475130318 598434602 701312013 760837640 730731360 415825354 914405935 970457879 985090055 19801517 121508710 628246076 993717285 426981857 669508226 798575421 254632137 420762930 30746527 125044026 402970347 80682339 385125217 977530859 278364332 237503091 971852344 411151587 982386841 87719899 473040283 213493969 84839143 766838220 789978446 775738556 906474677 336204403 264827549 455159108 370398542 481579319 479700896 641082854 28189030 510678007 36463735 39031862 900651098 717061197 213952141 219802403 551734642 608238287 861494743 950684216 892502305 411930699 124001812 15275735 278627393 820620552 423524364 861059966 214849880 577107465 683310290 944322819 298504151 813601866 447796483 409637849 106178391 572451843 737113094 134954827 104430300 142724578 966655819 119237310 401225748 651359315 313544591 633585904 591667862 477164729 808880660 980525885 701203237 96017075 418245098 279924950 953127661 910149466 998407979 628428297 267285698 222718591 188448312 402976638 247694949 658286575 268257535 597658486 731764160 140734640 644577334 406023436 220552743 754876995 719783582 228941173 487231894 781044194 598914114 795556161 82603511 407395264 183560119 647821209 747206747 952095310 535681372 173312385 162043454 245842802 954884761 532516117 68718789 806411727 881597729 579525837 579214336 227608065 349292593 615949498 51801130 790450655 186076624 671080904 312974566 862784442 62802959 270464764 151570049 697196954 503048264 522882742 783421236 423971461 56102497 840251373 647511649 737929657 709528584 178993527 222868435 196567023 508635125 638277440 917095680 3822232 994988845 175057295 581413448 340252449 531877434 609703494 303525940 814508080 178389110 855244833 811675321 522164966 927246655 778842611 992668789 722354716 954441537 643064814 93075950 800910248 903045042 426728665 80716504 596723607 470230414 530016089 692078413 309932402 850679520 794829099 752388372 101503355 478911995 222770789 793895644 524219374 60735674 692699834 955129215 465230914 421980102 669825204 159776578 883099240 23957453 355688186 550933777 766643208 716879565 495472521 663554501 355227592 356425545 842429693 635947871 493448326 230619023 155224007 182177356 652311195 915725050 730017653 653435040 76715288 949616428 327177199 844129629 68837641 552255825 283551413 436677547 418792630 216360288 111143972 365851167 109677791 291986267 240208048 858413558 676277245 934289547 312108073 540732504 880638342 204323526 167217912 610164119 556751143 373370795 717035872 768133743 993564681 962216419 828654783 268227397 390121486 74865247 696657100 382315370 195234578 612184990 296317144 398182487 318939692 576434917 818239247 697280752 509986540 424520582 497741238 944506563 74697372 280931356 499427948 635052360 539422594 53847499 935668074 844347168 16413722 408848258 226697413 431951703 816009821 72895802 315889064 72203427 131034878 497800501 901730204 683968164 993939624 800600385 174316994 93654820 823008067 406266357 643920405 30921559 772495663 1040881 571258539 923661081 267933317 394095391 20677362 64023604 495509595 650677238 103336181 279998873 645362686 206206643 249058453 709914787 717359158 585796767 255913682 578062426 451949191 391756110 503640833 897007275 553244268 524168156 116075541 259920306 345030812 610049071 532430808 38553841 108028487 67408954 316325936 145176728 84167255 145484085 947758684 25501885 374060721 658722535 528745014 962331299 855088499 931516638 482494321 156671989 632628277 275803060 369641690 545169929 373695818 795761737 442411929 601477406 257230078 438360845 844981870 490950048 381725911 356936500 769242358 761785697 803779285 444060673 584303333 215447263 865642675 547172862 778108746 926495363 269287718 461966400 429486544 466669021 972917019 853809573 860568057 998573802 562855162 247608342 935571043 667154768 140961255 174560711 844479493 576595870 412998909 656457844 330471792 239238799 452728467 419266724 46051855 154161221 988288377 574768359 850188137 894904207 217163321 363080985 287626844 481434917 85104728 726664094 800256609 651794152 838558100 574334630 89842380 769275685 24258341 102279016 171101195 169605072 251682045 430593896 812594404 269409739 162669322 78774194 203154361 51003422 570229361 500587038 430604228 999919422 27365074 594026124 962812509 794480200 870167432 410001959 691716657 830369348 251812071 144507556 646978698 709354852 808184190 59854721 547638923 145888836 720536917 845209928 9948274 111633705 862203181 456553163 554717399 484335428 503416772 414327399 721320425 202617838 480267024 747656515 290297525 683353067 37092225 119392912 186585184 50573993 844990785 78010056 298830185 917206911 544530293 175379696 198676202 717826288 62103930 119489496 827314646 724602856 530062890 588461911 546659386 775152379 313283863 94577553 813496445 374033834 398854092 677064755 210990241 941016479 750853393 812943283 378677634 604178413 449007141 672523922 609339923 363109459 239692803 563774107 322382502 12770936 665136799 56933411 352277538 322456877 522295336 720107848 923523916 601719216 729637958 819141940 82701825 437440741 225292634 517289305 682938999 749696668 438647234 23962293 996203649 147309776 767939348 228867341 3482314 164353764 844366687 352582706 86234646 231882469 545895535 170491713 199478406 61341900 698150152 575898588 86131922 691077051 628823592 909454708 103274382 634587453 953133126 552409216 178167399 619029128 594498711 615198149 937787237 151688635 192962629 328759693 637424169 996976930 923642808 487553265 98893101 256437871 232712655 261105426 556535560 564905472 694099237 24257113 585641897 329422366 34128206 155168700 410463129 798976057 781851673 457323002 292832572 717194286 87206605 177053403 323127309 170749827 877790061 677909618 911128550 787358887 174514678 982468701 247860792 173566004 546757022 331674369 604260685 737228335 352621588 934605520 345681290 427181380 809026756 361258884 762347696 656695820 698470930 729728867 750073112 938568 743323803 215039099 899138805 353322532 562501241 454924772 106007955 439593335 456920701 114087171 188714139 573130495 881543541 128390851 115644238 700404136 412239205 986894043 456589768 403692995 451399887 210315532 748481596 26041936 995302893 120697954 985396795 931014710 386217971 295708272 331154415 450868615 757715536 354921110 691064153 14166719 158298091 925634876 648657305 592048132 138499175 235775254 559558180 679501924 92420449 810380895 187147277 261178139 502460846 764932639 812056894 728504012 52318368 992236904 392119741 967829701 324568384 572074642 510935274 133196862 340048786 20337284 240473789 855134616 144063446 182692332 112917258 345795487 963415490 556859523 243464894 658766537 34393547 221428299 365648160 350404726 149432923 667570898 47325971 397341232 278148377 864169071 573382736 325048554 592916006 668338561 806480558 180038723 684356956 489823669 636879196 194898370 492713871 563749182 882160675 966688280 166116813 11243036 942969510 632141411 393803423 578619736 319684002 737601383 26388807 43884611 511222832 846287060 593479426 661203900 49393920 979122821 348569157 293968233 456401822 847701948 923560450 71471866 797764015 452352617 381437154 353146219 747695154 987877986 995907721 264185407 374720704 401607338 920907990 350037704 578409165 924955819 507088674 671618908 349225703 458061181 656315774 142260894 747025396 865389343 337961463 372916413 830938230 825871290 863662547 464601261 354955207 414728931 154173651 621250929 814910303 376174808 718383729 17255763 465718283 314223551 322096929 557639975 545858357 54200556 636224913 681034125 153572897 229086745 664263658 510389294 779022123 563600044 633571086 680224508 717171979 566594806 42469850 729998708 642977810 657858417 215038051 202637276 99622252 619956223 421466426 341386887 47760991 345372975 578776746 460282125 485251464 209345401 237283318 753685398 537912354 317657726 242439838 342646286 180805439 779231307 872784280 214897007 903748878 902809748 325791896 965783292 387942934 816928251 985617226 117849985 887853687 493890376 100067476 673421462 651095853 240029871 750660055 431148507 898105166 966812943 968441901 794606651 466506568 104607535 124810665 417526571 236777510 399052545 885182108 884986857 914017482 124358369 597315788 93072575 216605489 157619925 592155324 863133759 242821044 800508363 965461224 874222214 702651459 253984991 956468487 621458042 71855017 95658644 922822985 113438478 441277645 772228120 806812057 777477755 389662189 730732674 46932698 234631558 583946210 275837461 214936107 913980095 594475872 217127292 9506853 709531069 395562548 133290253 820991001 76950628 641306758 914659849 532761428 789966368 895173655 794298839 739781212 782720809 647304577 789683534 107082289 468149696 817438076 533170153 561491343 323475822 668524052 6487314 731543081 133149256 98754037 164422490 792967661 258517551 760201634 494477756 220784195 52410890 660234423 100579039 389233487 671868684 441411372 942507091 247308077 502420978 528048274 715966928 533988146 945987139 959809365 366677628 831075119 994998160 320694266 687634979 234481838 995613875 56926816 404939902 977598517 974763281 188847873 524051567 826318464 393894362 612950575 383206209 144722888 61800261 367575897 533391337 876071168 378546646 914447941 673633865 138429716 181985690 802800725 198386282 378631722 965560167 584638404 282785214 353523938 522127391 598528744 970382950 622013336 539576811 721657199 842831975 945033630 874234241 79551395 274782964 883695748 606019423 588619688 499486634 311423826 533308175 24146618 150775244 958757322 955188324 770125426 851685772 15481768 963987641 161661440 899119940 5143523 614180918 404806511 93874358 426266091 187358476 99087077 165344337 567184618 426722485 138378722 840673901 718278917 361257271 40047230 763775115 936045210 424575584 545931949 387588759 650116994 946663176 521383292 589112872 777575501 126403668 871955538 494857660 295557002 755558126 948906034 108441086 837738750 693593168 725435637 546566402 949059817 909548536 741608082 333338501 98602823 661513906 7347288 229301295 603640074 827973076 963615280 37426898 389182306 337314426 460292573 605874090 274986231 418925264 764091965 345520796 304913707 947675462 555740806 756950649 923423578 836756955 746691980 434036793 820809755 796391252 22695671 440165442 297380478 212633219 44711055 985909153 481381197 648040322 382477682 324213582 641668685 592982775 493712729 905506153 452404092 546736464 489023961 929739392 139803730 389433862 300789661 638127817 57097473 513338075 53846958 953578338 758357943 434307357 613462701 498105237 179013081 498611427 939234837 691394584 187907911 619477580 408534907 477029446 758379420 383481029 330569679 355305833 421487469 967346241 851798171 977001458 435275655 632485504 756286272 646034620 246690866 168159306 879961149 210343502 847236210 729536179 451007082 187822615 524895042 943467094 577879094 205901746 220629209 597102236 240170222 480681506 433777639 673043188 336349175 705933588 776280278 754206746 522340369 644152865 359131915 585011538 169574036 776151050 140275747 806899115 744091827 842551804 474529592 405450558 705666237 44338380 790450204 490947693 118317913 967060538 138722971 179615526 898997959 995180079 828975546 135117344 518755875 744349696 958991100 983371291 501492899 293621674 882665369 882819361 809623765 684613910 289896902 61693385 652381156 754260820 697617394 624784496 631829202 472932833 692140036 171642495 900472765 12623843 208033440 192734122 375650075 562205545 163081825 770269997 40244991 587039405 797021981 85835535 475893332 105703763 524360998 422526816 2057246 609211305 439664773 752292220 492883134 436788199 558591551 997263687 165805356 167185262 601987986 486554736 130414652 175154698 154852150 726975920 884513756 483898674 251167901 673234442 122768978 209263940 741848373 612835338 919869311 725198027 117160354 311743240 175884320 656095675 637300486 463603300 415087881 634219697 408880187 865232585 362635882 579137077 956494102 423948651 277881612 443051001 419401123 116235082 903842706 236335128 646236013 303292015 597612986 876786266 824601268 717563692 417459099 354164076 769319350 447175518 920247527 142040618 628042729 394952108 243914792 13978839 509538108 968547014 85092356 73201249 838741339 876373672 205513850 38728095 725061354 403858902 543268899 415643284 546358982 692877472 273243508 457846187 189155657 218560605 939280377 564481274 921486213 156142257 199968665 359961473 123468421 111719624 899790294 520623722 844644497 576932506 182745867 752328264 481593448 470742567 393442734 497866842 911394949 846976698 206112653 13846982 457552476 478759976 285818130 889254112 376410523 728155151 300469377 988519522 961135979 262752025 641710391 836978867 589167535 274970680 632585962 946533155 616010306 341024745 761368813 823406890 809005626 255520115 391902058 359851950 726127913 272800295 994982567 566861371 521125464 212893343 57982532 705885258 405170187 729568256 973811321 435710077 682320066 811745594 339463514 194964958 945850483 362449988 937028116 219619621 920166355 802006370 903851055 18973169 908916108 232563297 619169483 875004939 2320261 331769303 775496677 471286440 634076703 34720357 139329937 567965093 974376308 459644406 458801471 608366795 85290648 116228351 501399799 814682378 309362394 543084991 636792479 703197631 522708737 430948734 788452657 943226863 758331024 459717071 343140871 852169611 375672580 515289551 205393937 91260589 495850258 403640678 437900059 152128215 860348396 22109314 288997130 673202232 656975483 681102945 494559005 560095976 902086819 684006597 613484333 147708456 644036739 395682111 24406255 385628068 380239796 990003302 883322670 275388082 674825351 535299871 495814419 402254227 108861769 577808852 79223135 772234415 7552897 270949311 124566445 683532762 234434350 594242078 918475698 541980563 988386826 636085629 241475711 505187905 967699147 363074801 759832507 164725110 340433503 92009817 983023850 14398254 991267629 622597789 976412331 238178062 9849944 535596272 955567091 361085351 339655421 466010640 935674708 982593970 116192113 300569730 932698171 168306514 253764229 198048472 476964395 826798423 5536964 96354540 999757828 960114807 247336369 251558180 513866560 823486613 875493644 738752430 899906866 636662780 59809803 427697091 621061191 466177186 501762722 685075685 90448710 164378471 350698685 412367394 380467857 168123733 162130819 434773328 379597668 383522527 408213650 550596689 273999635 352695076 617238855 641312846 264979021 389964074 743130101 197659390 478681181 668250405 921729322 389784030 75825765 378354095 165510895 232207735 41486498 243195663 511614982 466338460 567514029 685764725 48293164 399468459 979244470 237757753 89854550 493235657 494844361 648408097 584654837 735441448 841771786 912720025 502500916 864615235 271798266 467062778 244166198 698934302 13669297 770455749 438258010 785593224 214603043 954963943 859154553 399375706 685617246 868199925 22487332 801357750 501642695 264570478 611125480 273161290 248387426 706826494 192928395 647858573 148282889 961316535 556203342 319650302 978716337 937215831 956458538 773794154 201630122 512692870 873023253 490508325 604765149 61116182 178136124 358026317 191531534 957609539 18221896 136330507 250095129 69030643 402059931 142067155 430992438 417131253 559948434 475343264 928479798 519453251 717972674 297456699 294888645 822492737 701385020 645016947 322511528 4044029 941371850 186463332 384013822 664651375 800472881 588002994 465360769 424186808 315167856 984708044 781465539 855906916 86054397 907413547 172170355 136559530 142312204 186490002 316762007 181312936 54035657 490548045 909666001 905185449 479525786 389003636 384782493 478678624 625736288 616295462 365116814 366476588 836974004 972736464 575012758 723826004 998180652 524365670 329485116 21492298 517139605 31375270 490436837 494718442 361955128 279756378 766855181 242824121 690562838 521671059 342608013 817348648 374761006 24133872 563789781 357092303 511401396 284853975 556195888 253786804 230098265 325724600 648776708 946475908 347818119 194053967 467793681 944761558 843513251 654691808 521464751 154324589 974342475 149294459 782616082 593636980 898002840 514904887 304921479 993601729 441274203 292424312 265794486 635414036 863888224 164379690 465852383 714893655 410617775 824353285 694098975 464579805 904896200 194908105 540251818 642113956 897720036 284663425 263047952 332150933 274840377 690967490 393197433 24729536 861097780 145943786 519118827 777248675 433247677 522031203 549642625 486908002 922997880 566552799 828318642 317210893 617831680 608189083 70758802 515532510 116723756 434127006 197970185 958393466 919694156 731826680 833942559 672238893 509924715 422215941 51601970 154576944 279670412 125822634 630101308 483579876 31721710 854666132 488285967 541101846 404937289 812241789 55263386 498368059 70016272 719240296 97583395 988868786 72299950 114320866 656754572 15365639 169182667 824747073 786194320 912144684 367629191 777205222 128038148 223983551 203122363 451869820 162106648 854971720 878434876 819173944 7389589 946809977 819127577 124282137 110017055 485872750 855531994 599959078 882037618 515681261 595249601 2174133 475675303 739653285 197686282 73701280 224903789 995170416 829047084 869251215 1936465 99121298 542229526 113355059 387790328 77403385 250868085 95160454 358573666 608727420 966270187 750017037 531280679 357182751 693199958 180835096 230205883 263819595 998534416 595503102 838278827 109066519 698256171 774360931 250718430 638448259 20514483 648172404 203977942 171379641 724633838 547395367 894090223 408152653 55625628 250834814 230598045 982051452 317961784 482800322 426612911 465925230 318576438 309675465 919820432 767213428 912599365 129631026 319425154 687238988 75863693 183227557 399300835 902529370 208629231 782374421 849219177 716689391 259706953 662064895 159587687 932618628 296718769 300448682 253105416 865073149 997908663 178684007 821838992 605136359 92342693 321439441 699007648 837210555 286888896 227369739 157990512 209872155 299807878 599080198 5466389 351399954 715263215 146384826 630467258 966081622 376023725 69910633 439320552 525140103 441797998 853098977 136387776 514651503 122951190 199684024 601146428 381402945 183310344 966009744 864300916 820179675 491445340 719859282 99398869 736124166 109127975 922145140 454053225 508758450 166126776 658894901 160759315 391613757 625061078 429104349 717841105 380775850 985000453 671046656 128987130 23501292 830595776 356837305 6784384 284743450 241858237 64884465 947878445 640311226 160504366 263881367 810754791 478250232 53286652 214341862 800348141 3081709 563361292 818991268 141527577 506968794 778884219 843184223 246690845 106853996 240586979 551294384 251658696 74062071 67545238 358069369 471416640 223732669 481457375 638584872 887635015 767549990 743673926 182918388 982269305 872477447 167651786 782095132 771359625 872657885 580067878 236698669 321181833 65403920 493253902 600667706 169049376 491239475 796600433 258244899 411635667 893750080 966757814 63669712 949584959 298276829 2782977 971297141 171133018 285824923 697687660 320190670 393372599 66485811 3279184 16866657 13449920 471121097 871768956 780457664 550199292 569753899 803826809 262202310 265821000 966430993 340639950 202563031 586189599 961107804 705383224 646259234 154276308 428442456 343565806 467414752 632483541 721117179 673521125 808743572 120653799 784127270 822918663 734953802 310082158 377187040 447067260 840311770 450018979 245644960 295220195 620045603 752071389 611729026 817098903 597503826 610218699 882485902 396407788 399337755 891923126 685852149 926054256 293701884 508179137 155179605 308313132 876260990 997313066 234428146 340972515 146285429 985392776 770047997 226504784 324844861 40477452 866326991 506046569 478164476 45594562 33719339 58474912 811352037 826488527 198356865 885367069 854343793 960148402 538020391 499316999 695162277 664097925 359241120 80399290 223006544 503470906 390665687 549186832 962443339 501832928 138000482 408488858 883950009 504482525 207640001 629417446 613695046 65036851 478606493 271306680 52218218 861172925 389024523 457029458 702418597 964673136 29811145 28151982 766022338 487254684 493068157 746589888 895363861 904958251 521860603 533280950 83583167 785513950 534945661 397278009 621723110 92377492 965613546 269990316 532567807 516554629 168789009 671223145 405033478 429842560 828306156 311620873 368329666 792910899 883371744 574823322 825782020 938768481 235994873 187367400 927524837 487013930 306286128 222168502 341272845 565239624 788407974 839444228 775458536 232418126 884618472 561669448 391235312 988459753 972152107 111289527 935308008 969427745 843603598 34334587 864416285 768345238 468242524 512614139 958513829 261291716 408414025 956300568 737035425 232862529 713265330 353976172 366665596 630154492 690054111 703473290 98097451 639846781 10826563 784499523 83669868 897236009 920476599 71095773 258162441 377473917 840718276 829250395 204690196 412372560 154020568 832692922 371149354 537098515 238901389 941747247 3012018 820933906 110564327 785283179 307615005 293837745 723464852 780714457 243610405 85630897 116653099 459636188 990385935 546038378 303956335 393110035 514846187 115307281 444992396 102354839 16643536 679340529 486489942 490763321 502798626 41130931 795007118 499730374 306336206 963028632 151362334 662563652 395048586 242567099 537005145 371958324 518992407 402758737 922942014 132781520 174434433 416138474 903388852 510603339 726703707 378571951 820377293 666655766 181447172 362167971 61810180 134908695 319514854 159182564 744317825 757552625 336458931 917875178 902326097 650315584 186831529 781804996 873304496 216788699 281386189 413975391 442637889 388171027 910409521 625549760 506260817 135550448 427255599 403174726 760091417 894112376 291001004 395522283 164351227 249072106 93531992 488863618 581906626 798809852 614542315 850374904 107126756 834984226 942382951 873948564 390278849 525579208 86086234 841254712 334353378 319645588 422735898 278322335 280700732 270125479 936712200 947650207 683765101 792974554 373761232 512086374 826857211 248315139 273452453 479588799 511273370 604019247 864702343 447370828 728074084 738167783 907287166 350035146 594068000 814846573 443213533 968372562 737514109 890190334 384328834 340862868 137591637 377285647 586142738 340024859 441691885 109069457 27793983 645368717 441515569 328692014 269183747 857149930 950615034 52461707 313725156 244660682 646879817 674628486 924104240 771236769 668162443 665237624 877893696 455457533 13397972 706184818 678065846 765321667 324084774 227336833 729704128 207936375 614821289 614831339 814331476 792671346 201434354 864402544 742526836 500305708 337855294 369101196 352440681 100717937 102121397 710652849 407784458 28380077 908403369 123869327 693374708 240062498 7065302 250179918 573978832 693189166 746344609 721662416 314203282 383251336 386514779 241066481 812488373 531969410 211781245 331910856 475743362 169433669 541582059 992464869 149465416 494227481 389056051 975529619 28711330 965371548 628492749 293653781 974168246 460673032 982973530 818259434 765571954 531659887 671348454 719961866 37587407 419689216 806083111 935920424 576723472 483497793 581353405 604983536 588123649 483360340 26463602 391125575 436039225 197792308 262557817 195420048 956744026 535915767 182625457 710637795 983819598 56312331 251783649 524803926 615980169 289314170 66232059 5034038 576473419 127342376 84050778 226652235 487914205 232361489 521500165 352219929 442260688 341180302 184062188 97387035 934761539 825284750 128120872 668449800 49457436 109859038 736342844 251687440 677580619 669221988 999241816 934743326 36512268 268140637 707550610 702385941 909586211 564685476 325915693 570864659 623355935 195851500 430825427 661522867 757912985 632967682 703050204 621739588 628308084 187447054 540416647 636717077 997487900 395166416 728379454 105339563 536479433 136677604 423387860 88345094 502796987 12857600 286485703 195744738 777319292 309334579 665922688 578789105 897933859 512722470 651092367 238543395 665290125 421140060 38643697 407115743 904339364 389018994 546991948 648252233 909482650 560348769 356457519 318850428 874419244 498506681 298603349 189944527 778063072 729741542 638273248 196291602 854613833 116618092 535448479 469026255 575780160 400162860 846441034 152650123 811532074 416488095 829128386 673012996 869685046 334707735 21189460 592222066 111731869 148301570 246641140 797254855 546352866 653042728 358314372 179353841 307795218 833492458 96913164 473442069 621072643 616676739 678329089 567148755 332159638 366285896 578427520 896508806 919131894 625646313 928652433 991153538 390253015 379978928 314439526 197256534 941853370 573098686 835858843 257847562 642086 430052690 167540597 952820063 812385006 994964739 521218597 540877075 382945647 971371011 40223492 623928348 974943951 606601564 942941398 888704234 478206529 941772340 800352009 788006823 311901758 390403850 548017908 316453752 19582411 164577016 761363738 327907770 613904824 243308785 437062758 396991303 363110876 860232961 503834991 571777969 564162139 112390034 336517043 352470147 206512354 807794851 214006493 695166597 446040551 713526032 588909056 577397494 640393195 939789775 661469403 635731665 572485817 459391278 399111956 835883531 643929254 541217304 623654271 870394064 125698001 661077839 938600791 275559115 96164194 970849968 968127361 87435356 182228684 955241076 25689037 745398241 956802828 900917867 505781302 499479280 416929257 366572352 980048415 179924888 87087924 220728250 262417301 577614245 355747847 50063350 513761937 117251035 798255112 409823408 854350901 545611064 959060132 408593017 242486284 473715764 553517142 657209087 909819724 157869569 223335903 851042378 13522452 79065036 404051341 919794682 17034928 716276220 135170678 854634636 687158482 75427184 840058811 248343700 340173016 62681283 630153159 852710402 821694219 939006857 975818128 484032863 184012507 443230609 372898770 272165134 738910757 83348514 630386264 593464973 561832559 114769728 403395893 645112755 573970472 352289509 31501828 457999345 799073258 346973258 999644461 191991187 473400250 184045341 818889505 330197758 537472068 47963338 368253339 580954609 494130721 798028725 663635166 144218310 148627218 732661371 479770363 65903023 363277123 985707830 78975242 652281851 611120267 360787640 891562093 12685136 857931176 98800076 144030226 264564976 492192646 105617017 81179567 207058678 383066742 779001152 172519686 382097816 841894776 836275803 5677344 617352292 323879795 103953150 877224339 741587332 157163641 554974872 590645694 42652924 179492614 146713616 41830410 344418792 407800128 968808201 815401256 501256129 763342389 970028832 386556247 862737302 942599969 36417323 858794908 164937557 718610599 952086137 574977289 752379137 534024213 432593942 499572216 776830970 657293987 808150533 842421071 977053242 490928305 265121926 790348732 742593940 361753870 24689999 278521592 82688757 884794925 755780309 913138950 751641509 450534255 262649730 485462898 809467012 639940702 610090749 472542867 981875535 109899245 113519463 200126155 11266010 793531323 546572954 507756995 405219668 754846030 658995050 770928050 144396680 929352026 737756901 620151957 966931480 592765690 461698452 716253045 786282946 216877299 790922938 484228006 666035101 416227061 604487569 825687044 426315866 188308699 737215634 188816437 26108805 8941543 900573867 192062443 225069250 68009481 273330312 115977761 659631890 503367447 908347340 718167643 810195982 755439635 464916054 608093160 533168936 657235050 131122559 778905889 369721070 622268721 528234840 183872681 364909128 74340968 579898862 587208364 414854583 150006840 817194120 18136098 384225942 510804022 785067236 444997130 359515738 2579616 220787839 868891825 774881748 811955612 198868428 178276587 85541483 23391357 939349369 125347670 430243683 200514304 441737647 316902299 746764058 716105352 730858320 737308590 322001480 506473831 852039481 219778315 763605308 340520471 759071615 557450745 516098851 368296058 73052852 915557576 963325250 563398431 7639328 325805332 692106808 148175998 612851209 421999873 885289279 411192 995265774 593025150 986809706 588509785 141130949 315501188 903206630 2073752 447753538 912622678 232411194 919261075 17755665 649385153 484629896 624896534 753674265 659824986 88519628 12270162 370032312 807530436 632478234 539942695 191308555 940340969 635281633 402713436 390276389 871966270 65162540 529911523 692794708 425087233 781047260 809975832 545550689 233154428 423007985 752613632 363257806 208739905 498972353 218817164 984215831 97591149 982438205 77969877 702920435 667290599 737765168 341315935 992284563 375501983 19572097 542808152 75880159 414532049 522380909 813865431 441869245 269064770 173097167 327411231 157601611 821246079 409491291 275485147 340450850 395320354 652148700 344718177 703783827 324854030 755741307 418454513 571696875 849379504 445968120 789094133 564637360 931476798 139522544 860991297 362102755 926786297 555465751 737763409 922288445 660516716 978251645 31577487 125834356 766995628 22701771 899715980 346418549 128299159 863325828 428588355 905923497 184650263 557319238 706037595 295357234 609866334 111303688 87415651 534310444 810595881 304039260 202923286 978997230 197778175 924142252 225930647 348394056 370701425 908551293 770560179 775763141 573049177 756387505 660423715 891140584 370333469 169285054 217810121 998812272 654802154 291120122 547729903 588247189 981739771 819800784 564134029 326664010 300046801 79381514 430553218 972443003 594796410 231301383 93400535 234080590 472852684 305686019 271442433 676912483 419128488 820810579 832038686 730178070 549429049 632870056 27988788 69251769 515898164 81467977 729360758 945267932 717921560 415860315 849499520 987728775 190576237 485731866 389195928 785841276 974565126 135869214 76398317 552866167 969423936 137203353 173213913 419049327 725531203 194304662 149384737 717142484 427809597 356405561 422717745 772886481 634487468 615202306 590088802 603957129 387368082 270343435 949583157 193570138 917813952 872490055 1673110 3001119 680419854 576935107 732097820 78986600 222732190 480935911 405179461 678109889 938823198 80877235 859363260 418262770 416485636 151065348 778045845 747993659 141585362 745199310 38646925 57287317 847910737 81576289 362076492 650496245 790932183 643903141 728862116 477694090 427545475 694918239 255016912 882576380 711148925 931530092 195667384 256267437 310212408 15850755 372221993 9891833 799866546 583627253 620720159 777835127 138200240 192625646 916328445 828970295 253596164 361300147 824597201 199835395 116285641 859478371 159323026 476906912 943166370 919181239 666693731 997318924 180925696 208163139 872042447 93107391 330018907 877957813 601227789 341555436 704873846 403885331 786326075 611310014 975258013 254938879 567558563 131591325 74663655 782145012 161455355 41832296 204679542 14238599 375831454 558699963 689227955 757766824 22430934 472529448 928268436 428856032 532882707 744740223 680126168 806494611 368703795 125614599 786840136 904076093 7246266 179282628 31875573 513623734 203895320 835968689 947968638 304351856 443209192 39071749 971638600 291610037 925311020 673987440 70610374 299986411 609507988 490924892 929149104 54656465 864835766 928164142 938996557 440069825 212739924 789195907 815558315 971287534 93581723 613592694 583869155 348439461 681011296 633847510 948644952 96092813 544391523 194852722 964312310 870928616 237623949 891529550 132128628 643618770 623999795 267546605 475910292 927464575 187197778 304420487 272950368 145580414 829549266 18282321 746640748 958085114 239545030 593167546 430425112 68678901 61088936 720820393 387597261 906914956 883252127 711923650 659087421 77643064 654164922 124263072 423702692 460766473 604225843 684478234 429510411 90447594 1055150 824490367 917446529 340495842 454004601 502387163 571120994 442813519 235427020 178582834 311423634 50309418 172471048 247065282 697461952 760231239 817269753 256521539 109453989 347995795 769839894 673060903 130159428 811130198 249947837 312397532 725379882 648053617 207058809 570042886 935044524 979285407 51470654 150005447 393885229 674850485 818972841 983646202 181785943 522204387 797039170 486285169 627206239 59330802 885226939 372518203 13786691 320548229 195497775 951022306 819169037 838861914 271990374 791569574 904744206 909842824 451872781 447771333 594969637 62665920 93268736 538443445 73286392 21132942 755660674 655050341 486223416 131859863 727279233 999560577 248865759 945291226 313561300 98624173 768247410 367820273 461681278 461546182 841865792 196107855 350161386 215006758 289701026 459050112 471228206 680062431 33868603 6592110 898483530 777567484 492591928 790297496 257713000 358636997 250283151 358468698 652104731 35262201 52699457 752647465 541770402 915747603 223579289 32052694 816409635 87577479 624903787 877981896 718533874 886730755 877557336 155879492 747762633 948689329 655482119 817649062 149291279 402725489 367360875 30776487 525079572 564035617 354690561 757252246 753545808 25771990 212887568 692756897 837722793 58526498 358965992 843642891 378282155 515867470 127473445 642420597 65526223 449533086 656108012 155708439 370985655 903310226 231166506 72888837 586634349 318325793 244849626 692678764 458748329 622823677 945773885 817042131 285917194 496932051 849453089 687437405 542071129 638632842 968976668 254270723 976878283 272436609 751226063 972791516 677079613 61248722 199635237 447901015 599171447 125090963 969676947 30334589 573553004 425321490 780562775 114684977 232063350 255422486 561810619 723533681 626479259 744524322 414492754 881217940 201227980 787234739 442160439 257644939 193948707 461062526 859262802 545828130 429722146 309562549 966961300 203215933 276724472 476633153 359105591 582858781 616240828 919925766 668557312 152690843 692174514 134575651 888010111 461707625 480172163 291926065 181671244 680146774 938774918 259786881 474336841 444246408 822043132 474209121 865807076 318700225 544181837 72600149 153992275 286321820 306317901 81730399 171505111 829789390 376065659 115520057 919807996 223976551 351836990 51325334 51437013 971850512 950399528 403463271 646403649 171974733 353466677 959330578 81928491 914625210 802982410 20414650 794537667 385042255 617301304 163217532 294084295 758721694 318828408 308713133 762072511 40043025 950891245 40922142 499787321 3347758 924848231 917358426 842280979 673379029 477285532 809417188 71143344 911670910 345145711 656034684 433620286 190584188 594228011 307125592 359603704 449859134 526442438 53688684 929825632 288457099 444765216 32612773 543326337 688938435 735828803 352756007 335678773 543983650 925225890 265921428 838543194 832959486 294569564 231569989 940698653 26896902 702204535 660570000 40902961 412997506 978405415 971804162 159441430 637337495 698608134 219876772 39916372 939065474 141846107 464957240 211633599 168627930 646107733 721976699 230497714 513112272 314531663 470040162 40319574 271702895 847312395 929375838 489248474 729413086 489905145 28901274 506324921 177424026 510090863 695679289 259738617 627904191 91934191 759052955 814698600 872660798 590576998 427765910 582936287 925914149 715168617 919958718 136187265 338645980 487016311 284853919 296399866 206679140 411064636 153952511 561600705 229373592 748725193 547809567 287405144 977118573 263589087 699153400 437779592 860175155 968811555 298582400 731599784 531873491 95638120 836415460 217066453 97451280 323460330 27574477 43643960 190103496 817379983 599311517 775667269 483032370 721023270 896435121 354004728 477235488 559115945 398059422 148483607 762715708 815428732 851905653 716145013 483827532 974193837 638465 780206634 35296367 711516468 455212293 75115485 206398046 575969074 213815936 832514044 841934254 231668787 855907562 929969408 91772427 865450349 207573878 229497260 975062908 3316993 95165776 634597452 295650211 888633655 280843486 943569400 973789435 864085443 252472065 333353424 443598874 402210564 686391890 665194047 348393198 794511169 202293351 38821945 114527746 680217580 398292749 94530174 589543351 128846561 115551629 612697815 97631117 266021797 663578601 68577622 501587801 68540584 646264861 521184152 652577934 880505477 792410976 522968067 923751287 357427007 133660002 909306634 23321208 911147908 23914381 886026342 950387025 331301867 822083142 237138524 980870237 626037815 102699564 187230971 359101389 136080531 643324245 46501724 942558447 847477973 235202197 495439074 63614826 760830909 632017079 242529914 37670529 71873588 187459011 577969113 799048782 889667216 757548089 589640386 681070342 877580748 876705874 668346431 583308856 556630738 119550788 984596453 102469135 727575474 280596092 206490386 673308813 353311978 590591715 185938992 928482000 561851037 420045850 96180209 9621071 782036958 291257792 824983698 33476635 789040100 751044777 986166554 877888032 690952533 669513254 767459994 526852195 752146813 107336001 729968492 868899907 954872213 793155071 544241781 511788473 258638846 117180062 193646180 91283610 333899653 386427606 748594419 990392273 686008991 152440090 100723235 855580839 31722155 631883221 262038913 632173565 351652149 184624303 116135781 979412366 546874158 677309896 984413231 607001392 743959607 678492921 504467851 502039057 859843029 821915927 32593323 882730491 958868155 970854193 944490641 791018130 840317445 727340495 936522052 86286994 658175609 625446963 352211223 266376979 971610566 119018905 637675751 321558727 558021574 603591288 240907355 884604216 152489405 119434176 451413796 264238092 788281241 357113371 914378300 23903811 319043377 613460782 731243305 515324276 882663816 259537111 549378360 598529813 937204746 924204654 765287620 91667890 876516811 660344325 601088622 75212851 662404300 565241770 442719332 633551128 443160375 187471010 85710748 422779837 392258208 262620333 856390423 660614552 893858628 846243654 918301984 949940600 651357515 850802402 796950156 116034245 908301318 951561773 859868154 838992068 400196403 259943762 408417042 773327314 717103158 105826098 570081735 657833638 491666784 167875753 436286359 311456145 219287850 35180493 714711239 285301182 867841399 223337264 856457641 470129780 9741015 983521051 485750231 445183057 242825152 904540371 920106871 331780238 131672021 803373014 172481654 97210943 483193633 779598620 163754959 178196370 232394074 957641303 322774211 791584013 499515168 305890101 486620704 267712209 78988093 636926619 743936381 721520091 407547364 248613353 651635833 561896255 9932275 380942906 94612480 708845933 299207219 871491490 231958408 38907246 298643604 863162480 980588622 728666662 56260467 517916779 598529179 27808145 294022358 793125399 549059842 330689031 957580717 523035119 170644385 206477177 431504656 371301289 588437341 996584627 837197189 152972663 503315240 696587418 269073976 848339266 228215101 137216366 163975234 792779247 63172191 151770630 229613028 285764252 707053343 540976408 201377227 977063392 843748117 543504496 760909899 454480656 701948452 978766389 461425318 257023862 740502456 801094185 893984836 892893594 298221576 772901095 75673082 408913531 201229654 427064101 357335365 508664532 16441131 172473073 557696909 723276377 54958494 648438006 972029797 443479801 826335372 405038006 261532102 510046235 551931614 226930894 650604889 383205347 79115720 545690167 252125100 894903404 798362117 444512640 669165689 835547404 438211358 564107543 870452452 41291669 276341922 337240959 16437947 724859280 565790572 5871257 828308918 204058497 704700130 166333661 942718134 658947112 916137010 381889183 234831111 590004668 809995669 331597132 188466591 340964655 39476110 878197932 28849758 528529774 970935849 545685023 991939918 175939744 581827646 406298082 431190499 110608740 114171565 280676937 896654906 477037589 977493920 630464772 244662362 100830215 249822158 565087324 592827255 985667272 146706868 321867892 460905772 14451554 780241628 135464074 277802686 42819989 682131735 991045173 161306206 852731679 767982532 967765158 819264612 544028405 17171721 499330025 723489430 813557897 443132694 201024547 202537313 730226436 413417319 630836435 51930396 676037258 560289280 252132370 814308682 123688315 610952368 471513045 905129942 182913965 646312528 337256231 573087830 12712885 628846083 637187953 837135177 278950429 960289910 23445428 49476443 207377068 110380830 895303627 507341470 453885347 584734078 277296556 76267473 193065724 790656096 674438309 552212890 53445547 583857433 693654176 591995853 874352350 940824775 391725921 844341412 703776063 741755284 968624068 306006534 19569710 596112370 278717185 365419202 138094856 639819230 327053290 446229458 357569125 229269534 173828137 867186587 348070739 948009349 164991876 126713641 594483358 643536940 600122139 836424053 659581449 829191864 430090918 127984800 112398740 465914264 271276985 765027127 799001269 497550406 462417665 592700782 312038817 948117123 798432645 844037735 190003842 894228380 286499304 790093674 266050239 99220905 550290851 817628460 414676025 8783562 874947661 641265930 540237962 692502122 638546132 397525068 367050310 282122366 339630275 526785380 861457979 340755653 23263100 934632750 576157874 704534022 307472253 878300208 113274029 809102166 582929821 643730393 746534185 752604498 14052429 312660419 544248923 263974751 357011160 1378034 867085044 459495150 101010597 49433876 904005983 543632059 865648754 739849152 759940351 614196235 506912664 554758585 968242036 14893035 360066379 854351403 789046740 852231286 652656601 890523626 241703411 520744973 767689192 318518967 564795293 324212382 323936697 996310652 351319513 756888287 525490793 445398668 479332389 153131409 623366444 458202342 53252542 747361983 678172818 385144177 874540247 696332542 702481349 591682367 480469982 767305389 13261254 752925643 359572156 636604724 297228980 350623804 894687763 689063494 145498886 284635810 402076799 453092640 964367054 28722486 841596376 297569225 667979510 54946715 351078508 251477074 645935236 920763937 702418502 111972885 384011735 438900990 307535468 575605496 243268073 399912853 693533210 794958505 450408332 377266097 647030793 709639136 512345263 777931976 828411820 826870689 21880728 932589370 43830383 156982393 759684138 840743824 747071224 890147774 123366686 306518975 301273192 737210066 632427851 452669541 651971481 161896542 969002207 600228872 660185182 803824536 196590756 42878556 331296455 534289791 533579582 259002747 361905244 923822107 412927594 729798956 619324767 669353408 573428286 7426590 482356749 654388297 163650669 888938795 353843675 703921246 783629698 93279896 530903226 757015216 531588641 700149073 761896020 786776890 992714827 475325999 216938318 327772287 184219800 851366195 197693575 548116688 919410556 628553417 159560277 700216197 95914116 992171272 923798476 271714368 616687512 279786735 581350392 920178735 556534328 985482151 267413279 381863753 330071745 220884421 328878593 196877709 86515111 567970950 261164314 55680584 27207866 158527762 1319388 199297357 940021859 407472059 754857463 587485244 96878821 696671037 25040019 995227581 817262494 433500669 392700306 722079940 67350085 353618764 195907792 583934925 118292523 79132323 735997796 58277406 630189948 719389926 472884446 793427209 778557053 354247587 93701257 83618089 924539597 115309650 386827944 648367010 78695078 42143635 976359354 913565027 115395098 673133173 953309623 983294564 357450328 839414699 957344594 558143210 785888486 663014614 877675319 581879488 711757030 263865280 827464012 145837182 117563987 596455836 802913777 528676035 129790786 969802825 221762881 888616828 120774948 557173134 374803025 997062941 105587712 290134621 558135918 807153636 112414138 416245265 770411105 598460698 116452177 836602289 443893163 119647315 355750426 207691053 689413067 528490667 254689032 641874078 905334645 446565896 305395685 306463111 510719961 240233564 197002903 633472024 397096932 826402530 734239838 694863975 844898168 872653150 855134994 31641015 560294068 935693663 575041127 601959346 56771888 305868158 966812970 394926512 168516927 92997278 158504066 504700912 636949804 208210731 110871858 226828508 37488767 944084061 960235219 353284679 638101303 46856564 949412636 475241647 106156304 190095611 368398108 925171325 444654780 686601222 559356539 469474113 985994027 580680566 642651326 943796984 702833349 416080177 301243522 777603400 99621547 272235372 980515006 195946176 17262075 697214947 366582787 734639130 261487371 766415133 26272189 82924923 567997099 374821290 338966384 756026799 70326117 826200934 741361661 868945775 262913214 964309685 787422940 22357660 772381300 745043399 825943394 437216131 325823423 966467539 213732858 316507672 626785938 280576605 381485421 127857981 529168600 33415793 220999708 875007994 533567417 624589287 568179522 192966340 353514196 409767071 529890356 61431480 26398084 730605508 192226722 968649950 741160478 470483211 897925333 411993960 441705262 13349874 278746865 699837170 564376767 359051011 58064434 688131009 497996690 763223824 125094704 451001606 193954403 226966646 972910620 942808602 868258088 912321116 696090627 650918337 115699283 764903410 44233224 488454505 426181645 979050421 424996011 412851817 850330491 396593319 705249030 46193476 577564667 192702360 356855307 247509221 120573029 454828642 735808969 703883747 733124683 890690342 898925222 27795388 104887611 919654801 354700965 831924763 493537273 459229723 850792095 377440787 689307079 911079237 586558347 639865699 296745376 405155032 852435383 935418801 969080182 387026730 797230094 122443217 871095672 208274009 849096529 745731326 954454864 174027663 712287584 329563677 698031966 99440190 656298097 761625854 511210496 285512035 631215700 164664732 406605516 792996038 1893815 101495130 736216530 986381365 994621277 394754117 283883228 331504845 877896039 63531094 475860142 148598835 907247757 883954863 358669384 416165845 646058851 696470235 299772961 890604075 224797591 810475023 410858347 474020345 865195310 505696365 130410324 164358028 397971916 539629118 258108992 769133050 940486123 698959669 832076561 792104549 162657824 319061936 318243937 128744758 841976411 689625080 951598020 533121379 217638181 608821117 930045705 852588971 251132641 896631324 36799863 736841174 270022925 404147547 407706386 442578935 37429120 605083049 175791061 129409451 611551147 954518944 298463990 730915674 900999130 394648389 106459175 506766707 179395186 640035652 396901585 362824625 745221938 279556662 62903640 286935130 506795635 627515868 724165724 165208955 562761322 99955298 508690931 312331311 562414691 935169951 79740146 939278295 341001221 184836689 481410595 333320545 898732690 196282211 491590030 312927876 273649189 864637737 411531698 5598975 15051507 381307552 527196873 253990367 248946829 390384816 235756041 880619703 483398426 288016747 71404768 389064935 965693599 433379661 969546293 358036695 188290616 725033595 800765867 462497082 934407005 868075014 136089311 188388430 650083616 750741799 752368807 442897688 87166315 407473282 444510802 700270250 511177285 204993381 551170284 453814111 809572619 646765319 420664952 605393947 345148856 439790027 689980726 381303181 888243231 831684732 728810717 429940077 613856557 912936849 323009503 464494016 349484586 291335272 121527465 217798673 251584502 198700172 183827169 914362040 328430670 266215664 968235176 470086164 66081541 460228403 415182808 466594770 735869261 573216475 36404037 925043749 720189166 925650076 2941437 773132557 34932619 256730513 579820682 709978003 11267042 769400959 668408876 147714312 458516234 773025558 37378080 87217227 131591092 843470641 817985246 400485121 781105515 814643218 727457108 445294301 43090390 895036841 415025710 461719255 98302451 961063372 990289679 764174966 325943643 840753021 927453143 666453768 88290691 378182185 546875356 805400806 599204598 488078053 762939186 217137331 659952797 564622257 223924710 8380059 624504057 296575158 315005244 69585814 872010597 993709961 968215286 428115620 920198486 676315240 53902477 373802511 133142428 257566585 689630839 234875566 821729696 919835151 486069089 204302110 154437286 922087910 236276084 915611401 18581258 468554852 98395027 130398305 494128516 368692184 820465304 222859938 332212838 314450621 970454171 455305237 517219546 694119669 877716525 750544649 752487462 201804047 683361174 760170778 795905769 636325763 381008925 590151276 662465117 198054386 327343934 7840495 638657941 60469864 840774130 542720410 239018686 431680668 467571180 389542321 147986527 65612588 716472536 784909312 846374042 603865827 302300061 524309023 260455018 848928757 634964377 749540782 744713445 439072063 260421097 560912280 102266490 182505353 161041568 236450129 611189809 325993157 519917068 944814106 512692463 662059343 233233398 328086585 379946161 466082604 495063264 997308483 302563277 129231693 951573318 652417108 285891638 578860747 137941728 739060563 876119223 911703594 269058012 290011185 150084148 784869528 927566885 275361576 378312942 904559404 761058976 967822589 850149821 259052585 98048108 806463551 248988501 922695226 790522911 793684104 865419652 587517877 70016781 331354041 915425903 308466650 732919426 897206591 509027802 236892691 121437956 834388818 393277023 661620531 137141652 609464370 784167603 684083897 845123307 398630250 581809894 738902028 86864063 891900687 498524065 262492093 416194813 162524928 5963623 379770570 248631566 569193509 406946262 493367255 83090196 52713393 57545445 689318004 601137963 962990689 167829029 304066652 477017258 360303036 269106178 966866610 885065057 38117715 185564929 775708483 548517595 721541120 203328257 481865160 463115163 432288552 243466876 376585507 221285472 161592827 930214852 599050398 442274658 37785776 153098312 464336177 482210196 612819403 897377742 873078459 994773986 344414041 410069432 708680517 711172210 475815984 160775745 60743236 592775141 605003057 840056767 220663766 164426388 581197448 179015136 788276737 158090196 631535336 515485935 466029560 538552628 435761360 386149645 22119767 283458492 799501770 145600890 424526692 386528558 257545641 997577163 389733966 871428422 293551560 460413747 393897583 563502843 615208527 873905084 925813644 180372925 148624751 900398476 604699153 82520247 17266338 352218147 983115350 509138444 336340462 911062937 207317983 159075867 222247712 404992994 375489685 960793276 815906579 933171211 839305744 320473218 887873768 544269692 964977358 803456504 204669261 654918453 439905146 675739366 485755833 396337939 688937512 787534220 122449323 607591178 308323733 705125859 78967279 592417897 950195305 110367969 52870618 682513691 196828790 403052978 672140427 636706530 81686519 684028673 54024234 591247516 7146708 32051759 94747947 357151104 406872538 812046488 250746761 633903711 345331205 748747987 237381133 695284965 769129912 296238064 655922566 198010582 254759937 179908793 198815247 980027731 852756951 160076019 874588238 388629 326489437 76086940 593522865 426520750 998656286 599010604 749922992 781224909 168179024 439399638 459247632 179698296 371738387 482432965 748723228 375768400 567820209 857907553 102216939 471260626 61914589 860616586 402821791 29024659 718492406 908728281 609502369 59186049 279528515 990785251 829660392 340971302 648797237 415271799 122905393 468941285 585527722 816572893 954807365 877817917 179801894 294135574 463992120 450719491 72517145 396261920 6701221 568157865 794838558 640927537 484491765 728728188 975030327 99385081 967216279 328027615 51447316 846220770 266838343 249806738 300133707 217290065 224944968 514649839 518455454 869443300 971738027 889486121 912950074 153717171 868579464 93753485 820099060 626780048 946001986 395181506 667664523 625169993 409221317 410009354 466994923 24863459 87664329 394536320 321649766 871018206 845143309 40479834 693184762 152305525 394600862 249428519 955761807 318593244 996345104 183643663 580843576 242389378 419103169 190713623 2633071 227961678 53373210 665812316 208335194 5250276 215153359 843141461 581227018 478519007 954502684 90353426 130872249 177646358 542344455 42140033 696175113 162861016 303496611 921290662 632922953 897888050 92993864 120858079 410158513 291600933 164947934 493046056 382397602 128492530 410058513 913283154 928749032 803451728 65028507 35941195 997105402 771856817 362501247 33958491 741302838 923986563 154643529 190017890 283608615 289258090 713982545 822259997 672148161 45488265 159222775 973479008 294908577 52182968 308559333 396106587 492196431 29156300 126440786 948975319 736074109 552551123 431658299 244153208 801567302 451209303 380009898 269063930 484993650 158147736 836180721 288427893 207069870 444306388 283099373 424584346 376602070 918330241 993713733 688233205 886911533 4952462 274437545 651708715 579011233 233539495 821888789 936782139 230638089 51242096 969490189 670364095 67575400 728941767 665456096 635532585 187857449 635607300 362451176 366681352 47270242 691163193 617376710 311863106 927205139 335296371 686522279 386181465 304185958 90061049 385575043 862447016 846708718 810597770 827714138 106084005 549722346 119700385 476418167 120052766 581780608 634675378 202404015 990285950 911041796 260563051 284202656 830608390 227011376 452126710 795251444 786909718 897163627 11738931 260450461 305735267 987659525 925282816 826076696 588873280 500657526 893412722 137438892 786237399 811961252 254427931 759558570 4172143 982398235 784729156 291714476 790103205 32688468 794908465 680959959 956702644 298139376 928810082 335674651 516456111 951344380 221738958 254239599 169719491 314914349 351624231 830361367 976473976 334746147 899421722 910539232 364028399 480853671 194503054 216521312 985911330 248722670 899989218 980500280 515915816 380297941 364386353 136294995 4592496 437978148 326918799 374917670 219034115 49849294 241645386 123658480 924572100 723477805 20241195 543687161 399526833 762692935 670786484 335603412 887914273 650440205 458184802 851069086 102832901 2636696 892207083 266094910 538084648 595024749 474870654 552412325 574408049 927946168 405040135 585796621 6512926 89535633 299436905 707486012 32294921 947342651 347023300 330326976 291177956 829833058 333576878 877867057 729886589 451483738 100570236 591132019 257156605 689435749 23193464 45624307 297569826 958856683 247776553 904960743 226838922 6612672 293807504 570822545 66967018 246275427 380872807 827564666 863013968 331322427 149996130 226251960 734284902 647529178 312286831 840360234 804620720 826949948 934038775 43373496 292367562 975208198 288051484 580571285 367952044 144721609 728262651 763312511 794743272 797214013 537770473 851159803 586257384 711652488 150051768 582522267 212448306 612403575 385140208 278014777 348456357 325908161 523768856 155588667 302069691 956293705 564328940 302827727 154482119 338883674 479170213 575475757 547024950 632282346 139369015 336396250 459886031 413465305 610548364 556332257 588772085 447552817 601887435 54446361 360766689 374953573 589418645 652951652 933009130 999132052 952069443 986092011 547904958 688791492 639549739 854643556 864502440 240655657 89222362 656509006 804758218 459942493 41100378 695446834 433110626 469119399 623785067 743904993 898696710 450605622 520008650 530799034 283535849 926797669 208393326 291003106 792999190 777083382 395424456 6540171 278802097 422692185 747432192 231117872 215705403 756062436 721472060 843009493 373116364 23266073 219248603 524777289 657380697 239861989 761864883 519988836 615642605 201345757 529887320 18799947 41424881 7999616 762725974 598332329 983911269 722321786 315338099 347814902 585264422 854182620 477301488 307032753 669511208 923564647 559700423 807318439 315779259 185651648 47595 826873131 113073096 80084922 801715596 998296925 529299475 836697489 434641490 394384230 371960184 917967403 851232415 148476087 695607343 553472343 50971344 367628367 481865737 664670479 220783226 326249460 185838002 869171895 528912814 642438518 748760047 346065501 86202935 256728049 143912159 674908153 716562136 889425161 237182780 665415852 16798864 977119277 968692633 659649538 987553239 434479062 837607330 372048177 917282272 753374407 110136161 873400922 449845719 703885132 154086005 81419205 589989410 976860284 365288794 909147942 747509154 905459065 235097254 6942940 420891888 546527405 263118407 968968494 825315234 985752845 321974471 948919694 171624837 969263447 325816458 18567128 828615650 243606356 661118221 702131601 5545147 268633880 195904038 927813417 330289676 223046207 907264328 254626619 341488908 674928432 91129021 371072458 576929643 544408155 692118764 140146052 723827860 508109692 406209938 339786496 780556010 143861463 639820554 352801793 386511628 392209020 284725127 320933042 542480658 626086786 863869014 284301033 506336719 659534669 739395359 235513190 985426447 587070665 668607267 50215186 413264856 961427886 989729404 183715907 309687210 12109756 784313697 312563700 706000833 859026942 147005793 920281871 691785039 693152265 20585637 984992676 370909636 365384507 624157488 697333297 722956808 549478398 989214752 664282841 374700989 30470916 411897068 73786031 907091583 8788106 182952101 807263978 117567781 26475415 660474679 287388208 760193279 328730939 50132134 946300877 626854167 712032210 78353491 894494970 558346098 247984192 700814903 275135512 371537998 262258485 639363620 791322612 915079523 115454056 90309897 136313603 330502436 885206493 761111084 675437732 380401661 273975585 121762927 968962659 195969940 885352586 288107917 926611761 125726217 266524793 573988699 795355823 425459511 91377305 678203657 3252834 584948211 331221279 541288545 169218813 30351689 406491657 296554756 167434140 499531716 776281185 617349554 660247301 224554661 117360505 864459648 618847462 669219624 40050223 524341536 894396700 330017220 925153320 923814431 160664296 995226473 462747925 108457504 717741625 772200641 406523891 553088547 81191654 537447793 648928836 105720258 915993074 902210391 319336793 551615088 957394121 283327435 292962697 328635578 513411199 647338719 405276024 397452167 535172885 515140257 391661395 555436890 801724085 245924438 616580624 739401100 839510259 679009214 103273648 334636948 656305676 558113364 10550655 210872896 812268071 455699597 710975312 128156923 996076184 628215061 322467010 289351431 692439834 161500695 335488895 577406146 390527762 466649204 888023418 58233571 550303953 298921736 465162798 539336123 113475792 703009258 375076323 875653237 173022450 760112553 194976490 983658584 694454215 620789905 16213213 277939201 19195845 581883878 309631458 313965228 936922767 749030182 949361639 466168682 458195504 919223625 601198564 836870249 259473502 396462594 89265438 298121265 970293689 692159740 816871008 440649443 900862218 539708703 220717377 463372154 459327623 59066826 942394722 568055563 886542603 559498264 682833839 597718022 369316192 602353693 147636635 633454452 445832566 941418024 819821158 89169464 156704682 557924864 515133016 914801745 729874946 977720361 769296901 394766868 597602670 518546718 764553608 942770035 20651782 596555926 281180617 196279610 641291599 515541184 935828921 271501902 540850552 432533896 553621907 827126510 444315287 496195026 608819739 485546996 758435054 91197116 833140192 438596627 770311978 594018526 139975290 972172055 939679647 572392842 645006798 52464938 210367375 160219662 487900999 93398027 293062754 385202926 100252444 509262934 381732589 827333420 888428943 501885121 354663597 852176258 935887402 593777498 932914442 568652196 993355521 999618763 650507414 853296513 804074484 660901272 60941389 853766784 230050283 135826270 3519189 98936005 28977178 928376851 863648701 790741099 276690749 948901194 649253055 687877320 58767066 466648942 49486591 540438446 752056963 805079299 659657803 819047078 530453267 120970729 222805595 566102580 70172654 73594523 757906448 375587096 883264579 704569706 283893430 8297353 872589899 391406532 695377219 813414521 352320649 814422385 526661015 427800790 634204937 246132177 178983868 135340740 20946082 678553377 81370406 295228133 936675382 831915957 919665137 315937171 677839855 561825597 794984999 83329058 274619521 845046273 386743033 943221793 703370348 208844839 121152515 309787287 133241145 153165546 641835146 119453511 528326842 339539937 859543231 59316206 123680844 870752832 486531322 424832897 37567509 964163599 744008961 196491122 390878792 144323446 993313601 740316906 235263069 306643443 323596817 716972557 130644059 928672672 265153780 442830651 703911441 781901935 97271253 477867082 730402902 510536047 584950858 956551631 340686926 600121350 980816082 88944212 339240613 852571446 861799961 869477280 716852947 368943322 556736561 938422260 259899992 672130279 898207192 605043530 451097086 719641262 124426679 529223830 269410588 572915222 188736415 296623367 195375311 485596899 600595403 201775428 702508353 163640820 421928482 611606192 128400612 768948350 345008499 672862888 956244917 920412500 807751864 674904001 136058491 568279072 685468246 657716492 121977350 340908712 321151833 469741908 211334770 834605068 46323386 492410461 388007524 919212035 149315226 367461924 119044169 678655523 302980998 87701539 231418779 442611480 987202482 433005707 362087453 869278186 312102976 516669833 249294620 857878329 450068088 846820483 40844462 303102082 173748495 347567450 80460020 566368600 373983586 686633896 76530009 502375085 867792057 104005121 540369874 961489417 587566470 99125555 383408669 952090319 707756197 153475463 490261252 608041853 518056092 788065279 592295833 504970473 646795994 413807512 784419449 103340934 680805625 922821767 799728907 959571103 367434749 435308925 798531776 434545048 628272020 581764325 391385682 231037234 394578261 885372450 807111942 502983878 303570947 132508372 846726636 22164870 452766921 82861073 380277019 58393536 847456894 539458477 918933751 753503772 402425568 566938996 802332525 943224027 94795738 162191981 419889459 906851608 278233791 688505366 850952458 609203208 524280718 105247148 493213437 394346555 608675374 561790818 74022817 825971418 351274417 732499878 928889173 275260137 654435730 60335713 193585025 606415492 817774840 717409333 473093080 458856483 453303283 200868287 190590359 428736471 309337276 474839252 223904966 935407244 337177334 70305221 171792755 372894023 349251313 810847901 442268412 868015720 310721251 319019615 741749059 735134950 208676399 87440970 744408569 364298135 702899360 144314134 675809750 873883239 442805676 306087478 327357916 80154525 380215218 458720534 637337241 215508251 321271614 197198941 155319651 894951325 629436482 962273065 414527387 141549046 728390492 2840663 496623597 529272920 466130197 841042361 623221132 346224522 705362205 939907424 821918071 199892017 703910290 146297041 632425401 200815626 942235703 719562833 539010722 501498155 445891007 753853980 56393232 248554311 998193409 471971239 352269995 943145192 711882306 52814563 299667746 327240373 723457137 329558907 887626608 302529707 198876260 510214674 523107867 127851366 101627421 786063751 443322225 13254487 450010632 809983026 672382666 718953484 808081980 205800742 411727307 637542765 592657336 991819631 458901919 301738234 190199205 748571987 908236349 815593744 53928599 407319955 740826023 454693411 797899725 58221224 78820646 491940355 380692079 110190088 558178961 811338521 429908173 201002336 836559748 703253416 115291556 165939672 103327915 415924494 517896537 167668564 977401078 795669762 568336189 68183472 404711652 877936341 793777353 490909185 603764666 267149491 148620513 272303064 294709450 659103457 232185107 839999615 326201007 634329854 621019350 35791931 767571597 254219075 21561549 654325130 345495891 131089861 711127556 333721700 201966842 56033199 809628463 664773500 973481924 417686666 803595247 265150334 965087616 564799351 332300814 677147728 253319874 615101041 918146239 206483026 655140397 73581966 679556577 804289952 431487402 879268924 883388219 437704012 628018096 754059909 98894271 318536870 381877884 355201101 832836296 461271670 495315287 420462224 568605021 346178110 805595093 10911399 395567470 190263674 343351058 521905537 481882899 15394017 81102069 66065132 374122962 86566819 546187630 791198411 585195480 471949994 254998969 130877022 768761660 575993307 87048602 601996671 224435520 427179860 87319200 773250017 939376529 788046509 797033828 468869713 373327236 75687993 283319497 517397495 336588121 973645379 401232699 404682643 482612090 838395987 857218546 889712834 439266234 917070441 745182765 435241272 355947671 5405246 813534841 355661828 80014457 81472135 952509418 921034961 774034675 823590963 675805534 797905697 987855359 412900778 367488191 334264210 284608324 556729357 358568511 831120154 785317201 256336506 462326682 930440781 488371424 774549319 670828889 292733587 80939030 567427396 366402060 827865972 250488767 726817531 563739020 976426958 452145300 485257201 16830017 974258970 823380086 567375332 981267031 536866988 818600370 185695756 834299656 582444786 454566972 799675996 722236375 756449970 860489974 73054911 736082385 66449485 211215080 703535709 231056075 911562496 986910854 227029 762892456 755221024 667981551 260557187 729491090 86787675 858076971 165649593 511998526 520078587 329075050 260431623 57461035 815510819 861902409 605276788 207867360 701227281 9089549 854360516 547783986 966216541 445554663 887917490 424577405 548589110 441333040 583030324 549067240 208562345 105139372 327324092 65270692 95049179 801952713 755718259 233884459 779621451 742257630 360747902 576177538 608011027 12211054 972426811 201066873 173657382 397378404 373252482 883945191 830888081 118789206 416533221 750808560 337175995 886839749 367304690 856747073 264293030 763663192 250898285 136757328 297308718 265369638 541466265 418366622 420087110 573044714 783264366 94333686 579043392 142688846 279314145 977353645 439576579 729036835 570654241 310761186 488764244 822096037 438769621 197198268 116517904 299885241 819256417 950089137 392634989 944989231 159093279 783244219 447679038 97370882 861351592 344087458 271055406 156161684 391848459 133990711 303962369 203125493 73230354 985090452 81079512 791455259 136048513 315798110 925532267 659975977 934383448 768921349 819115598 558549929 689164814 853360129 831141422 69004499 853057237 43897876 443806227 615692486 205680347 235350412 922472350 91200460 359106692 521684351 861021001 624341912 821459122 783926542 167659947 932840072 166541823 262135460 101286067 126859492 989262335 366203702 105890026 948970015 110941313 241578371 205312179 23986195 357423308 81075539 713075084 770797639 818260196 326880953 102408524 755340074 210993348 25998163 118841189 578668886 512940450 664510342 496180257 803347152 21817648 224729540 607193573 131494980 123664087 230041031 367323250 918429258 265232123 431461845 302289953 289824934 438997564 761763836 983092005 129886593 384791729 592166740 496166602 157492403 825181484 493690690 40509625 870941434 452384378 29224625 575956019 638600001 937672866 669158744 601126227 879160796 990623779 53403385 98680911 38643656 776080184 607740573 957708981 506302957 288921877 139986906 170815664 548164701 915327272 531036175 465889345 869780372 29880410 313686948 955131016 441501111 108357198 708484941 23084794 161051095 599026846 258391877 959511210 654495533 45696547 506520213 200674178 715267677 138839083 748870220 234950536 409745589 91084738 729934021 864298524 297514860 392179436 993605350 546663734 588585189 994576358 300740445 553308842 584699371 331378282 303064547 82144101 76617461 90449129 549880442 178027182 892675425 469649872 54576305 74451816 10126010 366872262 35941084 265105228 423725043 764050410 566265182 281560113 429269162 408266006 401148384 321898310 140881000 132236064 569740441 666217044 135155678 685090582 255561094 443124478 748114471 3770751 437159856 99106817 143181834 718247326 832866411 230349942 758940471 753092272 778757266 870511885 592926087 670203690 773029326 518673234 327947325 160940541 352627150 412717290 913213769 74345940 572665742 28396756 879703681 753548882 653143698 978642601 947699943 324647255 310495785 949991389 359359464 864723513 626209452 844920062 423559321 979638029 68444349 681132274 31007482 278463965 824170123 160660027 56858420 459769328 46161674 884950579 606012636 22416135 239549757 950556242 119097903 923482267 274091374 505190245 174313302 156455202 1720945 958585558 482913697 322638154 968114919 444695528 487760077 155995962 8531574 401717498 748827200 533000149 542918419 135045313 882669129 808688631 74465850 904349583 661379426 661410744 742515249 607557776 190249840 299479974 934394699 573878025 275013887 459180557 357998369 166884762 51827336 756343856 949267416 43476347 87901100 814610830 517692767 584504255 289064055 82090272 43280047 720688277 82604704 6713495 218412811 713327236 275850437 235416992 857385279 676118956 401949617 288809761 80802531 821218569 372954520 599413371 485931415 686149041 383657815 183279815 101197382 417566738 642146742 506469403 345070693 784054583 492034215 675385028 79800626 967172610 219271814 213191307 107750647 39887984 518613336 606780914 317810758 700310234 519234062 728474998 728698172 753976624 842907073 928533196 121014464 961364541 544868597 219425317 790750658 254025960 220128472 920143211 392518270 67372399 343942785 106250628 457705400 528818347 215689779 52403596 357782016 123189584 960002201 175132188 634503917 250425131 937051657 979090567 482648675 169336420 424694723 729886745 683254223 80093372 809359665 369891672 918668135 772436173 819039014 45964613 894678892 100106062 619011361 35750553 572627817 591372366 647198857 267151626 344216435 578380918 837870575 343517829 558895976 631750218 292233809 502249587 790698034 9580902 540189779 544732406 536350979 34145218 859832197 165767210 2119832 967674607 396094882 252598118 8256632 907080537 800109516 495045242 373482548 575206789 281831379 700950769 473641638 798111570 67427693 228684110 994721076 322848057 620142460 655090256 400156427 503552399 663505741 526733359 814595686 176971712 309360085 252367326 553319366 272188307 695983860 771396681 471093560 37618794 305825971 32197014 818505109 366292096 831185543 977459302 158759867 112124459 970813069 480769810 669693398 619749657 230108878 573619952 204981403 728732564 952551546 684196749 100204681 357707200 963816238 166024689 940223272 511511257 184646192 522993120 483035723 493716088 788212655 569528086 124109135 834325452 92130821 808278151 274751579 390632163 195853047 429723046 726039456 329887712 845329649 616424861 895799961 867146308 690494027 90861199 334974793 459076135 536683657 555982555 973510017 149143933 195185044 195937881 495329816 954884435 983839491 296594844 67834931 230549776 341602647 90087216 888318589 231097783 966442296 122907354 597975149 820602657 344641211 119379165 937927556 932124485 9309340 752391985 389494926 942494066 371690373 197842636 302656734 138385297 915867463 206994139 851956628 291360613 884868126 82427398 882465496 810810316 968159728 108511153 984706845 303524348 998127499 333793591 372617313 455329993 579021291 128929583 83213161 892282331 501901683 601138345 650623751 6180602 438305073 979872367 223148373 142228804 930031644 343695430 659272953 353822322 626534487 435476012 567644769 295024153 963341933 624925081 88579334 227900132 269119636 559773888 453105834 868193756 22390764 117569997 380373659 93568418 580620735 170186789 570550512 953606065 692887232 255766955 297432008 23848350 521695822 779060215 176856208 900031065 211923376 633293214 796063035 907404652 469673303 753446767 886904713 279011896 683166753 870133682 111494211 755914044 768727698 400938856 264600186 576111440 670591002 626524559 452627661 224332515 646525524 278613085 118162593 611387714 962339906 319217282 593872232 166778322 755727252 520055912 94793693 800861523 288915424 731545460 276949316 419866909 690742248 397145924 203779244 654133859 99642073 507025136 991722542 43819380 89994120 561547850 18959916 476884727 68558260 290616096 114406037 334371116 622058825 891459191 133968413 423565615 900439961 940720591 322081671 586844214 203686562 127556195 842390749 85857999 144057420 695865447 349931699 938765861 927603626 839020618 373935465 263958842 131195446 326199796 753627752 277116460 355943190 997670918 101905761 571378033 805710427 676725534 988340627 484555036 843162687 934489362 851548932 98125848 926851172 150979122 956912580 55074665 830778137 893990024 57754927 929638768 302110870 109973784 389669673 520568101 121762364 112654626 969529185 155082076 781154775 205505373 37651600 163399683 390800606 196890940 903941561 692746079 705456047 587299882 233589096 960606036 451162325 644580047 637836533 626225308 253915716 78219850 695659968 172377100 313425560 612952950 425588340 502062548 335349339 947178535 758004293 1234621 142780222 270595180 3223604 973068650 706045277 107430348 130280519 697722265 591158397 868638347 460139219 277096801 84333391 889225955 697043892 709035636 488355500 992253005 292997009 606824284 850811096 908168888 119490330 660304575 350113473 810760142 925221451 584867996 875283262 90210355 551231401 240478604 87805522 507638471 944505729 599480324 97272424 851782113 878503725 591294352 40616854 14189203 145380944 17273879 438127324 805080042 468924439 653056795 594289508 699139117 414538359 344478455 928963009 301748763 586606451 471677473 770861873 643592239 345337430 727510631 978440925 313433565 190577394 504058931 904413974 958745812 291016425 332618697 847571095 434340923 119233762 501960326 153698759 475608565 900245968 619276832 503883765 118242271 940662320 811781098 298475164 516860687 315680073 881949710 202742942 660497172 998297195 190490322 921056651 625659194 733649458 875785686 837920985 798848453 638216643 138505554 247001386 187272498 763162635 526125402 825498507 916209531 827793669 472620827 980837553 163709265 549258994 843447325 424561723 829842785 310852511 794426240 222312437 362538898 65941924 767699777 27126033 540565571 101037986 484882292 779275629 151611791 859724674 529238409 353076433 200328842 725851578 679466888 566109232 67169922 348710536 772670806 978685668 927541312 253943606 324189680 572454387 865878343 459503958 557429933 42064206 837139217 369945606 268640382 310866190 306541655 906124075 743892783 277763256 260486727 569282230 5914277 760908408 302213069 686435812 131238943 321108582 817275596 489661047 749166966 353108421 295248228 65558016 776583263 966495297 60279083 663248150 835266981 418559278 404059766 419367070 276228721 141657294 208950159 155256067 838481796 130375049 495050237 658358140 307726457 941567283 189464001 871203146 489152773 729101899 340456597 244423928 674048569 821676856 185591085 578647452 396522428 288203660 403606647 311772178 886664978 558926659 320735964 382038597 617396954 650348546 19644798 282154600 98496521 347672153 893472634 913950262 569162545 354257155 465846053 847559223 45788607 45672483 190399825 532040444 972448054 843636359 407344774 433848416 104777846 994594534 897686603 484210886 886966009 834244387 614244956 276975199 769437202 255030665 128771059 950419043 424835118 384222734 523237121 585952852 506227732 767512466 680605555 493899584 785261094 244321055 719490671 578095870 482003872 214949160 872853910 786901357 177489366 747907275 185005634 660301754 232884599 580273937 749432518 472973720 184842190 597669931 585079219 369136263 733534205 788695220 446850319 783456527 916281409 265732851 754791325 744317956 656953139 653327383 155846681 778559425 700840195 45707131 674688123 382049135 270598844 62929377 594306865 932912189 622962053 988086969 923656806 781097638 787004892 723715417 828839744 720771504 421082842 4346947 127680795 701205545 159881587 849287780 121571024 795190762 709530037 367448656 913933298 130361109 626569733 561458569 758199309 216954201 958023271 464265655 339567080 290747690 137372597 727546863 953925825 752509195 772073700 311505902 243854229 184322757 378870340 396021597 222132310 905388207 402783422 9641740 122550069 337350886 783227669 625918520 789990872 630243987 750392616 446155207 924515490 499207978 970209580 49444232 179465711 998920103 352695539 217333621 876492630 822292944 66569513 286096626 905980647 210198391 538521235 223574029 463628397 58644919 257707344 223307453 534268587 7989300 876975642 722357286 740244640 201640541 609894787 828255185 886335172 148564651 661629242 261397749 775548490 144319457 40317765 230535603 983535710 31373899 188006214 125081171 362153318 916087553 773405625 826749577 869837379 973689123 47985457 867744948 455780238 651547932 429102496 625230619 934350045 201510368 125861773 445103920 588422653 141465135 405473117 439961294 461780535 49847250 266819724 186324349 211535757 508037851 439887603 977102762 320162299 757650151 853272066 157899249 701500088 460654172 823224836 182513237 323415924 752488877 668575583 325060484 860605338 238080147 797692883 458827285 518934925 916245331 409770424 73998283 403974636 692569596 267963714 567240401 556105423 250642343 991195070 526916861 201239817 170909111 726570196 196686095 780538726 533224216 179052996 293716976 45484524 256716674 471228075 679226357 318043931 135778485 831002557 373811740 651168047 741773244 211536522 801136972 236256602 498724908 356228410 269262230 588357900 553226595 490206675 228358519 652530477 344790475 389341552 125369109 408431967 465174550 346704264 889491840 469239102 54633089 339575599 391612400 26258337 539813907 312885325 520392459 213305816 208718812 562412778 649064477 513911533 400959032 644652644 754764895 377506021 68882956 256118965 443282994 951628798 696136197 576161199 855320675 103528944 492959198 871811649 894518119 663604014 899079576 275474865 651694237 183315492 628317888 123522785 255292304 722736760 971933614 661564812 826308916 909800010 269135554 632340871 509953830 594487157 240631207 93222402 98906351 377600206 816251026 154840774 15498047 453939554 293401986 779813751 736525619 280222649 139566463 542791377 182674320 454232855 538595804 880967149 701231623 6456503 318820214 245836666 383253105 670806800 56492532 626400005 601370643 343180562 671076615 83597875 405372121 646594919 604149161 756555780 270945435 542753204 44458335 68699152 781967964 632828887 562016121 242648523 416080776 750606632 201117774 471523778 390079283 573415866 427896963 939059420 246495582 321085848 975445058 640282523 893128755 707700234 712440453 903817051 377376582 771074255 634820682 261552528 516272339 14101347 939581917 904739593 912105220 940049464 31067667 273189681 465914666 951908862 155320203 383498570 241078017 895429852 989292013 174070705 111004142 57791414 269881132 656943903 626539074 958496615 81657030 253552612 443369077 545843206 858498304 378991916 811371117 217481250 568216620 256214587 348606647 564679688 797896676 5444530 837063114 561373433 232295502 575808713 948162377 298131574 417869655 555974805 693191999 511615350 455697914 819279169 270165858 454661548 755582328 832557910 484766290 906258627 181331615 213008117 511233752 491519907 617046789 771467544 277050153 78693291 219040844 41409239 139341347 297193462 484689757 313861279 467448460 219075224 505531823 736824698 713054808 2437088 521777278 102746699 671800801 885587862 908797462 748133648 586086190 745669691 863180039 47362592 642860334 678071885 764235631 33793901 988691196 872811906 130134070 876186561 260959002 4940297 497466443 843871746 833167544 511625167 932665833 682765935 42265324 183163317 140283350 199535586 268489208 211310812 976694944 207836429 380187784 54345179 172116960 492388799 247801587 190234116 571182968 451039774 347461752 51986085 506451158 732420588 935935104 620502082 580549681 546185157 561088480 333903837 927220680 306455644 848940565 466100784 437654824 400041923 536703623 241709296 809759844 396628129 851469768 332626953 681871196 182669179 236187348 520620774 389975289 628739053 282638929 94277543 66374252 218425840 142522830 981300842 526071412 581704468 90737925 660682884 158261398 48037828 458081562 416388039 145906277 700019847 368613339 499436988 186482873 11481914 202860287 641359592 573264633 364651096 316885865 604330504 766431315 538086452 524357733 418371926 801922816 764379708 22244071 859823043 985991555 238625333 122078416 674380861 917018600 88849283 584376874 842527976 587137799 478650463 936491113 635934822 320827839 419194656 227125673 37292817 728834109 779056501 201934836 588617789 598270773 198544295 208008827 957810553 599325477 582619097 847673562 334822860 667400598 857661257 692336214 44858105 218552412 787145102 416568607 2166973 724902611 869317081 657149840 953906702 259270946 504477238 978549100 966264411 443150713 259726026 817565473 326425808 790365012 680639764 583568646 394259344 654903479 188329773 596382365 786853627 985514353 730789130 501233619 253974248 799371867 971880887 507014717 151922153 407930008 859102363 656290907 61045387 521442004 107964088 147050711 772605589 301105287 198990313 134551492 519886918 809184561 19615779 924638688 419069336 632413597 732777654 698321364 533736321 783856416 454196108 166562160 956927279 923059416 222573158 600433394 559201609 941156079 42220579 503839806 842918706 955822038 893259259 657106980 138728007 830238092 622504637 851639198 808749853 637784279 185869847 256132881 113007302 136246408 482184652 833733513 811605514 515986617 445601020 604465151 932983472 851812367 916191073 907836564 763726516 932549369 430130830 447208405 97955216 467946225 33511728 83535862 383847797 563417016 350557263 417410073 22757520 557545115 450356363 96483206 915147335 355819954 588626272 631664882 811191419 745144093 610979940 338167226 353694406 403817543 884585606 771595558 159051196 561708325 709586766 660932008 513630251 139969909 546456097 628766748 653102684 57036801 199265148 833088776 55989585 81174491 787278902 300442587 695454215 942521760 362772672 457453103 449499315 749296823 393509478 690978056 370821127 263028369 715653260 444277268 517484651 671939560 842481139 569452266 903036230 110517762 300482547 22674509 897518132 498496492 955303361 334191464 241657934 747506112 554052008 103039762 150721384 938338786 195034193 329176329 104521036 221143100 961855485 943132472 610179329 670558087 598515142 773557490 758467080 698242692 666383076 808248374 287227802 8868156 117024740 919629547 522101229 544123973 655977968 423950883 146165614 447055869 566192651 712809305 52608518 432148430 156567635 184228788 549959255 925002603 759440192 400329540 905371902 172478991 877946081 686300226 778999248 340121026 985673251 174860369 892516126 902367893 496998411 806147009 19109619 305469922 372906744 573715656 702960722 771007887 75285476 60663497 741890682 432291145 941268898 537660815 698263076 650741707 299781662 852016784 359797441 682558998 659813794 573154859 223385022 155080888 734150157 604123372 629737409 60047111 392616987 731696837 714888170 904708197 221319330 610324052 553596181 970302843 450296272 943299106 300441365 561215871 683423344 938619871 740947448 803411824 161562916 718817193 231845703 613235542 520943017 126871363 472188228 878574980 209363992 782326624 563363883 780341720 738798113 289023191 569500531 370725111 327663695 328253933 991342348 294568851 41211208 85672337 737435297 166352807 456317196 319429272 437326549 588600246 132234291 867685127 186506887 978253329 60731185 963904839 754748943 376791056 574270355 211399024 344491648 894368085 581896001 662503552 319685862 531352846 879480252 54899619 13497223 820660530 311359838 438613866 711232804 310415808 910954654 749357845 880610870 14221317 865151819 817034700 546819635 171038164 846492622 977675231 478431944 368939213 64889450 204876811 488288030 40486296 589126781 779927221 105967894 173656873 146868670 52794158 716575375 612300283 511674239 177124591 256867485 541675863 879853033 422096604 292675281 29547660 441980740 454136451 364889717 793530933 347621166 781717339 893065166 311098744 46183393 683956743 13508954 989705539 996772207 729541010 854216977 130777999 465646343 50149555 412575142 354161823 427868207 995096328 185898949 75229759 713134601 585120348 750142292 309834503 902269072 707613154 15374515 569407894 258819034 743154553 281331198 204791769 586932565 898909928 633126983 195454531 556250891 962532640 35264222 233506068 716182240 427776383 702318219 620170645 101378512 495643913 855893712 36045144 60671795 41438127 903331113 862048633 770158587 434910601 361623629 89828833 571347442 529885725 588474732 971678335 289864447 285680024 719832944 497818255 300865631 157533201 138125374 681832405 274274285 229096650 185390580 570900960 201727836 391805296 110947370 521100105 358706553 856579416 252910387 875921139 20395371 62724290 360261466 766551882 272339445 614365207 762737191 269681030 136976048 421638957 389275034 98147047 334006611 177742975 454021996 389740536 496137965 621323382 849052754 237043149 912499495 34795685 350618427 291330886 330538372 262511878 387372175 490704460 147841185 403691328 83495280 845128465 161140087 443924450 602047738 650200914 745629846 233724838 246388099 478324118 153316202 699974833 98796509 325208685 589944695 298099663 851547282 816427443 360497054 409744825 916911908 512737228 588964696 667572304 952246612 213989095 768148983 584388064 726925913 714469950 206905321 846760544 520549926 552497490 382201846 990662319 671954086 601274160 194751103 42040790 940796161 991820208 739074239 689889865 674083031 477322930 205427211 942184231 569581953 948340577 122016531 260895608 912621396 56183666 595825440 208351596 257238751 562336355 156708182 268523423 638407721 426715838 869558257 58294873 781826038 137679189 857754505 906944200 774156033 608226949 253955664 327078982 870918465 459877237 212917584 82815383 579795237 460576597 255110063 167595561 751731417 549147297 442317804 172330835 62293377 249462878 641352993 689246616 971073147 417596249 989866561 572816867 148048543 797185901 957232984 973656778 536180095 383231163 38186192 491066830 595116201 495976176 384828072 507796118 774955746 313640580 262682044 29906489 897383786 250301943 479389442 597306994 801043260 525090069 894353608 364309739 716331596 391967280 670159865 2947701 692489929 508984170 733267799 736483915 428814426 893298154 253366463 924328277 220061027 825406243 920519786 717523296 577854527 490254354 760632872 507506792 259098756 354450046 826114212 736870863 640969284 468219448 307381925 669569957 213478216 346797146 771787336 483373024 457627733 986461834 523615305 34634659 321266792 945667637 53083449 339521656 904270331 466634198 255617734 905994647 251159104 321425966 340883704 220413727 758010466 659542923 461170031 910000986 681751240 822295299 123072168 498578939 682947668 315896247 269977911 870838112 608296862 205841939 33261324 511430097 709038139 311417098 765275824 91324609 589720569 320724315 435374214 505376266 860628002 952779473 729865228 559535411 108605110 589983612 746062105 16742571 466321331 346938618 832645406 200223500 648365646 934931890 631851111 27478106 691370041 620633109 69450073 731306820 641297629 2454494 843102131 369677919 651987102 76532048 587380175 605576048 923410972 345259644 39890399 401799328 579162478 500879482 848456498 355709383 946960742 235964588 722254190 318311843 310594769 419481088 999267797 905395487 841506230 579342892 696322690 759136399 685332628 701206258 381551019 245170928 991453606 242444635 293744350 17281322 773005344 489418494 3482693 555112783 540802416 652192567 811525092 907740635 28027007 343695474 39858903 190114035 388914928 649114463 523557527 48855976 219782750 514945085 498571827 299919155 138690975 186425361 305001881 942108728 501352964 659080685 381815500 690127877 202802328 655451180 901179692 280283089 524956511 843407282 345568947 372690431 635228310 767449901 36201780 567266650 797544951 478033496 854603676 11007577 822532595 410272053 141020979 806364250 875250423 476242256 690653401 607437543 704350378 264491264 294213195 320474358 997373227 422447783 369362269 422369826 383579732 634418159 980513086 130839541 15854331 536851212 184383417 848021280 385748014 965652478 611794544 455837374 843925108 332712909 854786593 706290070 2098448 366073805 442836963 105650520 467347263 380753626 608692839 262602204 424410998 733660314 893128505 558520424 665046695 557397183 77996029 556067561 399496570 329366596 967634868 457451830 703160726 802322605 235037175 108370001 967593687 26109257 686042168 547235751 77685911 120956529 621403397 176721997 239991527 681540808 154589510 495623747 749682132 220057722 433647484 816592306 768744100 229850751 513035010 825436719 704400152 524895191 463995213 723031543 539800746 452567244 146163501 320167731 106636749 870454325 552787980 295487283 462925106 637834927 454205227 731161012 758243583 475287524 553673449 745123356 508658711 63840197 146244094 185629882 387202390 252783057 445630137 914526216 639647444 991516238 586654279 629378539 95073567 695859596 881094637 882424047 748144259 589772071 917217354 740327821 541118531 181438275 522933912 109846886 798287838 172799439 92633578 400630406 975455821 692285893 593391213 887243428 4964161 642467429 829925544 247008350 437789799 204294783 531673277 660686975 230461093 346451368 245257640 36464955 167593308 102489473 172964477 770322799 368412581 886456053 803935147 599861731 936114582 739212664 197984829 500315785 322810236 467939403 2707220 750916029 298574112 11579828 474918448 100666244 612587268 853671496 268612071 267986639 173602725 949845539 651793962 546292919 732657848 800172076 793041860 868278720 752119406 256215380 642030492 390432024 321431730 648810965 844697583 657531862 689772135 277838452 265781656 814828093 209886892 110834624 150636363 656708856 899622425 354953555 54600403 284293725 78081025 310160142 386579545 791525292 870510000 980676702 424265629 859845199 119964076 613785467 924538172 485878041 992785654 280541861 666430442 116778377 206703176 212801895 554785207 956890886 733800789 810551766 175986508 95873057 849548301 393236945 455940396 587283416 78899672 431561791 29502197 884963023 156528344 294974550 62212254 59017366 89139497 113462480 821193145 572035816 258670115 130918197 344898224 733066471 644616596 315099413 528815112 533549155 938817287 714419020 505427362 790625042 962243329 889464127 166880759 91149782 466097728 153609755 164319578 978013180 99483389 187275291 548921655 701991033 696536104 947936192 510851928 216363821 48154288 602765080 528793372 90703393 152344762 928131321 127322303 325335242 882662631 318188612 350933654 364011333 241998224 994952484 615758418 261200283 972879371 68069454 752279610 778565372 543552485 494368321 893785203 948410629 331219495 54433413 245482553 417563900 404378770 451817709 258677540 699507984 215398629 234250967 934104678 913971611 253789204 983887976 811127305 259617889 929215376 243581394 215828532 124388305 785387651 452383375 122417252 762904640 271004946 777172133 530870452 552926002 278541723 659750369 78260503 702195347 818811382 598314270 594542746 915967991 481336502 586745725 881459877 381832160 548686439 322733996 362704952 937549046 9923791 180354849 368624432 43012429 60067374 524064094 137751937 98035108 757356671 662302508 386943099 965430434 127507639 79415777 476002822 176130585 200612867 602627228 632198119 85867077 747957515 928613765 544945915 859101451 427688755 66800912 468273785 727922492 438333910 502959928 720812850 818105297 290413451 955423941 993223890 419277614 64728930 30779016 209281822 474628705 895415333 634161820 163287861 732275297 802161049 545897381 626095824 294913361 536324540 884148754 84217731 332628924 133743622 75869531 463159292 797283288 319627946 222389573 48030017 439835845 789987284 203172123 553822708 139179469 581167850 614167796 556145040 679581603 689046476 824554226 12115882 884837798 875450389 278617214 387956530 600935197 612381273 366601615 187094449 435406457 70360423 612276194 120533131 783440024 958741383 129747008 490832444 849385982 411609531 967381436 83999644 692891163 125116159 473486580 385974045 644328074 614610313 306640718 155973129 627546189 797506571 593914426 682161094 114451732 250570478 300342899 935092499 501921397 542552983 783877951 507367242 199621938 273333668 149574572 268674462 779995768 926857773 392731603 120979036 566058780 617168645 403973655 97470507 882038493 201875447 707796580 351565645 236034983 301282315 410063218 235280094 367777484 973061824 987993600 135253522 292935754 647738193 646612507 315553656 32791049 102104563 788976726 284649531 719720732 396929810 223262994 441601373 123884797 123651737 925534645 400587515 74085586 48072488 143474676 723653518 879424684 139632477 712955147 493887782 825087172 357166862 493886720 910462126 322810559 107643019 813738470 898218797 34127593 198707166 643180309 239392001 289316730 995772428 967165044 774970147 973425622 658130514 304214962 781779559 613663686 718283114 310235014 832582330 839640257 860080326 993194739 804083300 986924840 458246097 590146696 662850886 683130755 33649459 138336665 743752219 986309062 159192587 941500297 434694072 34172048 933778740 270457602 802502733 812850280 307455618 206246201 420271267 575366912 690262020 368634668 925322589 330237044 182064449 92570341 192403001 923909769 539991165 893457590 777341774 490248688 374111219 319509116 588926541 106972546 303076633 103380189 428963266 424570243 538273761 961944716 164275282 437208801 582201332 999221634 144687100 733849203 165275126 52596292 812008794 990133820 108731591 316907297 651203295 24875175 830942910 420256627 523289111 379146698 300735213 1819866 171800300 13185701 197602914 877793926 150991581 516018786 585771361 31485036 166171718 671559572 822994604 560387725 561088412 189486969 483626173 860629556 224662704 202294586 223341320 278292278 913911785 880483112 290114876 826339633 517870476 410686462 5708416 212086479 772304117 814389795 703991991 967912706 20377053 768526566 33981374 35929159 393849747 500348866 703821995 584887781 484467269 310182809 595532557 868261165 858454582 768489979 156737072 195381945 885246215 969835614 268134488 364230062 172380400 217275748 19918850 997261052 107599877 743240730 69663016 550169242 668948851 529620789 973255291 926596812 317194945 722715220 741330601 530839391 96248082 412505411 72322966 796966121 74083423 792072500 981022116 901399563 335548095 743212549 686228717 552219312 984269217 835337598 372233349 711347021 913022222 267261073 210730938 948387361 107135209 416732826 794991445 982270068 304766000 803773087 122099929 465100249 500808762 400486543 490072001 331752813 458100216 940045444 511772355 208821015 108017462 213725186 837725456 248582344 949072856 317458232 576679827 398607802 218953503 983959611 125961264 994399155 507469540 347107919 882539780 22044224 71110361 133854496 580149673 120212476 245982669 208071682 934688880 342980552 377347814 203094326 35385254 675148818 934917350 412087078 622127313 548687888 326265704 174322086 232722418 867985667 259495969 218908467 557061315 348161911 354669601 723836981 695531512 938197119 455433489 455283262 403102335 694013179 128843381 790832969 937090753 389873363 551732969 903765758 272335841 575934010 892752229 835955178 522048249 81219822 932495995 523177161 755421794 890293108 70693781 16091582 70699242 139161694 736944697 195038615 956827421 49625990 930381127 859117835 733432958 891102546 15746615 123926013 264361676 286663152 38893148 178558648 366304576 774123672 183241253 150333746 854628299 769726159 623941721 386069067 813277274 129182624 981438296 244768525 663014931 43390178 382142558 890551787 580249751 176436343 430063297 375450115 937878848 143363464 479938864 10487902 204805730 729985995 960378099 229021485 768210571 935215807 394723631 921783563 547503044 736600300 757889569 607048767 505051855 447067942 607471200 421624312 635656296 751452105 878123549 22350737 119081607 593185275 356558947 445156812 844821402 497116398 653422681 142520857 855523789 331780893 266077820 613472717 677080131 286925707 683258344 767780205 645701723 832132873 63032718 692676067 767003885 993199471 867336572 698905028 834270605 852549856 557640730 987391634 572406724 780195592 274498921 282954229 891380828 379678302 830463044 994026242 736672402 709621604 738403744 708937590 726729571 744309220 157103053 938790138 177164482 653753906 605167028 356589662 665303773 869861486 834812952 782816479 913550685 331361729 132644567 442660706 173528740 214060956 323429416 647909816 142859534 580842750 792757725 455357403 442253874 61565869 59226784 981859629 180031008 507471225 456451895 475919293 838669475 951408509 749177793 262169986 415626878 121935711 34971895 186688927 573372080 849003150 591374702 267110816 664889266 804367233 511787218 44533945 694289589 81238267 667099946 354910988 557177061 99769675 515027992 700322529 552524971 605306245 963035671 769521644 228703460 64022220 188377533 411365516 84486701 303255946 956259576 249649928 919335448 663151795 875576403 873507026 957522037 543995144 396284463 339497925 129941644 175886415 980042252 54284649 755535455 463435933 846841791 58666539 889148906 162991502 488601275 88897703 534926436 431492489 626871627 121990368 422557054 179144446 553773011 35604868 289744544 670557609 379974163 211681066 399290928 240899022 50172006 227263381 639274700 431238012 171555581 673987824 239285388 90241485 277004582 616042769 82085443 268276769 512047240 929058488 617972925 561437032 419524198 626046670 158924800 602857815 900120793 261729192 953932940 898950063 7633945 460207172 712929437 203913083 884555698 395100040 963033957 385150031 571622864 430345096 801585236 670491020 131935349 892856510 780137554 299497368 645657791 992605521 873347329 931713320 425086501 251281488 695676925 880897144 204120504 483110646 727273501 103136399 487177060 690080229 80548529 490951294 927357230 436929645 882068675 389109407 115643509 621006788 22771288 693546967 932633906 470077516 878099374 423620310 584545594 801974994 652086909 613250899 430330232 441531338 625729848 233573202 154940213 800490134 899306571 662547552 47778130 999663806 455273308 807609043 717195146 984012599 200845963 73513740 85912499 724567966 596363188 987040950 410039547 344967036 6653353 759707142 929809196 820243841 260005242 240854778 391722474 496320202 474757038 318327452 672115697 678498844 224139145 852372030 215132249 918056232 993930310 394623677 39333844 818132423 173343836 916912064 496934380 924466494 655185595 864960248 348289607 134956921 245859341 392322399 889443812 941243984 991448055 899407995 458680413 625516742 909971543 917568409 237141797 587086406 19574917 781702420 472800457 252271079 645460116 200373645 603786289 528051111 258604175 232065842 593380317 803623857 827474366 657536761 570344233 743904153 592772577 974750691 749734795 50250651 214929521 735688252 851006418 997029857 956371427 443836119 610070886 349906364 90773734 284509267 272360844 29484264 864815521 809259610 372824225 513703114 645945592 99593439 505199964 558111155 297990086 473507677 304622094 560058395 640748578 151996956 304409570 267390440 504176284 769257325 298944543 696173991 228237182 570644714 737613155 597363663 912372237 667415737 614181095 457802755 499190726 68414664 786916799 136911438 105082275 752101903 84669465 450412646 929057110 707922899 296386171 65060075 952092810 55930079 700145926 846609062 449809447 924463306 412961463 485923276 508933516 977426741 23230114 195077435 4815828 829958924 227512119 794026937 968629012 432444354 403437439 100014394 209831320 10279063 330391134 838466072 173350187 216696275 480271824 788275290 863666253 362131465 44744237 408188655 14554492 357429079 892133222 14066418 422359662 564768418 126294599 295800549 380159827 416979676 129876405 722516983 203692565 540863552 254240240 186114880 920787864 493915026 205191119 197411586 692359420 213542240 854398984 682506215 58354392 520311621 319204455 166184519 955080318 866674979 898373395 860190561 940748092 129115750 418935246 468659870 116048790 166324549 535724851 916115155 978062991 253648898 437338104 234529661 763484895 994486822 288855595 152643588 397226555 773936584 191112311 12552954 485274257 240582853 123528542 915867483 356143435 761588230 220205181 530940877 843214985 718210239 141979085 76229599 34816105 589018539 191179485 379355979 978513985 725973587 962590747 866669877 842714592 831865926 298050570 387924843 179075794 275982944 904676491 434694564 937124763 605617669 805733910 179168963 70856952 763338340 888142591 520494100 813247267 473100214 520342195 504751755 682555662 621654141 616626426 837229065 983987108 297563848 776869172 29527192 402434316 560130411 718968734 624020396 9076199 52929865 350886540 796556129 763702927 310512268 972968366 516191681 683800152 202352104 269935437 528905725 780720337 615429597 451153292 149005745 52451073 110342132 756708777 29831714 463850155 429454847 942645051 294700928 954550156 199577946 104422771 304530982 945734298 673820718 922071133 469161943 584640836 978443434 855605790 689716992 903859382 525859402 275064373 172974075 364935956 114643730 350364347 395373639 319368891 95913169 443494821 362972114 914319749 142909537 530793982 974450225 805708803 652445922 575945519 565112292 357940930 401924868 50205241 583672213 728987017 850157628 892277495 8959319 812044951 170891274 478383455 695149544 43671014 219673915 231567551 914511345 574278252 818322723 836626689 995494722 316102487 612026592 573712873 267420185 328881998 44615324 416126035 742200921 475681204 169607369 255915383 618809045 986566118 304313188 429070375 963627140 419329145 306882356 680917005 881554891 472932991 224087305 332865775 618630585 37639873 297336575 543024109 1720644 198147331 907215290 63122623 817837198 349706052 832511402 971597561 764238884 942398205 351598662 152941384 217385530 78741599 228752210 846535347 2216946 421724567 151942683 326774748 258039444 990547980 595494582 319242815 111553237 562278300 229328198 171930992 782956050 952206820 706916662 897351262 304839571 306584439 32746616 48407188 894069706 561291555 953364686 807544692 824002451 183156529 984999167 183353212 718891380 831223460 666455070 446445443 741895387 454675062 269425864 757962234 290920293 224695519 99698276 458367020 855279123 605702288 936512610 400192384 69422739 276216305 272621439 664670388 789987455 912420969 211022589 956087585 856997527 166560660 753319404 169703931 477479431 228330124 121732198 244102544 587410342 277857570 962898636 816162950 828190514 743515427 328191244 909773086 657696406 360022933 790881244 397762677 413613349 300723705 631046141 541211583 589370590 572049800 469842810 68960140 986487720 677351032 945247464 251439366 954640020 177786678 957438630 449311022 201868064 303802283 79917084 195120675 382383216 191415929 578473725 480684124 2617493 376528957 436754054 130126827 98377159 153976524 930463934 325610426 342947244 281733751 231762870 204745423 685814417 592766793 584386248 153823113 46108333 999039557 349990874 437756130 248286051 256166570 784687770 889797036 120727165 831578929 368835520 597284310 223892339 608750923 423896145 67897254 95603364 53540965 750468311 168385791 476062362 999876389 886317228 941067930 646314312 25400492 146055982 292950862 260377932 277093331 908194057 839726921 232158511 250710128 161452915 269385045 65189537 750544528 819436904 719262742 718250432 290995644 160461555 178294089 502032975 791377462 929020007 160585988 861250816 774087226 451904415 337414906 262261933 16205631 43533124 556856758 424638360 960252213 972729861 276841948 768833200 253347783 360540125 147147629 768047821 360344984 210858322 961339649 441951217 564894087 203127473 622833420 704380038 811526636 547841877 879173915 567933092 254047706 546026208 765823766 99127625 573374045 470494334 374991997 370865569 459829691 255899174 326462381 2407997 704639669 989174746 470964506 961932893 726795716 184882915 549464212 990812456 525795422 726743319 367004292 666019057 190949424 675032597 187490093 241507953 249945187 538843782 706181101 115085841 2157785 132717915 172182139 649250591 6543726 537404179 429831208 22715669 698614073 713806579 90231584 167285975 145507274 376436813 435562408 414465011 931675243 513640892 881619807 943050720 320718689 818073700 803974783 29033281 100164906 186859828 303560986 4454689 479947711 647093285 688500831 196148791 262409680 648448889 395091412 964677665 941053964 97785086 716830875 286183082 561445976 742592331 38931119 702903557 550646037 350487296 961489957 697924881 243543132 243341319 351420525 801901717 615850818 533464791 716323217 731010690 726705430 850187693 754090866 474887222 46378144 702908370 374250768 808179381 882697570 637386970 116075456 423233520 396848856 417546209 232163445 326884351 495926201 607249613 768267001 258254440 630209333 455009169 732014386 274513239 846500406 149480293 764185184 356568806 893365409 341354000 926387291 192812116 881180308 165036833 430505175 85583695 135850919 210208047 293824161 592692524 761844269 257000221 276282080 375624235 687865458 489647450 239265367 120662197 763442683 606423322 501565599 75354271 258415307 332241824 103825263 514860135 570086042 951264630 339932118 779647091 961984030 667002801 597207420 544169047 587723331 212632879 953544678 158945805 441656692 927935449 987150257 622539580 439833810 970629603 872067028 428610163 208044921 593800457 339832544 766500460 629934016 470887890 403041857 90404172 626126966 922443982 495644027 440706527 445237288 766561241 1226607 89650910 62913112 431348055 688219029 589283370 945382596 371550584 230525250 828531727 469955750 629567859 601650401 423226500 293518832 155298508 164752187 657859687 41583246 261440143 304418481 900704452 762606501 481576596 522902654 185174540 21233368 636586171 741912567 458272095 251421055 272222255 702794700 379788228 908474351 375063205 38880070 522104686 157806263 311092635 603009417 338746102 216596958 157802907 75333841 876464293 934247464 771623799 380626358 147745705 158321744 371200396 792043113 571197788 249180237 336803585 911984118 172250242 480099983 891384071 240595330 836781704 358720 807647768 343129997 226328264 169554308 955574585 267500335 369712066 587372219 480183098 488352091 453192802 115146172 924432370 327633952 14236478 31848986 469123461 460997092 684994006 497260896 29599648 391472298 35474900 730451030 278644921 256004427 409098316 511530555 635637073 187936958 252240122 468161546 729976115 53504337 123538312 197493175 467219636 693142511 561681095 838146417 143608818 705667929 138137074 34965727 141952023 222784879 421219824 250294885 549521557 111318631 246579345 190503518 741764714 980402193 661191118 266847840 101551963 579449627 616314634 800117885 72595257 721059400 192969813 705348734 301693217 317996473 365314469 509961000 287390389 23016998 920403484 533187960 582037862 789338147 751139143 200690152 17856939 36110174 924230747 666824106 690543177 310436316 871669624 646082537 769898378 569614145 932537063 623683341 660245128 346311175 209460829 587856885 619024993 635020483 260318776 56555836 847191937 715430757 331948734 618220662 493302493 694925429 180813155 235027825 870884148 652054617 321915393 394208631 229318222 127637132 988687903 930335880 615825470 427431142 116450348 245167266 279969442 425870552 909951170 809672443 821907935 517617838 397282277 284171586 920969831 575051981 541126723 510332643 567392756 286991604 541017716 580720706 618306252 568488316 719697465 193533948 549070077 853957786 449837503 204439083 623126943 248918426 423054555 66546592 109847063 432951331 841782860 481310505 837052752 843834231 787950845 423121098 325467393 33685937 952163138 402131717 25756907 141909254 685701144 178557972 45430298 659674887 294574183 752850731 760747553 190080987 599013441 963958200 388167264 860820359 53537826 636430501 325427519 805007655 306556975 263907730 106256242 897125939 698840953 301749277 560370996 375844797 365456185 431252251 204791694 462271919 151136787 731233758 512169871 253367312 618113365 859178350 822726034 322838077 790974006 473775058 988892285 240994353 119162649 215739718 979132670 872307647 345916105 530395012 544023246 441252308 904308156 578660605 284383215 847250360 199753043 491978270 668275695 211028043 779657493 711259790 881999653 187428682 438707193 839518316 269645296 932828808 831634330 46878611 615799805 227174199 734477186 487261911 953176447 596208415 239301218 268525382 979231350 837094371 623594837 655370601 690846187 640839745 59251490 429619842 276499247 969602896 95605113 184049102 80944929 758718401 494038066 302897602 419140967 231435039 276795027 438956880 292875185 317174033 213442696 803524384 619149563 316379285 217564651 908488409 753096393 6582084 467691451 310352471 596410986 592594579 217892198 858206964 431848503 173830413 820668929 306173633 885075666 127040923 97955724 652782539 678748778 1275070 804991024 637310808 462448627 85487057 392288642 68124457 367679600 614626889 69127103 461128888 89265707 311200502 508835088 197213817 822651896 661015873 682353349 220284698 849095287 188669550 329399451 153395396 43501393 433695449 240097784 82511961 374328952 106383162 152217899 299590326 800325993 659087331 717689518 422422000 898879594 781472766 461363814 25746584 678275534 97608913 455302367 108523257 460177197 445006587 73081489 509728854 417983151 719584694 586429728 147019310 191949888 758683669 779569813 223441274 926911706 781728837 31538344 788824555 43385280 961341645 3472887 37048622 156341182 378651599 208264525 939479081 455758956 182369862 755116766 656043069 535258986 806241096 880591751 671317123 656532387 516510020 104070672 514821393 400452236 764435266 788473963 623544884 35311971 889840679 203460852 196471221 767196274 639764976 255218096 569623574 839086155 203928307 215487888 445124564 358373643 799734051 480300461 97699492 60779928 435533131 472497291 621611191 477225189 910660175 132594519 279638008 786343211 80524912 38971179 873694538 409797935 525524614 906428487 443661260 848738177 629739845 963802967 783921687 977622456 937705595 561641649 133681020 787761592 325682765 103732629 11211591 829729006 97093759 652208493 886653441 203987343 476032939 582313228 148919463 998064607 904352902 719231985 911733238 911512934 134992672 334199683 293592992 124999225 755825698 38463059 538089365 298921529 889783823 209128799 231923005 931217997 679500421 165117259 415810746 9749416 893495675 838683047 82453033 70172935 726384770 61103662 454941919 860531697 794424838 685913090 90509485 799012343 504506508 545285875 382456093 621649395 693252595 144587959 318571700 805386058 539536053 114404912 106108464 57585964 770735908 525946027 270901194 450033616 221416111 8039709 731152499 890160059 786480412 836284774 245796631 777424119 846948301 34464143 588873182 86681693 510507773 313624845 479699816 572363470 864857858 794621949 6382606 849848947 279214986 957837928 565936934 616960002 78478560 88999294 423196221 256144889 705119525 922371804 158779484 722270690 5015449 346125768 942602565 280729488 463313873 855298673 815205556 76556894 460524800 828311857 417293728 734156404 192994096 182507980 25514873 639554051 719110791 432951472 444906345 984409733 665877125 721344565 144540053 789732864 623316290 110524892 50173531 211569218 785721010 20599186 677208467 414550051 219198434 854018283 81582544 538096328 75658298 812825705 37936030 840878299 900256442 31668916 706562755 662365654 222142783 411518944 958523263 109610807 827814333 734149292 135326158 784717771 296001411 256931775 144076450 364723941 752045180 564997355 252553515 705009572 105113706 926119532 530673169 629642803 600898091 865913383 604274869 729487618 43340022 588258541 134092406 119961616 428352412 888510391 333613543 993035810 205456329 556531433 178898971 22880778 408395585 85447057 899392988 902339554 298343205 782744742 780186348 808745552 986726702 363715659 539984716 740735938 799804654 760278283 120744563 296450993 1538323 973256476 223072916 561102815 770442406 199230878 653333979 114408858 574662213 887294939 638234542 515055865 223642478 762304134 364155373 362683419 740132790 384410366 756169779 652370029 485392907 87178377 437604117 377628130 822135287 18277787 382140767 930134074 118825181 839594767 340256092 156291133 7174460 169786218 680515597 956274431 555301865 456512028 898202222 404500252 53342038 49845951 311401142 889462266