1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565 5604 6842 8349 10143 12310 14883 17977 21637 26015 31185 37338 44583 53174 63261 75175 89134 105558 124754 147273 173525 204226 239943 281589 329931 386155 451276 526823 614154 715220 831820 966467 1121505 1300156 1505499 1741630 2012558 2323520 2679689 3087735 3554345 4087968 4697205 5392783 6185689 7089500 8118264 9289091 10619863 12132164 13848650 15796476 18004327 20506255 23338469 26543660 30167357 34262962 38887673 44108109 49995925 56634173 64112359 72533807 82010177 92669720 104651419 118114304 133230930 150198136 169229875 190569292 214481126 241265379 271248950 304801365 342325709 384276336 431149389 483502844 541946240 607163746 679903203 761002156 851376628 952050665 65900098 190663895 329465723 483829790 655424312 846105207 59659345 294832206 555849535 845451794 168394293 524489633 919131236 358101188 842294458 380093635 973317739 631364771 358919041 163085871 51636899 33138150 116957133 313409595 633773306 92212840 698779560 471894966 426095697 579278679 950993537 564455068 441341388 607355848 92314139 923461193 139628697 772315124 865141262 462012100 609054799 360405990 771416529 906275738 833026314 626013695 366234773 142138747 50053451 195111874 691771539 666639862 255594678 605020267 877836865 251420055 913251795 76618770 962404109 822066609 921404275 553300909 34034576 705835739 945788142 161764778 791147031 318294510 261388533 186925784 707583568 492066304 261781722 799651371 957983888 659334583 901645133 770593893 440370753 183625235 378560468 520156484 226737408 249156795 484054969 984748801 974388392 857051217 234580494 918185048 954527725 634670238 515722183 445077675 579794696 414291632 801431761 987720613 638394517 870178779 291543752 33715345 794517524 887745844 280887521 647955762 430130843 886074754 162524015 352062132 574911451 54296007 193312239 674712845 552038125 352793690 189230129 879235639 77164040 400735924 589624482 658601669 65624947 892508782 48557230 464688729 331001112 329403841 889995699 475500379 861252717 469588872 691170891 264705550 649346389 458195434 887138222 209782361 269037098 43971933 218622830 821886406 889325156 187382610 967812066 811884457 484002394 887640010 63450972 262987839 98299076 771593907 383990750 340730457 843511181 507823585 52277122 146853832 351251488 216499848 493180960 534144102 811891188 655571237 123636580 117094772 660996042 450788085 581470848 590750961 710078662 460134446 492119591 815657844 313127518 674106755 677754166 938227344 44335259 224125257 465248142 226282178 648144777 460756077 440770104 653776934 337732887 649838717 162400242 318354477 743319506 646334976 175253689 12190819 56222424 493429286 105789849 135583136 564698016 148043463 31482428 362307250 697725463 639765511 516058350 567257844 451998122 563903916 977922801 561057532 47272858 677426091 204766717 877102285 249312206 455457467 804721330 406668585 647561386 348874540 386019979 687807486 411064623 261801278 795426797 744925279 201914823 814710748 855846812 386342668 412806344 397320431 1856002 566839979 256373010 467433290 501008738 238424247 841286193 422276938 710990148 879060957 598595750 674806840 438786365 422967183 604520316 981597818 853854428 839863082 122733852 232346565 998034201 297756422 357229054 630580603 153383543 764261987 343100308 827643896 416787078 179799071 727027885 707610976 35681188 211760660 980641197 291472680 174788100 234477796 765049764 944960237 625625204 986747847 149364895 901162343 292379156 236803268 589729867 983473344 632172390 663347932 71937595 204211351 878003336 560659972 802120713 57680992 315037078 519256288 619426225 243341899 432731653 671201605 407132464 772643850 708202897 895227873 939147131 226158980 352569460 914435167 299520730 934369952 772742943 485995804 604670993 588546875 873455643 858719939 162418614 568367797 798470924 541010750 200290248 488926113 234313052 874979491 640523709 997432022 702040684 20374921 595836497 474555404 781133116 538144151 186008554 358877508 689373802 503521687 610029653 777949585 875515482 510024362 446858044 575465827 661307142 436737769 88462778 524987762 342495404 941692332 849747892 265936873 474948616 504773762 980535445 926283826 850237717 542565546 670680741 945566215 400298023 932584250 223091750 988775482 764090093 907541246 46975882 837301480 742593756 821767311 788530091 14726414 928267519 407069515 140702566 414504959 979766137 967617451 160137671 723532467 182763772 440402269 931186076 93827269 410332422 437279964 361933481 768590964 971594332 290703335 345466613 509333323 783462874 700353811 998053423 695951817 968864185 90095664 788791868 788761100 436614829 944874145 971493851 738271130 183243673 34774568 56758830 214436801 191896749 587528771 500141973 23540487 785603665 157077956 238433306 937355474 719458860 644981523 601727492 974161715 582979776 262643364 900743161 668102774 291458116 96158293 528478740 523557563 516686878 714732850 950939990 249233922 536896158 75194299 771341153 950483521 270778323 604775300 216263990 471103356 625882994 905760934 47380774 672036655 238972924 467847383 487383322 592822269 64651127 190732804 723176670 273170105 93887238 442259364 871192639 108961565 323860103 964113996 435156570 509930788 912665398 137156811 631881170 899471585 379261415 892227493 870186981 752674172 420308409 288714420 259450487 60137990 784029219 103308331 18767654 813937043 807262118 565177768 435408279 440012083 204043508 774136467 391511503 624960526 415127819 18663124 916889038 368890232 290699953 686979750 354240350 667670640 65917821 724286121 182485354 50300926 876125785 625540587 941717530 729342041 748502400 500913016 210793097 846191623 118956886 333998542 512187512 301206680 136457637 828534063 160202680 702054616 370854192 586614093 754004000 492174262 54017789 87356589 77174753 986421568 885740997 915664840 55707369 256270130 818238524 243590297 211465908 222654292 69227307 684256149 397761107 179317834 284867895 559521640 469525298 413738695 493672410 247355194 488052822 116648940 82360933 338862728 579625137 345128610 76204974 863709100 669987573 355155322 444072928 243817512 356463449 463459593 298559809 975898201 985312380 922853455 265621322 852865881 841637188 724055455 623176675 426498198 713980612 668762485 782024479 929630262 105744172 214446631 685346825 819180452 163782850 897152280 987005893 106366649 394919291 563523726 105759072 578252092 314832095 78389495 914348923 755165455 809899394 119303216 127490327 714292700 120828384 956776274 299771298 993554713 187306355 204199590 910814072 531107155 567294434 651831275 212531355 625475178 804603285 858322687 83951792 388068814 826110444 736537262 721853880 816834141 403794204 827338988 797144838 401862965 960744572 450199759 745709343 619306678 487425723 180456559 771505384 926679712 695253620 13555904 77586782 873712396 548049524 466368066 744907768 818357987 537941008 785826835 883606217 591211890 78188951 469929316 381731314 184205912 662910437 55472297 915686014 289905960 231613465 765944711 315513824 745453129 436276845 987804192 35759274 503726461 736624761 715784498 484524517 264459758 360075815 696481968 731902013 735430558 45706580 900537480 380544360 3006536 540279196 129058964 315151519 595822747 762122041 610380031 577868986 913488707 713329029 686413200 881512809 980629241 265532172 655412847 401015385 708510839 261380697 821253712 410793417 947999133 789464437 981803405 619413293 211806896 491884113 616965309 991008959 200018177 767763083 207177876 198832980 303393975 407426187 472739479 590881950 527179629 384933555 912415242 228674427 615633542 403492563 183370622 178855437 219843327 801012532 506520143 784152044 452823881 364081481 554118269 785359874 233868341 331555165 197645500 444126703 29122145 471267272 420415731 971993054 112939867 323234900 967384697 46362306 218639399 439763972 491141903 378157063 503310307 172240346 167076640 103123259 221460673 332968449 203243498 218028019 159293145 303294013 193889672 377556164 562948699 960053773 965956377 995720833 434046990 235693016 187101362 461407065 544027140 552358863 662429610 159502303 287775078 832232334 310487049 577056990 901531574 832483138 585465157 876287633 400598563 193324737 538046772 10629153 832384477 706971434 990848907 181970574 819840435 468346181 560672362 719302476 882705335 970731110 805164463 209415733 692608781 687889213 26644634 584798183 514404889 720643756 411805032 386866238 410945248 83088389 233727403 808363787 989403188 674235138 909568920 127868104 431752887 449794972 4537640 146047107 91463170 721594215 412498730 267916527 849719397 601967950 110475850 545934663 134006225 751102193 975509535 985542976 99377406 693208521 338074175 141142805 562494825 975275507 718144722 883095620 113810422 745330911 286116140 196581551 813371701 994512491 482643939 20935422 835089413 603887826 751133120 456535300 781768306 669594459 312769781 681327493 811911747 770957190 873513813 574165984 964782943 158893099 783375126 945489723 769508102 661753388 469024085 190294698 113524554 582033654 707574255 7804223 299717098 42027048 979230240 500126858 217557292 825983573 472154800 293441142 156076708 950045408 987677675 825062835 558779385 45118111 879768565 459134695 775265644 303676317 746614293 921136002 520876490 550864078 107387303 961431801 21822685 548070138 911355084 722302533 850552632 790837477 980908098 524414757 53257632 471087673 466358153 971065097 390687549 925200477 683696000 38543258 908902409 960421753 927747168 134625524 37374371 78278640 293093312 761650898 627356119 793646380 393282587 26815014 104004986 554321233 754119163 217605233 80882343 8430039 607239918 863868399 665641591 200405010 678075549 504122097 456086854 892107649 101601475 642893618 763439332 447538888 7624065 943087401 405434792 300523571 261410002 366634737 318510550 56761460 223816813 775139539 381218165 559546383 280702444 852919705 361645297 523563144 436288825 197804276 657095060 65348509 171446592 411522257 554959905 959370250 222628071 8757323 463152525 469598373 860369720 223085910 838943466 158927488 154740403 429949195 217656669 34276367 893167914 919267944 156006762 722532215 733217401 78483700 190718349 821430681 627943092 330297101 991714682 469777546 641365932 937271410 994812029 810573279 830715255 117959994 462442817 904428175 66235681 334575195 386049547 400699748 519906738 709013288 232711897 308802137 210570381 327521684 823501640 976117578 462789176 145744757 267682135 911841173 430902910 316193385 277591845 887746904 871010283 236587087 178280023 618144737 888732223 170752093 687967705 529167696 913127897 759055543 228301023 145514410 238949095 19521278 315787100 949011289 16059061 429443769 769959325 818692500 939069545 519892285 304046880 641167982 943462443 538680629 491951878 961557284 161122633 459565775 76147119 199568987 167358588 205182362 502957838 470313892 665480390 291741075 704046300 780506213 117112782 516637574 909919433 363156545 798068198 603552614 42035762 604815776 582221940 689597789 589965656 86429533 4539764 755635458 970760570 506227020 719732141 395147060 842851761 458582985 177437162 511090813 813295366 720997683 956082895 296209189 556706970 380252026 94660457 614091165 161803067 69314096 584694959 103071714 29525012 264621443 603509137 955630325 255944605 94453147 37060194 210447362 93550114 672447994 929855142 967100108 711452871 433419864 368765833 426489502 250413181 884317146 234695598 896726052 734119717 142403439 389710990 731090914 917473215 901436046 712756429 614517452 156300018 97377172 416958215 752553618 790067788 418043613 959783150 648655864 409463798 358017111 740976823 442101265 391887515 276427861 775360050 629221296 430416676 811796751 78342854 442916000 647151465 322563064 485583115 442730211 497027782 289015872 943329360 859484141 812375298 885058595 241042906 520970883 160767919 126553570 944497960 329678067 940326107 731903704 347377065 456339547 449791876 597743313 922274884 259550708 609031563 332455751 646105764 587244290 129226869 756874430 403802621 97122365 996550279 289428767 520908481 643914213 576143185 557469202 189626708 64336127 368670893 172625481 858201102 731460531 616781910 826450119 589067465 725047552 551938606 210258004 227272552 170710655 907007159 352748372 467068499 256161777 421355426 701984425 450653856 465182604 253351744 16198701 725422569 870788148 458515496 967497175 28817409 991497882 908494878 797573235 346067948 899607386 769099981 913005177 567852830 305054849 384077861 61355629 616021695 218767931 964388942 333550144 793841878 333562913 560364119 709971189 81043042 756573719 551444567 758802696 461788387 914714689 551960206 850405748 277914548 878451602 191414453 415170109 956194187 496312912 129811507 78000415 635346181 438624584 591799123 424615523 799674764 735391657 762276398 166777153 452218366 75326620 841508256 258879217 525519736 731431052 307140530 654945124 576512432 526620825 362604563 809869960 641931378 223555675 764195688 553664413 317642787 293575850 171357637 915255005 40104099 662906165 667902175 279878582 486438191 577415882 850313046 766333905 544228988 67285271 887963243 252112594 916367035 703982512 67288491 592081146 45637012 560878335 663483644 22781254 942499018 77421617 260336489 547396261 953763243 287720110 605801337 267658112 175734192 451554464 957380931 271455813 514464200 122438335 575579760 23033556 578030465 220836968 134084711 779274147 279054037 33468495 161659830 922750433 607861534 891502477 397835754 958696630 88539677 878100056 438230375 255418407 60757385 388633373 779691597 823000458 111977999 170037444 388554399 603482943 579387282 540240987 394641502 953854947 74470279 955498012 301828049 425067436 232542163 816751832 451659704 693363835 519551381 255398830 804049610 134694501 309645924 920867857 101208804 347770631 77346579 812242192 659056320 599703651 286938838 179808036 74399716 93906516 904394787 311971122 608541730 143765307 706200035 503606735 352825703 975338211 255976284 581697438 477441432 794879654 499116496 936157377 421312684 368779040 83337268 170690881 865392559 522198100 131287949 179172889 577641646 247786341 826159001 839507844 300835222 821125480 413445282 881125015 373891968 520062869 615334227 671446889 361677049 445723840 516236514 754190586 378693338 283844332 490711098 427589881 548707483 158817855 759459603 399281837 201122203 542841279 290175016 419881754 588657253 789798904 693017290 607520099 721019335 926700056 789016658 902509019 318128148 513915044 314816310 314613747 963072738 460865715 7104053 704246720 887435329 317841679 656887491 686100186 726475741 816517425 101848106 429451172 319340362 271932860 87747017 418851874 636011438 158675003 345931616 961443105 578721809 558320391 420397560 177886103 632226736 27161747 289717110 431173552 120745313 430764298 222642780 666886146 934989406 574116562 610734665 898593143 241551983 107919969 17017843 557612487 63793577 639322207 900063930 172262920 58199379 128014829 975105776 537384753 438528842 795031041 633559579 940511474 68309233 485898116 309871260 140044359 603177949 701904833 837474269 892648166 747029022 784924598 129459200 822649533 952073218 787037264 257286876 417634466 863471311 22513163 808642304 812964544 809347708 733997010 837305425 611588212 857135363 851220313 291716100 813008907 351609173 736388451 494523989 349526431 441868645 894345481 965102075 304444585 392536243 8346217 26935618 972262000 194915452 671696583 821935936 941901272 699957144 964721634 399440101 105499304 28764225 602760887 342445137 483106949 199255213 227724013 985612160 839651817 392095143 755759445 644551360 403407407 102167934 182170007 622599586 418571740 294071736 976091323 331585261 5612935 597536818 309431243 65343955 503001287 323656791 972232962 97316227 39539139 451531295 776965617 293368192 377513850 423352559 301998142 535253285 53865528 562160494 778093023 863618490 184572829 603394462 758926258 21692515 633246809 601081288 705744058 310736760 888971063 763200323 492476770 640601190 689046603 589123283 812957843 631489303 584706253 236308833 822055222 935808903 226687103 355431318 38955293 165009699 735647123 113911115 37867389 283287007 837757686 424366949 117720641 156065347 155490782 176606174 973008397 587867142 954065852 795105653 143287711 733642485 149738127 750362118 427781230 856279562 190322582 749531092 537193298 399711659 338423792 789064005 704413356 251694507 225152231 396675889 639736615 771840095 272691757 381761530 727578210 749112340 4486753 740841201 160153095 943949603 161537366 788463371 573283854 76462143 75281857 963895360 935391520 142163650 806393413 734134487 840599657 346553088 261273668 411174026 91062429 455855851 73703789 579931574 171319240 191154513 24415860 550057930 467818975 844480258 708745148 721941977 515634837 550579863 486376282 154400776 119137360 266675548 202210275 2041091 625831034 719815234 397273136 695077393 67994722 678949999 245770188 814111017 878575937 141910535 404844736 756964537 920253052 480549993 687047809 892025858 728316790 599209073 484416641 717058300 709758857 227516876 110215788 653148110 509603252 105189436 597945390 821722588 440216372 821653962 813132715 360740810 521477450 454318656 252790806 942189178 384034318 509709882 986904077 284997031 45178135 594900089 812103395 564172580 276553147 762066294 19934300 638766484 703377401 472233852 390054398 71537482 657461233 107209590 17677155 310905138 97497489 285153851 560054285 973195048 23485459 869065031 831220546 380969651 299282358 983385683 993398844 553017331 333859921 563673947 942197204 713567117 923158360 256468099 597701341 284224166 886208151 164428169 136937485 520802153 494554916 401315571 451559274 210417734 600707895 47540604 219377868 915936505 927886869 262817953 303558087 157923421 33714215 36212049 171947049 637746831 908763424 246392652 24160488 263007117 639730767 59660296 309477956 271320578 456877799 953969208 744529904 950123672 489429723 11342513 148536276 848822070 747023478 44068222 603237348 82529174 313836946 642550714 116026429 435041069 535148674 581445544 939893947 297616380 721825028 98762596 953935033 132396181 900002599 615733614 142989514 627329052 332383497 659054620 475612063 203785454 902617668 78767975 188545627 103946848 605378304 293929176 928207585 415448564 473119802 361868384 68130268 3521841 544651818 981047373 820685514 649113577 546759315 734971759 614584976 677630018 812583961 408178521 911409372 798772487 75956933 613999759 995167384 573980964 335642491 771320098 587850600 418420863 692827842 776533462 206978209 51791817 754165027 351811595 79266654 147242593 495948501 76605363 972474554 821321170 746691278 958736976 905355298 582725961 50353220 360505376 154537649 691048131 403375727 729324263 558157709 161406562 968986117 585086450 520629197 359093937 824008211 328428942 102299522 44291535 63656799 863214533 465281351 777939954 81961018 196590091 36656436 445953640 343298800 316126789 550759657 948218944 295207947 234075522 104910387 435698188 888574107 444672220 38038660 492006581 423524482 55012889 133921096 496843547 246144020 414174054 592443100 346081294 493395356 275515463 15451561 678016081 149040428 987593439 484014604 903336285 799321607 813365243 920821660 616503839 859072596 526439751 611773459 567761685 513995451 623977179 717691634 14331764 741934713 312531848 971916925 650078243 310387677 892941790 447863384 916525115 113547930 310668548 167899943 122103018 819056863 629811397 260572798 774894356 765926204 846204615 587018205 266735745 519146274 205808568 947701213 498239641 212723812 110060900 278027244 336213306 567045983 539309262 546911296 91471555 537516266 479943402 852483304 943686967 637844316 654805829 117504681 316488168 85136950 451335045 26611805 326386527 276483109 136917866 173054289 531005712 160335315 881853949 316982250 645486635 849582231 47154793 508016380 643903461 639645205 829016774 235773322 938735659 635688550 721333211 52763721 389642740 112396293 133278258 571470396 369385132 746875687 398652238 200115617 619767001 702351423 440540311 957934888 917087590 437882507 928094065 227399968 786393798 688337379 316921673 680604585 429270281 105215200 443889009 864034863 148305471 756820849 751324954 267497520 928911820 988331722 861613067 644057257 219388267 604178298 378831249 519423434 322139369 340646553 956331816 65230121 321129050 802792915 748884836 637203067 954212390 754509071 335940632 319376617 913882914 506016543 122779114 634305640 96784301 528193264 50971813 571265246 807483663 139238940 940891416 335706230 201437356 67287162 75015686 8951961 961105754 777896402 13276319 369225520 936494852 909323233 260134460 893742779 849051289 147569658 366029914 284605824 356586013 493508988 211814657 219345823 243336741 19290559 945014669 363551823 62489867 974922203 622821455 314818624 923301079 49948051 276574687 508181204 978078711 561498125 795649253 20918205 895521593 116395932 535692994 956762026 898005129 648252925 108602518 988925738 695561606 938002188 96087611 351571621 341221579 217814771 988946030 882645410 785952818 304741506 593976385 780654884 330376049 642608943 776197412 237796662 572320052 377178775 476899215 159755068 822616583 822206860 663209662 31025500 285239550 580874346 850052438 326007058 772416592 863664358 224583476 659379750 538665159 824453964 596992341 326287193 398884847 653330465 34785053 473687708 550367309 535279328 184831088 692716164 114835952 666231987 857489531 861739090 162368409 855350564 27699715 108166447 525301172 718587190 698886295 536947890 25085430 587004748 685332656 906210462 796545281 981729306 716566935 535775044 834624577 60917946 428599784 219820691 512960415 774457318 307876538 566767391 494595178 187012801 597970934 869684391 420300665 932519773 331746919 780128237 892402067 550439854 362843056 44093627 212786430 792697288 630968976 298916526 16623538 477418047 920865723 357016241 269548873 311275433 535516099 493121738 7504456 459448432 751862713 210164438 875945303 817705992 388023030 436235597 835895769 180045293 196061625 14804584 364295712 147190884 10109511 340230351 349219592 854239698 655907988 266795045 935403719 885832319 370077009 881815248 211530216 609373324 238948097 549657322 899885825 504474293 321950911 530008533 406141537 603430611 294432912 586546093 527409075 44744964 622829489 741987595 958611755 835288341 654871780 830702897 231952793 561080441 105388099 906479906 92996642 566936182 656131059 543862422 690065847 26726377 474935871 489490266 835438747 449972504 503500989 594281504 375017851 564572958 689567107 808837166 171315484 937195400 991366798 321255019 874503630 396554983 102376826 798378340 626030249 7096905 817610704 533226490 951316706 689650022 985234235 8865733 593472549 7529479 127290161 336685814 766027032 676351323 803652924 498417513 531788431 336701599 341066936 186105459 934905231 627292547 964066853 706806029 883861883 431362953 700926480 956555668 439463802 786257712 353088349 326232055 827678332 535705870 384839476 897357645 966464959 52263933 824617971 848208730 711539497 872573646 511796108 597608686 131056269 634817815 504755372 752986660 452524430 135617811 995222209 651860597 66236208 815433 564300353 283035784 538252177 946103584 7844851 801552493 846814206 48463715 668637497 908295733 41762633 938172053 115695109 889729385 339007669 316773967 450961813 534034666 893473165 969227534 713767057 750052245 753608187 688066718 567054237 975208535 369256913 442589279 833110459 261917876 34246100 300189913 22125149 415489936 254600268 128946397 130579356 450688343 515026912 365687207 844508351 356433603 372056261 851557917 389497135 278106227 840180110 302580131 531777984 447068196 743210020 453033424 507635947 651796871 197314679 373302471 567388399 576117683 654395994 708613202 110580861 772082724 80259699 409842929 199741596 496015761 812157932 617785172 650103388 683473355 179674662 933654866 79481763 123145084 38079977 502944366 952234886 805452174 835786369 638860559 294948026 725825615 595650040 982202393 637167943 288021355 495257453 926089786 338736577 198228966 238809956 457145899 420611223 840538345 920503141 442397344 199085748 509034266 925274420 29079036 214166245 542863775 706195464 670091054 755923058 614752607 983188499 823289881 991984318 383744925 704527536 460143831 980027531 516020730 479188243 412000781 508321859 868719585 440225488 304697816 739879985 589728122 731950980 148531820 348745761 914070447 600458283 369757095 983257676 67436806 977148597 770829462 519180503 928889904 776643301 938991202 365269507 924566065 176917015 163867380 50131898 686533917 873780642 428806373 513237098 105192616 334631783 248409058 122130690 816453859 721465269 263025431 557559901 854202239 589015980 979755632 446143404 681485114 598288182 9073354 323456582 994371746 720875954 812030042 63410590 997435608 400282090 568157747 222190330 806299501 243767161 592302281 125439846 153479981 579970409 172322514 54075903 976203243 770657487 241479473 635572163 432683608 671574757 606795720 256306044 258522940 890022317 719813985 796196725 249007796 227086995 294700024 934340497 921759836 911492774 956607183 106618047 17880414 23540452 660233309 311520602 788753783 121458584 110173600 548712936 402189315 538951936 145484703 392696471 550210130 253542717 478315391 25346014 787231418 482467993 946870857 216284695 262090627 887547161 206287808 211518267 781980537 450143052 677965195 600587710 103384363 647362812 71782073 860139721 79763616 833164417 56443290 736350626 490428501 890300946 284866184 95428460 750743377 839258835 625355232 698741379 745312625 161760808 496580410 83016810 385333413 834756265 185179447 441135683 880679918 325318621 711382310 895309306 200218570 62335899 460960298 164165299 486891766 672801249 632647519 112549415 549876581 55882014 880549077 547612374 737227932 453404709 322618041 930928296 832076455 741506283 200746611 373922688 205306550 918169117 328095411 399366909 772030321 459235311 689225431 380554478 689475660 487500776 163896074 808438570 964771278 855248513 586582323 133110400 963304153 558222969 771913058 737148059 753583622 143787018 865815233 483400158 435459627 270223798 95111064 50788088 487710129 478357266 326402042 918891577 355168744 982581812 652758902 621510653 950544494 738936043 455777877 487614304 819790010 837869783 821087634 42667290 267088722 293486223 583433863 806174304 384833719 506575659 966284694 744815929 436923930 341851170 530967796 522371325 90657823 83743788 653818038 951277784 539555580 390195257 750221779 869009958 741524821 668252306 175676385 10600470 840311147 754237894 359491287 533201581 492665651 795837881 858847149 998179019 923503039 274966072 354645891 648589176 208447696 2773492 118843651 316847968 480582483 623414709 958432256 615022602 126133773 585404267 968324576 523063513 506059359 375207226 840228287 437009967 204636905 427555104 456351513 302631435 230009844 394565994 238207411 483688836 555651142 493739925 528624205 615918107 811323137 330556466 19338260 861280399 523220175 82175195 849387459 916667875 288493951 126441652 181241323 159430928 205080715 530661358 489397457 546927444 213399983 477681666 954646083 942354155 229883558 67604735 66057121 730366701 365009946 510508895 500740827 555274484 853794201 592183368 759951454 4598561 252044980 669529215 493418323 797150536 318336414 91328137 548435317 752657276 612789283 311489130 710156374 139232539 98856911 552436488 148465156 865481591 425269391 95872241 286760550 212084232 562251889 531868850 117165667 286039026 883565745 932622369 155131867 141064969 354429437 634791032 848802473 674117122 683333230 470560181 199863938 152576756 289023518 729251814 117989241 663614047 923378871 41865366 87884772 119964649 286426279 1659455 52792525 79682487 310207251 51047696 288844060 471142816 683306206 874810006 302483875 238409029 346814656 224766568 180343353 780629438 130482956 670433557 276145184 287837311 853453884 533398189 186452685 360180779 308991202 607635003 670333365 202970245 937247742 284070498 602551395 712795189 187588252 990911402 62294906 462128299 185004357 591196649 961026657 145138974 654487173 253520968 657206543 632311235 479962148 244212541 866795738 657274512 462293157 534923573 359175690 403518661 400834159 773114097 335468229 570423629 376902197 196392351 744869247 106073686 971645493 993367970 174089554 508310513 494409717 196921008 624687463 301287326 282865916 268919072 481516838 876180057 404789313 847851349 57743123 86088203 541048431 420518473 760660907 213928133 35814492 625343587 451659994 386417290 151345344 288125853 279789658 828886792 177936607 578410414 338879870 432335209 120064028 496249196 103065188 287209101 761353182 583650375 208952346 41342819 654292755 816295611 993224242 887329663 588263102 645758825 7996837 519589264 381280695 519429298 162414278 132463756 303273782 780472677 204010225 710012664 404289680 455548861 246430832 773191019 703431519 600699702 307724669 282735542 403837768 952168859 348460076 694417190 536960833 806960478 973389582 861037187 14754070 965867729 730840753 124249339 933629066 720067442 380341268 555437078 666499933 149627798 181269312 442594773 420782134 890033307 258242470 409787915 551404599 373462811 834434057 767934566 5517833 129036226 422394160 325712380 929703971 918923887 861860278 814601434 875569309 79642540 248642704 754819821 963365130 275766261 89618888 513288432 630615244 697776478 279668694 383735854 596245732 115787477 598433951 265915387 264448549 561798311 145218607 875067990 890372435 395391419 320408505 808426890 996189353 241614268 94025121 779076191 24263278 795201218 953423509 16056635 950591017 370159651 812580665 740973173 489297713 549115448 244552016 931327343 123235590 767557032 347615888 102189765 161535478 104385101 548457865 325842364 522427212 930540795 780831711 202594813 470104428 232646961 410772960 41575891 609592513 831290477 253438760 265544393 790653464 792100132 242165962 555482473 629550762 635454329 815310591 75839965 879807338 859227821 382275441 746458400 617014064 972471612 308779269 635231895 347902008 880806514 315675707 548265281 160315748 467706072 946031188 136132904 769708591 405956219 610722181 817134953 720019711 744557581 823158252 487093794 38445966 136463334 97304815 609001481 568143555 709850730 552693620 382468289 777070023 928622397 901503640 696229323 278635517 330615341 696034260 466188786 344693453 265536771 163561681 700263346 247898389 555629509 708076401 142415919 445470733 787972451 326536541 869312025 881439311 772088632 80793712 527896431 610261802 323845723 227411568 714383005 499581626 605838455 297295703 529285512 993616895 413178313 525817772 165341740 845192556 777122709 117704202 674060473 416051887 205471864 121431799 594849329 702759322 29291287 295396819 481316875 530182698 285806185 406667366 194737471 518307761 783586157 955274664 273514081 151199119 463023296 419239496 33345891 427880158 7853106 884033275 276037369 931723562 44184473 619718116 562661692 785829397 294252724 498423057 658480082 552393284 712563498 50245313 975987380 485836394 883966156 870434908 27468060 122284031 700791397 65429028 218928157 467113582 742984178 300367515 399512304 744004715 646586590 152650557 239815628 756123667 588639566 648449690 66678255 335198116 499233196 695347026 315878352 212911154 286778107 182285561 40869670 661083391 275895787 398678214 428652086 475794735 45405065 879271469 290205677 453129970 48797325 320222668 970762028 687862343 51251762 457825361 929139570 16158562 47818881 257683384 159944634 966670178 201629408 527670779 634155656 837622950 645076434 237424113 889016500 742928087 702247070 561850045 471979745 731085934 201580310 504157979 688212552 229751598 390471458 454665536 250383523 171203484 957467816 302631126 185858213 864282310 82218536 955172976 731561999 544305807 412111951 428227538 752138697 400670756 12571834 797726745 471254822 340890962 467437735 424610027 857912281 234040706 612785390 506736438 209469653 428267968 412265559 164536086 641820613 45174951 531514294 857350593 314967 216042980 994993198 781907868 568395207 828419118 997909069 720162454 899472581 78674686 81607145 414307242 558155727 804164934 105778187 81327805 674411577 367120321 307928528 250773583 976090715 282085431 869039191 127372202 455536759 630787203 637224875 859441932 322196360 318439474 162735597 476814654 994307519 457114996 853757838 746520025 351824751 491166346 979817225 609244113 785923968 579800328 23940617 418001282 48800908 314647115 110659879 516232173 40544928 624493901 251380169 931696886 292033344 306973760 797311661 274500802 131767678 671531320 966559099 835709399 997705477 624291910 148924436 951263075 388790243 395191324 53726323 969197805 894349768 82087349 534788265 148761448 207541519 25566960 467471794 960471016 753260177 865859171 118942758 666331332 900855308 750938445 249060233 861764423 760197247 144639932 240516192 402706766 782749940 770488098 500590919 458906082 946664888 602800043 922978545 114312149 500228594 150129868 955258918 269593810 476165002 719496649 648295337 431939863 450173079 951918903 617500676 16921508 605758523 162023371 607957207 481266375 128580305 448984974 434466131 500407793 586888321 555469639 258307467 125548043 472982497 46874886 659058433 102829179 218904919 586245204 297228983 214897434 700061902 997599964 872899765 479437868 124181395 729688777 292068893 370272288 576672625 117754853 968488367 729973195 422731279 21311035 893833272 367001380 696427052 742999522 896916051 950613042 465721367 923873826 800153364 539190920 83369941 832158178 566317804 891365157 550122755 391062684 429984411 269390464 376316344 528695934 207381861 282826416 210783301 653951123 354129316 375338373 557611226 235450051 522448735 841318063 908919557 965572578 664919182 613972391 459156158 659291030 377838571 396357472 315219460 969500434 990581590 956639032 526922847 874872022 846874624 385554804 179824698 565585968 191484225 140206299 519003450 52836051 484743750 307129726 215680981 467418170 672835499 560789584 375469219 325359207 809513535 950555799 409907721 744130458 871205995 455911817 811366048 44207749 587981865 360625394 831255118 740470776 903571863 177418978 852191742 777423509 119476506 368546906 832792605 291473339 26442074 317285082 236537392 21460033 425931128 950201343 858587513 778816673 54671762 255933663 921861973 197042796 86963371 21986336 330766350 603912366 25770593 47566009 783346395 924608414 806360919 349473369 202113020 505926334 336750825 820106764 365779158 874736402 905112852 892417641 471940385 929829214 167222076 347262046 656469195 798068435 878746105 974625803 743929615 351804395 785262501 282783951 581225264 219758400 756901425 637445511 864293111 250757742 867019584 791313226 248781698 42736777 838883948 91046024 650050148 817599175 517460015 114378845 817964216 866372762 856125915 565849377 349376621 639733039 256169168 435870976 876076277 459946931 218270268 827924191 981374390 905470192 802700653 510901174 727650922 39358028 187849141 230985326 479875115 17173257 273640527 258070568 664363484 4965353 591611806 811177076 106037506 574189075 815541165 402710913 25369277 490822249 901007815 47557345 660904568 58812146 511026287 341246344 340212605 660117338 515581442 24986056 546848400 499778960 145171405 335879067 920424482 952942355 388334257 910183876 512083250 203094130 979067635 461254916 945711994 744443960 920874910 669413597 457865845 259909337 118217973 561356627 730772281 961531737 22750934 249343081 278017777 650468415 741536287 427544031 851644263 632660905 917021206 707967706 752587745 657458487 52490676 196563292 661153796 152186759 198681589 252735119 51953512 956921803 477507751 638795583 969006406 194565878 587739795 30877865 612641052 422487565 825777236 87649561 482424889 772643337 931920512 898753124 6613289 11858226 260801736 890653567 343043241 853008992 279665569 681732813 475640456 719261964 984189800 368677920 856067573 272685086 115335149 345334430 461646950 665033792 579565809 488818781 838197376 409176547 551626820 686398462 554143706 920939258 75307657 185551394 537609934 104999181 939338100 301528498 652984714 481881017 437360155 40439339 683770517 24173886 764815707 88512976 476822084 443722362 679828791 108585171 652744811 802216476 612049697 221655346 635884023 626586719 286501557 847575331 272666233 307323419 518477453 378717876 844453595 754662108 893964473 440857314 824820935 178891704 749990724 47603991 125347886 465030565 879009811 309304792 891614420 953685104 879036009 273533140 87899766 294896596 76940832 308523466 201894727 131922064 671051064 545105535 574208789 642598631 139793527 116200238 387488457 479365019 735561337 240094915 9242691 153890624 358115932 701938099 49285380 90974138 180747165 693023824 597797346 517582549 72945001 255933301 564184703 670129230 949038280 236073773 164897209 146814079 99340149 863298463 497273864 493798117 935752600 958881072 418975872 576523546 681017492 433272291 731475209 398526712 292888982 620442891 465552269 715675425 829063251 873581188 91636947 686880739 60633201 21149497 682661113 589527922 930053012 752789833 553895064 436071352 285141125 494136258 107483428 864408008 631119943 97479895 117828274 343689393 43470959 774416971 528838451 87118979 262398047 513791023 719770669 59323825 379116091 270034073 693995800 674540255 472239773 722667907 723805961 551072659 578596038 4536554 924367408 928706366 567155863 833988441 109986462 846454931 310585922 865040247 105742886 493081909 473806467 469193349 155431805 877522519 378277977 55471652 991982386 200338823 915759128 707396398 450207163 821428949 616769841 752876658 746611537 12939677 562883099 681207576 480655253 111219385 10755684 953388474 812157777 561643611 875154865 873638507 57292063 746193046 89910446 867380619 862308463 184363034 710925085 199787199 124183832 326376441 126988489 931506323 924146401 181189102 660496967 993616552 108426453 318428711 895889691 419804344 994958116 601855870 57953669 542046601 97550107 921582923 971984276 22403016 595294238 756335661 376940433 463444023 266977084 535234223 154126313 628642438 636774329 697933085 195774424 201557751 429876867 774741026 554743621 919282492 409529931 741751710 676963072 299072671 240918234 399942591 697647409 238936502 158208035 358974876 975662409 183574232 390737545 245162626 511613291 590340319 646023252 409674416 929042056 206488327 329260604 529010620 546378447 745095992 427087051 28942381 722901870 246754981 686663033 376745137 779328717 19359820 936014547 787100688 70045881 526667002 343913798 372137034 362540067 722191358 752693567 48575901 461478284 732219404 205491858 728716237 348698093 883309081 163548604 903693721 99751595 669808480 837302606 563647742 521621218 267429503 658113797 651269351 540187784 107892699 203028471 201783243 588657125 711501268 968782350 711036577 65847692 519690452 587245495 445811904 35708076 837491621 246118754 765671820 416850798 100723351 607640493 426546181 650269576 318005622 627250973 889279170 235200910 192127415 127149377 600279025 285943279 335445105 461611028 219310536 227684412 799316341 4652451 842922209 905793468 366249971 308164646 239864362 487821784 787657144 550984590 46605480 744045074 495738432 95473483 398792717 751004162 827024042 907915920 256326852 283734396 823651836 738750237 776135511 239646432 734796997 43373770 461517494 930108420 76644257 421144621 610389836 764495781 199462887 124181553 842210876 803427347 605374310 551924121 751461438 805079361 112638296 629625647 687169099 72267890 16768505 291222143 461792011 237033298 424973265 994437510 750226388 811243400 236733884 352583924 513413734 566906936 702031919 315220514 748222242 698722425 442426079 315320746 556280664 746628546 388123448 884272859 793376285 712949799 15046646 431452003 936590935 221372268 969653231 22954244 343545493 32432263 187437289 204445418 573288207 595714409 940579576 541912912 256894233 411330976 788609160 82477470 324732017 492936599 733910303 820344289 345886211 280395403 880976631 631283136 667944452 218911270 529045766 918924421 576533041 930767520 965549751 941938183 428581728 627146238 303431713 197779857 389541412 789483483 931580871 515653529 790204196 676386159 241442704 555432271 694293032 895953765 808630552 64092469 287688763 426496560 937557910 8126112 234033877 418945614 569286526 919160056 120036726 491895949 5830247 191303599 608175832 555423326 434015281 603856459 448233728 279477734 845498918 14950293 493260585 3508292 500349657 760510402 139527337 855295869 124311245 518517883 818308141 855395552 643357135 23475508 194121849 984207452 648964295 599419112 742934129 782063211 137918249 313484907 425962205 914953259 967211826 360544566 191455954 492631739 151578016 415579149 192866315 727874203 922981938 938440771 635439818 739982309 242340816 909259038 549797171 184141169 48212196 689900500 185015305 271514405 270441891 356563072 865157226 363906655 195136613 888828968 456611883 859164465 897315581 586532098 295476622 51053123 970305793 472805653 878297056 1964052 181951070 6157803 564221554 813982294 713392417 902351299 731722865 993334313 798671210 810223346 100047631 539273893 869649410 578788760 384837912 697612993 768009923 738109759 399454440 109339061 838983166 794143505 846123972 618075444 288945429 445724649 469802393 442340484 198712838 99248257 915895748 414634653 254697238 822950373 107620741 789669197 40353547 32233915 149757658 676683275 367612342 568676141 725235991 581280606 896814226 279103519 308883018 736805865 189003228 735792857 113702999 307254437 15277735 716216819 612109269 762128348 556455107 529514027 679372122 380233105 544007399 339647077 416143145 671928052 341388845 825274328 705911910 880098141 19735801 527393283 849460877 845597951 373163112 761903966 645024489 78613459 986584800 361935088 304356134 298039853 73342752 365985830 683487232 549685594 367050846 684589562 788505400 739988928 338669529 46813137 761735152 863377404 589926824 374778653 243322292 947845582 324944731 687190703 210586951 34467790 479300317 984315779 98527019 971899619 397047906 993933700 488079697 899347333 982728868 652973264 963514087 662067952 301894387 628179656 580092462 437310645 184439887 257624090 904615237 857997777 813356109 104976639 876310565 180363816 12748785 233910683 970347940 91017788 912123322 15968258 770295304 709980161 257998984 238744139 761486543 84444416 168674472 259462634 935160150 905576345 223485446 514774168 968129609 544368833 555599961 52780163 767556455 439850105 531730173 248752734 119174280 335482579 16051696 776233972 204599220 34872258 422102490 967203812 723927805 306163789 679863812 716983040 201284295 592368670 328211684 370640998 277052725 828657992 430662016 562107835 788637683 808169646 799854368 884022652 664042847 174642269 887802947 132309681 844409674 920435191 410630883 339775954 771411741 163401381 54560724 852683606 939168133 920684689 382635131 855539970 965348310 830081981 789258830 120527743 221148956 733129521 835433235 984544052 367072244 830155151 154298409 212312054 613028235 903105621 697438788 379504776 313084146 916925621 686402048 16236399 401410458 558291013 129499061 183231970 874722743 933344526 175004890 184817008 869124617 490424675 167823293 14021923 759317923 993514891 423728242 157331331 921406316 541861170 760449195 368669228 358678759 942039532 791388471 136856525 975159027 915070481 892054970 617965496 439658253 920819029 564379860 637445006 739475810 547625340 816022575 727966211 918359334 54615263 382542987 714797144 805049783 359166827 665358713 876607132 900000618 233776498 576816866 754777164 75106263 934707926 504080449 209501567 703107187 63249577 120907919 241983987 722663134 190196641 801272581 45465545 952418821 71171326 502811901 831584035 645781420 207329042 360298851 203999237 977454673 568087126 189058806 575146728 465906591 87697363 407968821 414919396 307107403 629027892 504020315 627911085 821677583 722564377 461628691 411463310 355989528 880561098 318033802 671725802 353451919 520817647 858268709 870556582 842237553 703374365 471872366 427619610 790948360 295204896 397478903 538397334 916173353 56036229 902489631 132714775 171288557 500982594 611135320 980706756 295817888 14186906 757811757 254903663 965177340 820956547 240546691 656033539 286246218 188225609 704156416 97763858 875867527 296443862 223247623 576675049 831668505 376573240 320110593 507218517 485808569 369974282 187993666 627292277 806869106 619450653 849910489 334822622 75808053 360977217 787403530 19730026 933407849 810851856 317418841 780700555 900617638 324305349 899807425 959312232 662089742 91834323 108987649 313134652 301044569 165318433 825201806 731250815 37675072 214607871 602389410 98315606 731177876 579450378 888896954 799431467 493084670 909517781 79727864 444151574 898902204 215139219 279083076 757062039 980872545 360184742 406873764 93616703 995449407 187983929 305663725 721372085 33968557 229591170 142192712 266676293 69524060 824913838 305937792 796674511 757917957 11586686 665646595 856743807 631651630 188036617 696842369 261457264 827792353 611013665 900065247 191855308 796632433 377734420 632652177 367828898 133778925 863709982 825714891 527634363 356630780 406830824 854976858 20047351 440249117 712873847 200745351 856112962 295217312 113338460 927069935 800186514 948225117 132317421 42770183 105981444 574209050 497467466 480967006 492030772 154080648 837901634 508932973 259422277 336527544 977320157 949271279 805303574 587362610 396074949 789704815 899879113 360077447 720482546 974013102 215538993 740480220 923928606 947159423 721290830 367771531 313668154 47562643 230810747 572210517 660252643 308431453 596663424 728576280 425863578 808919497 34914485 791643387 153182799 82402498 386695905 198420840 310679382 302523541 937018564 996285216 609574386 447736927 371518441 180138000 80863936 769886630 479047090 480973812 282992746 137396223 975903294 507652277 328070080 329542131 907100635 727161423 503726555 726528820 830727472 259010793 928692959 418161901 544569981 111262784 444396908 660486480 538834758 193755179 137824270 547065622 381626293 280454304 858661895 905389592 29086203 890297590 195151325 320402197 28398998 466920912 281859340 944259454 853499925 325007242 731052037 557485663 954373552 493415993 524089233 71230659 671867116 325723813 618810880 271708097 425262016 151522395 356027078 793493540 991265094 90745739 125589637 155551367 645432470 110485852 554189551 133474375 541463236 407515239 616893121 841314197 331056469 882303858 520448926 190054823 558281140 899963974 670586957 74075693 689745653 136085824 946985199 337632472 196262813 972549067 248851193 59737628 288154936 379809843 631763493 887408036 25143834 528366124 74931529 192768477 281297818 837742741 166897676 793303322 672303748 308845553 501059883 369380388 100462409 250611682 62200044 679146694 38612589 728415766 104260450 500337225 478670328 468564188 909863217 877322250 673652380 262010727 764552836 832191930 301188884 122945446 770652822 23870148 697057178 516547768 989052706 187001286 505575123 740823792 324041319 473078605 645201695 411287992 642435808 449829644 988031235 541133466 865166353 71838333 917901788 592808321 530136902 300664986 885348789 74492635 186236909 794123881 880060952 498520581 748308639 456680388 390112119 1501289 880758148 63962495 229544311 43685413 994377228 251120032 563628690 392224839 966747954 310105684 937202423 209899789 217597118 985041471 751370036 301985588 534706659 925817029 979216595 965839338 301726094 259220169 496865566 421765121 409611736 782514264 545089194 113894318 526442051 296769147 990098236 801777975 275151591 975442635 856052590 466112563 895205215 662360944 672601109 923727551 508246311 126194529 207097823 906585199 235847299 739232259 942013579 5217591 105195058 64877148 103404342 967000216 186919290 795674447 691969332 314859552 893033227 283100692 355589580 982219319 62897159 461855469 620145148 170086531 944702389 619458077 967246396 429635945 584261906 242613107 346597095 153860187 940040628 844123319 261365034 554973898 928160402 863214807 168576812 12969031 127222473 954793513 891894024 216138421 316282025 518617319 722405672 608703192 76271102 77054860 562109791 463608312 461184579 341941025 900705420 456884863 333644543 887509811 51745761 162674344 552415843 806896371 169516771 597802086 990874079 425740201 323616975 42899738 815668179 126775515 17165912 539083574 414578236 333992589 420830893 28632120 697183260 435598883 349214816 970839174 384097006 317031936 364587322 818182095 800779407 629086764 956707722 252423043 134460566 682469429 428759380 461695999 421171055 608903844 937329734 82631400 913492296 429155192 793457325 996878389 135138445 410607917 311627279 830627743 36057687 57067222 241765424 22675889 99970098 576831912 932593389 268533736 633049294 870843170 376254524 308927534 505994143 26789043 833304570 47750686 761060976 107097075 791135603 895154174 445246988 128333354 691576781 473919158 669065883 461571760 255416606 983084823 661653857 855784633 881195195 137301151 265041444 555640318 764312265 677138002 332888500 604822944 320811753 730843902 16135442 455546618 126264662 428666329 24733128 91093072 854499504 776572664 823811691 53911809 371063363 909851675 499448538 726381523 393862484 583814368 118485873 944718675 69142577 78244312 84227425 775517780 475934405 634189189 426859751 748700555 284710603 74556919 292893661 324546452 437490540 667923319 932912786 36791945 681463853 315752772 224278372 678832653 17588681 775979066 744285912 640980318 886867708 195787223 647404198 318734154 733642706 733348734 493206232 901318558 895843262 741469900 961979165 657434132 128772650 718854573 50908479 379895305 319700675 98273735 646398848 873154703 134113753 203842114 729072467 604064225 429892148 372490667 942931284 469017019 17322657 271555152 732412720 241119714 554768586 188327354 157812560 677080673 30994923 948179620 742422021 833788033 220557618 299808457 935859089 364163409 308852550 158213140 949913925 576359934 142644306 389376884 870461033 412452559 826387340 61102537 654503808 943582009 111578061 743922690 86599706 346824520 151841526 571174279 847719766 525902987 614148483 433754911 849138147 954114467 327198946 893468478 628146495 187323533 555532861 373147062 520141125 326503396 741173067 600728001 220106958 669435248 611806815 26733120 232183793 155223109 93241749 128522027 998059856 991829315 56713495 813891310 439534542 478763376 738127571 510374100 49196117 345281088 362838985 836458439 92510950 980836302 828445712 873987739 385524131 512187555 84997676 812990095 577365916 408988700 615091451 740328063 610971607 475441135 940972024 15984002 176614286 300335279 21148545 17017558 795835921 745805629 321597923 267067548 908792048 32684587 125388992 939487889 577221945 198967477 874129626 783005045 665073557 702809257 586219643 486024785 112689604 766139182 288576378 31151169 104628840 368120952 753047513 521572772 490039428 773194515 911021111 766705581 529306332 45349600 199320210 730099608 439924561 503959644 522524748 322128779 309241655 973571398 665583346 408278848 966806231 84934426 147086359 443193826 484667396 872986325 957794811 945303856 667129208 727263505 608170795 536040262 505573470 352997939 353615992 537518114 717720962 594126501 742655401 574113352 968223185 590382362 314987497 229622708 652361932 969678909 240154144 929302259 486114423 723158857 231846705 445221911 24931467 716213599 519273189 100926504 665232955 64620137 441159284 524080358 393567544 789318413 49316197 644335888 857139593 919765620 152844198 16778959 133964788 838725754 490762969 512048873 321917702 660488097 920752153 942202533 36597465 102707803 921309091 724673713 768780917 408858596 396840896 280876153 84375019 372260631 330259135 90967429 814734715 383288825 301111057 475710898 335965713 61852414 223839629 362358557 561976013 581227723 390926513 349840616 349539719 992938094 556590550 596001593 805702118 213410868 76840361 268158227 306154098 17341240 665215255 550696661 139494073 368377375 578793257 99797442 148316734 19575619 458064264 539112055 995417360 961961523 644967827 947521536 688673933 668618061 832098307 652343242 307429802 873485912 685213668 603041444 81795414 881496469 353374406 579807069 592129275 552504487 601509231 514880978 547478351 378756908 344155893 300646479 841849974 837585605 270029638 888997403 172005793 301819894 267907010 280335609 123569536 164842725 423826498 710794813 133937953 314037825 780064449 622270480 527162697 931607141 213139865 823479411 733213248 592008503 960805198 125415365 103662638 994721859 5590643 269546586 795840375 474986493 837548180 958485176 254980574 388028148 689688457 122758627 56635168 826916798 116602118 205016340 960146504 461011221 79137338 707707862 354002916 373732413 230305927 895570713 460967251 418403881 973824036 235297755 161074112 251949583 290868277 53644928 18582440 210969837 184982419 698537047 773033801 339519198 982424305 807124077 285176264 758622556 15511213 894636730 226520566 836588400 904696041 565815779 231297108 611227276 336083370 554993296 530359212 324367065 437668795 569362028 878570676 191290627 65350547 558044170 49462266 650615219 563422422 207214306 893453134 413908526 905482136 643742518 31613763 159999474 674888000 754518586 82404104 764723972 38230333 194696275 67048371 559633926 567164842 786884593 730175091 457094106 538719441 227442958 455845843 83886427 976707081 944977070 525321142 512052121 283238437 938214126 1129707 745174169 466623156 790699263 838846934 518908214 215155910 782587984 539846575 400309208 124992981 228139519 239609552 75432740 965626967 617860116 457832872 160645412 515194601 165075536 934350962 629709988 150817727 592711599 645379415 553693480 525633443 703250410 314239469 605490501 277817929 160335374 361904475 261567570 343426698 971277426 147560374 546541252 872058827 953267493 194897741 95297713 224271064 988185562 264754277 924381637 266829570 267120291 744165564 214905852 643598572 110664809 642244233 841831165 114679794 538578176 521874365 417624566 705515180 764566286 617408179 374496311 371973517 463229180 656996922 381914940 702186044 264703688 136838065 944742957 370357624 138156513 778277576 942553265 7070186 400349340 109616664 403528214 925652502 520277068 601027518 121233252 382937777 819647965 565432567 568589827 707498074 543902291 39189826 439530739 826102643 452416790 616617349 759711644 450171253 869051972 854679515 996344475 436157111 3600061 889178623 683693717 660688712 408779203 392479720 607099744 586228757 874354199 561528777 636304419 415801073 994867521 82690425 720620934 934589807 9835136 873048418 417902686 593890718 185362144 503078188 672605497 340445289 214307112 643592618 106665241 424021044 830936483 634839045 172077903 453794531 417817911 78040119 346213434 585220378 664479505 783673441 534411586 929020743 789658250 868716912 158429070 684480905 479286295 117997791 640904971 911239991 647058283 91200334 220096682 832159311 235880138 888150798 543718601 178253916 926271428 231728835 9695612 660036519 642949080 202916560 260317943 144136886 502238728 786128102 348128456 853900062 715859518 275651339 601701684 72015654 350134261 816818731 846350158 545257104 930340723 300569758 552232353 289749962 882695949 338439784 133581394 317453061 406378938 646950086 650959653 322480445 274747803 392358800 332873114 744369004 532111706 734499406 43672163 169628438 850538133 363575632 593516974 3994854 284485072 255945705 144234974 649589373 160984408 324399158 783271443 403287575 630789328 119767238 471372152 59636579 667695985 677437776 912606775 641839031 344378966 620682790 954183080 844290472 335319351 174252806 982223100 765980843 501502689 177373665 919395616 936291879 833359894 375704417 581478681 545202077 942886826 971485480 729726583 424269881 370207952 67842237 389277652 280252440 849301005 40900858 458657739 934489342 183880353 424460376 311398418 670941914 383452282 50448653 628008819 831610217 711535226 21346584 84220866 683271304 596669051 692637562 743720317 598742679 222451558 734371189 242432320 6221240 7100292 880229297 210957875 82096762 961533302 97935237 514406603 497173963 131098184 175542880 43415047 361076730 292923413 994052237 13901497 496179220 442430767 154541409 746173457 316255698 68759528 70562647 516256060 986575964 985915561 36587769 888345512 343877921 34453708 101718107 589407162 271291357 404562992 988406352 482512222 342267045 620472521 566554780 841849948 761886291 47915536 990453545 898644965 367896180 492923702 288225103 500790734 51779289 678386542 932026952 527983289 776094093 927738547 224042130 722531432 295708162 253021561 983498979 593710229 594494780 977428518 704844986 497215268 353136711 255728074 836567451 829687210 685778888 139569781 22971137 355361429 683602131 196621622 561167070 235250949 199289623 983505037 210105305 836074578 893007974 173428497 445420981 262778997 782468039 143346906 661464275 994423583 159739468 53480138 429199224 90924729 173163227 856696159 763638008 762223441 393643608 168045950 687549263 420624584 616312262 394082167 202348208 218823210 609798031 232901677 47705174 764683785 520195798 220635872 681594416 443928491 577539168 429234930 565870873 90617844 940972043 284111361 804531984 225860999 937840737 937332997 202380790 690567904 687584801 593695643 945648672 868385470 245396394 723764381 913149212 848593378 888785020 242851405 504516464 282740648 106446430 584840619 987930287 134051166 543281660 373691166 450081260 89888605 754013266 670397093 808211509 134629946 865436376 396029895 734458874 954307239 221291709 201166066 506665286 133152261 596703036 874205991 912465415 849825800 424034168 891677513 245770137 972357741 540679859 8820370 416739765 792937689 283295643 312068795 978958432 303864490 355204257 275951300 261215004 635248171 287059889 876168939 143519568 490315571 823062020 888080752 316911663 170184177 877082986 328046182 672251415 12941732 275882026 452376774 394592043 90417493 541145228 398802123 845670518 126943307 49076294 710873078 810223544 568649416 214179325 959656818 401337170 939153098 910060379 967517075 836553437 731601988 893564747 465383031 137104704 225993919 569231557 546821230 897652480 760953401 616685469 148636648 569473563 844989162 561515098 405115056 603478902 32172153 827733394 763400868 238430552 355316935 598675610 486667237 754072479 340584297 808648410 867555483 52883294 324137329 242063525 525784995 108396420 513683715 662178248 15073975 988145572 815275481 394811772 22819659 493759396 113944819 731135483 409348593 938895210 82967039 401615585 220267271 706637906 810764986 44789209 778936793 528714217 307412097 234727266 582061934 767380233 665218895 544010706 416240897 600109856 186509334 402324776 667586783 694427993 310542027 961530586 259651502 461168349 340717479 403530311 183797490 60833571 83150010 383044560 74424589 796616169 559823464 713544141 918427372 442218108 295429572 8197657 668688943 35199933 148956467 336725707 258342411 339382471 613325059 420809908 441885209 613111334 157161484 891783859 863497721 101864505 71101329 206834504 703983088 86850253 256776187 848944183 973980175 326114069 732086661 710151752 123624460 262773249 418940297 195032344 206595980 664682060 969676775 39625060 136229152 401874209 443201500 391949233 666654829 101549333 935630919 263058413 815257183 121781837 213098124 644394585 570065617 506092460 140743799 579500513 604564099 244501383 873727952 79041447 118495090 805831289 683562187 47789677 860318979 698656912 384240995 622333032 146554054 709223730 398383460 390034492 907390376 391298811 828714191 383596061 584278202 264633871 608438473 20991397 954155171 163969904 280274621 394532431 402429079 781604999 515521316 971077815 9133773 744000640 686332964 323151250 896940726 858753395 23638174 849938950 665139884 700695626 52744647 482210502 650772401 96225897 863992666 681531732 128310208 87493530 941598875 451707187 809870325 203413081 4368133 763582509 122585231 757297328 714520499 425088097 182476749 214785944 436923761 671886438 319840691 410820040 863640292 262571514 548825642 684672517 177598203 322732136 238321067 129675121 278578304 430212976 417895826 750734417 867390635 474722484 432786911 313551721 810124968 966164647 138605173 651724376 8291905 951070490 140392959 138066082 253041484 832537853 819873 270181153 128418780 577728578 600809404 197396458 537704816 608463718 885592047 552969558 945284237 820955406 422649570 431338050 217066033 771350419 841624448 460326319 913646044 320906924 499244337 224601441 556034217 637500590 799956337 539000305 350473429 657723645 199268673 890334959 320637400 458117611 783921577 615444139 516486108 100541154 49775277 495349248 711697696 760181725 727143350 332176762 337611167 941288488 487331743 834779850 252983653 8260329 670576154 983967201 429229435 144523915 779094267 820300140 960796131 217781758 907497148 536529138 948778527 808065175 802494123 204727617 332864006 496157393 465000215 502915776 740529173 992989968 538245226 177859069 809071666 69414528 489901377 146077353 410075772 988975884 343784307 152565679 48379999 877784801 636009091 38210921 125014675 940210705 753103235 655689975 653801500 926400485 498822631 281968402 905884270 44232497 533166418 879713143 517414070 843621165 626745795 277687929 120386348 916067072 979743397 840472149 665001210 402465170 307208372 628198357 451745319 396494562 455405880 518798256 217555767 723636701 525860160 528339178 730951604 621615925 935439781 283916155 613520456 385184029 127128058 855491882 177601925 780161242 880340560 600678001 147948671 417987935 141826149 210475696 740105817 99499419 242223478 479588426 468775645 338976845 138629585 167010151 948487103 164786775 895549679 631729277 697847262 780580035 595483875 419095627 231973007 978013432 778864507 422492588 374751330 450834324 637196893 26350690 861003348 102159568 648211316 244897861 4760356 836409336 472882931 678611892 11169806 378556225 229030445 947238449 589208116 897912599 455929455 764489340 277420880 53528005 197088217 881368863 203067066 711438575 577713273 195152740 859411326 299507596 848692747 608904991 93506239 369707806 281353111 163953963 13332041 145258509 177531321 275248783 835680375 193520853 106527784 561513533 592676618 74759570 445809197 437131408 698663526 674038352 57692469 320150346 782240738 440582081 643524034 539366349 464463664 142688 638256391 156602631 670486081 446250538 595256118 243833328 820120451 480447196 66449533 866861260 767061797 381010030 608618379 984128639 172660771 554496469 325009687 465155819 73398152 73078175 391529852 38884792 925957418 707663413 256732703 649146678 820099146 82431208 22180177 314415337 378876159 269299650 974710239 346837917 65541409 814352480 200394780 616580 704035025 816835344 257192496 624827037 729208202 661818705 778125508 997691723 176964333 653098353 451481317 731020938 702281354 747122476 872122762 568437920 445603822 550613963 8754639 65884676 141071813 795170145 50340201 87553644 220689643 737899818 106327710 463557618 348185467 650218500 133389599 452539213 339899800 198080732 80456734 965661960 358058291 825760319 187225213 443626298 755287700 273026411 858961848 92498568 363344446 125236001 290339891 376078248 182688882 43226526 19264102 490305381 114835010 481648258 433845131 58394096 16933540 625207815 586272961 466856707 166592612 645849980 218998560 342275229 578995987 644179322 97736501 431030962 788008571 309757258 440183769 401874733 131863304 598559567 766669602 393952917 804042281 872218616 289990288 995322811 371965343 776322969 37216127 592124867 616710219 985870413 627679305 56577829 21608166 602750905 121116344 894630826 736481223 204001343 270273945 993950030 213636769 942692216 111455318 820528521 125467879 756598768 845568438 38468562 484513789 326492767 353529782 591285892 380349946 387733945 429784909 579466044 515401357 274896610 522908856 865113199 376841519 633708876 126244832 6947984 818501136 394418119 845382710 814813121 671547631 350143439 638008780 67890733 846631099 884165261 462434080 554071051 826747551 424742055 316798487 110622291 295672707 888998098 819303638 490500749 339628660 68933674 92560913 374113678 724757159 672741379 830221821 661324485 866883275 63850374 832005421 52345037 672096342 522421149 606227400 462421761 429392973 332356050 754651156 28476404 311099135 100117659 31102753 989863631 58515279 975085980 741409874 379470353 138089416 335687497 567758594 703311711 808938310 708442991 786870243 831215373 697896223 748971431 745750944 633231405 319319076 296979009 274467261 116306867 669151227 763406886 639045133 974801714 269213028 378796662 136886009 659115393 874825430 438687716 813542307 396096904 204492426 846363215 345496150 72521293 749608148 719001691 291169357 851892441 958867229 184340522 343124594 929381948 231985803 511996651 499490959 24208359 31287277 104291599 188130871 110697238 620021175 988318468 856865299 248969133 960167693 846022342 520646224 256024390 818402688 318604660 166313701 428925081 365843862 667892996 159245034 63432861 637095803 55886876 395947086 237068549 69801118 130891316 52666235 269424407 150580679 609252247 917775910 763512485 866667062 233098436 72886900 56105389 364952536 8686558 252699338 667897581 827214977 754803451 491590397 895500427 695987433 699677461 274272086 49065607 50278008 95639939 398020101 870595317 131630433 340758986 128306501 603992252 519191931 616580013 911338482 698094162 893052917 816820732 235834534 464752148 132268170 405657904 220266857 550973843 695203360 482109765 996872168 441116145 792422232 539568048 706773228 245788490 223574600 540395749 436211648 202304279 812166535 56719007 179150804 795556428 331076204 740492321 26334170 660584771 757262325 192003418 197526746 32141970 867402056 936753187 750929762 678179170 778664971 731010617 47243114 279977527 890500640 159049344 324710579 758709686 134314183 638993015 469768586 672235320 910750738 732153933 732481321 147639119 514814482 238070508 237789617 511454647 223923751 745518228 847440667 175340621 321488426 272287542 774969365 394137056 156977853 966502826 374518367 237265579 720243151 351854453 682067510 261134811 162005695 522032446 387899164 676853156 579317989 619600146 579789212 20497984 445563739 860992068 330249850 54668700 547395694 319309651 154169806 926716842 81523713 773086966 188346598 85590736 545812536 441291232 692311972 758919517 743809775 569018742 496562491 287368589 575314264 878991912 208220574 288041643 740691402 428807225 719499248 674666832 233956918 411632388 807328610 205563786 52794568 213266183 206372857 326753061 604199635 186101309 300291838 89499774 578925110 678579648 697263560 902597263 200294679 39877203 117219677 821818786 863255555 953252540 554019387 325897009 712436988 885020076 116242273 615398070 45298611 609876586 345427260 345361198 746013558 507364244 496066588 9725462 837664065 584351196 952935848 920912956 818075994 15129177 173050055 600792274 351754034 745653715 279563065 305930106 818799555 383173052 605426235 772366519 648511524 670291183 7323580 531607901 673436386 845974591 356335158 256217989 534939446 437840525 932307193 535354918 908957889 333034269 296182535 390385166 18174709 899009640 161871654 555153308 203036954 602342159 791241744 453040131 876058336 641567794 844007921 808457631 838570193 676631587 77340401 63195216 810915355 232522470 979314515 478338927 678487540 223928461 224712628 927180814 413708600 666885694 781672849 160693585 117068996 691320149 319896405 674732441 860278130 726902709 179493229 742925973 611181113 998143775 721086471 631529864 814934812 331024874 304093568 378938162 971316018 549701747 460462776 750452831 855878593 99988237 144590871 255351055 30782070 155408405 70453903 568494843 7793562 751393453 847543970 919714192 653553978 123691506 614781285 642592717 167945286 747857693 243977155 57322359 156895196 512451225 242479697 521703269 744132410 69489770 324903412 378429342 328865122 556472188 995938032 600109657 873438475 553142547 443333615 449604073 689188615 607617291 662396190 638269823 396974335 989930687 260154201 57023833 257632094 789391132 536317396 388950102 610885988 297632027 499132862 912655719 910344484 871570011 432244803 273567425 515734943 273202105 628819493 663382191 151600081 622943898 932072110 515714089 444664700 646979053 598936305 441476553 588476761 989163975 387418753 314368114 215652357 466088373 577921739 56129572 891837751 141776673 699633019 928110264 406710929 939666765 742039976 748902794 400552727 544151810 335772959 741057001 517079878 851703181 363054404 755811274 345840823 905660484 509113464 741145547 23821354 42276644 34799238 901102612 126936975 655474277 508602861 467799539 518298547 416772592 765812708 836372403 221823377 738101799 107494005 366302301 835150861 917386271 179417002 453727852 368981377 662912047 327508471 76934821 811279664 872166398 504772153 435751858 681405318 109090741 750192577 276741024 130554736 200884632 171919811 870759476 245653163 88452979 388852404 608117817 634524221 934432881 6880721 874461755 213155399 861818347 853169255 877139535 489181271 755786771 954002667 647856499 559405189 852283013 303116981 595469674 366653632 464715615 998057816 921980924 345544071 629598051 635690919 691784184 628768736 60300378 195223912 678162519 151847891 712455790 887751289 240751878 205571905 849043821 573087156 752305403 3718600 980408607 155457191 695109034 299836687 188036358 531459947 973449198 922911224 917568009 454281425 119240462 859663165 922855441 194588218 286138406 318230984 151000719 165923393 324603524 773534732 396155672 349855405 637598090 378688934 229269280 674305373 2381890 315723335 403450371 483302639 20541268 927835719 107821550 223887397 642877432 187182654 307255988 15720216 695168010 379789599 507786016 83537844 295505159 84981582 470835296 388233707 540689193 620731882 544313059 854877473 111421064 486818360 704340309 933433546 108183776 704692860 941152992 149609464 331283667 576348354 957098738 880037932 159186742 275795423 371421295 745918392 974828464 375085844 242948400 130291287 862003472 329432936 998062420 885004799 790188796 957151658 776172766 153084538 892320098 268974034 808423526 162304442 931412400 131487992 467052242 243194249 501952027 685096501 887611140 543773762 947940857 159977623 419790494 568192286 505910933 897861233 103768774 857257300 785799250 356306173 438421112 206883670 840086990 759465537 877371960 798912975 830189980 232434976 683781591 881563603 564481495 439624524 856524166 284178854 841258004 449210906 40198384 61644800 91950433 76442273 70342008 991167765 629093995 861800077 602420410 419875085 963857449 305885386 935287298 706552668 632239126 989632460 278303201 62578764 225739379 790588525 440489962 566626188 707991119 195379406 575130697 210789672 427366504 11151438 550540653 98816802 632558398 724490627 794085439 138175612 721928958 971972180 847403260 832008068 87489379 912899141 798172515 932885472 341165097 927407133 110612519 867702909 150294956 39476242 734593139 197213123 695967397 552147525 781989009 187104338 286559600 253117863 473298827 240595395 529282278 533073623 803930417 890984503 103782725 368541568 220485129 38807330 971237882 544510162 394763253 485120854 685471808 103500600 269919235 803343583 18228419 765710601 500507296 298085920 426202735 677031908 24573289 335130608 252910894 245854890 392033837 425809059 922038442 826863984 598389623 188064364 835267129 790387975 755019084 60281449 351409962 636646854 876053096 3958972 780983568 9845264 105476155 680714947 168435763 371627590 405346532 566942241 593817086 60574147 210632005 778140984 770140421 893811411 938712363 872128903 964774834 931916927 890135756 942813184 277736497 654877352 792550182 981823740 939963365 408261373 50474744 52422555 992962573 656662323 971734773 409651837 474286472 510552274 2358358 574024570 21632004 719473287 584924366 856082881 318471031 929257785 966877574 452911151 274277237 633996169 186367282 583984766 682912604 83029071 224410617 68481531 638258793 53404785 745153245 89463843 515120922 186437657 280116423 785683702 987002695 878344515 437677773 656364415 724792274 835794082 373679898 555374115 742878137 465207925 59630 866401354 406939658 546081397 860595888 581703489 946527024 47188788 783468454 721525318 946870323 633273832 996563746 834551660 792643238 5302424 622234358 652246081 918108222 572739905 280658163 406904402 612447384 23975457 560224760 506136333 797281076 715370841 460313006 425461697 681882086 276114498 484916165 254781070 174943951 672808407 292285324 903238102 141582793 661198571 574450926 79876246 512881686 660859768 852563843 218960155 859343559 24407408 490551111 103416058 84816760 554094629 65584238 402527565 400970737 960033877 483072954 583407003 160609132 333906153 508278036 331347120 174280842 824872205 287742089 461257348 67312106 995317551 587529821 430490413 423895005 153784330 110256171 576023315 229681399 996326217 954533829 973483520 882961107 422516156 43057488 148516422 792817279 964577108 129876261 733656026 489255214 706287308 466979286 204637523 926544077 125795697 105459241 593409887 615956578 853542800 313968704 674911031 349056626 126465905 947892907 361440114 566945916 768844913 227076575 995531676 674261317 509655814 607516975 944964740 416410876 434278700 683963932 110814394 838829497 44189335 851396679 364166677 901856167 641661162 801064549 214110221 787705245 293314157 322375658 900143314 744549104 823047312 459586022 235533782 75155990 242872558 529850970 801761106 279403083 862828120 388013859 97122865 882713486 405509496 933332933 622978084 266143820 797452779 342388959 41711807 8877650 32894176 519620587 254389399 661976225 743307837 13054827 962748386 892111767 215725496 635222813 173110311 66808922 311712369 447018193 519642635 287113048 627221301 672884391 52365476 194504714 422512010 657034666 543249036 711414337 404345579 142548742 667147791 309439578 2936014 786431604 3769562 628702384 203722625 903045789 777432568 489952719 336680219 626700418 856827951 448894658 751831413 162828502 418478403 24943746 857085883 138802934 551521404 138283767 691925161 369294744 711772998 274752480 827507235 467287401 522606538 145330871 489396475 760158891 228440750 665937508 508626506 419718179 765334227 43749162 72413550 873106074 837144164 429268883 78103117 763414513 725180065 981502268 840575524 537431419 732217278 427604575 615588101 112112156 482517252 769524924 345830706 571167608 836653355 659903761 732552722 619612107 585643488 76973554 895083202 964568443 82699999 119289164 57632432 970077118 871323570 675537633 37562285 249479183 349145319 94858461 321653496 622730554 913723019 102227318 384401761 180252440 465130216 313278647 939190481 20006640 778953558 568977228 895432100 544024021 885021713 346969298 430334035 74934473 717571317 776570009 463162261 392382674 638849881 385264835 278997027 20837685 830111413 376568629 882505014 637546484 915562723 104624553 441188211 28740319 713166224 554158121 651079246 838111976 187318545 858026226 486031959 592444201 6636268 116598251 453348866 783418749 177216780 448846576 149890245 737137059 853044919 193713495 31174402 532312105 12373299 492647981 12118554 801667387 474997664 587741506 324162743 627006915 454699650 596057800 31482215 945872627 413949883 587062004 313755253 949595319 55744851 871661312 459218580 507173756 105339100 205720438 523660467 834482425 433539291 485312688 882411025 550736620 713395556 705513769 861153533 929087820 532435780 952483047 422766472 169414752 692244232 809927042 231189279 842569881 516665281 673324633 612360168 387725368 255984900 897177440 50853517 526175179 198291529 249367715 236618229 622776411 743883291 112616198 287922213 936966306 609488669 364817165 684471712 60320940 983548921 236905691 673212303 833294735 569112578 565839787 375362067 703526820 272431437 466410977 903721459 811005351 616105804 416951273 51540584 261323705 615595185 596982434 127807572 475193966 269310847 448963399 569435029 285927899 535062909 851267228 221888427 308772211 241649421 428917316 430116143 755366864 70272782 206709020 690240236 965777946 599033759 599914575 603223534 651167736 780581635 239903219 521946248 620617213 516828754 11121511 990282795 236601545 239051533 226761707 914013190 303004109 582439197 985909537 353727954 217334033 630077611 903290678 286570830 241031607 824940608 3627311 168405601 918603726 389813863 100482849 916665351 547061397 337097241 741311900 472989791 125367136 678154744 512469466 802852815 865117461 962953060 970655266 719577846 954097047 643069742 312763381 724147507 897676231 996136130 50067745 646802381 179638916 731089078 554121573 506790706 952598749 765099515 255458574 399742843 690459429 918916126 945555287 946804610 948133388 595852063 742999168 38597007 140791814 104720547 215818346 21235520 474911144 25692758 565968759 248246174 840422263 107032294 609772632 928745278 196579421 548430801 478026939 661969912 432690432 707913696 702225013 672494338 447486433 219513261 58422786 451516976 271424378 419867731 792190337 530776394 249932642 775145779 698748899 440009818 350524055 93027067 624707844 718019414 562735965 19277746 61427589 245139828 382780508 454528437 807220357 236480716 982588391 678133644 428635742 917908646 283265677 625065067 974441774 721011708 347568834 551118503 506089836 461359654 967848931 832164188 272750621 290010936 113638823 301079323 431940090 560915462 657496552 914133122 601397654 160664218 782292166 841657450 586078743 489681544 130301669 196745938 99485403 429999871 412313457 805984828 104950332 21088656 789385008 188050351 842447396 387346306 545717487 952976766 942699385 169809727 612048490 761812328 120849546 369466812 74647325 226928809 250839814 391303305 532796329 981441211 550169584 880649768 705038776 986971604 760990432 259584148 245062759 268865698 233355647 951110407 253476961 96606154 660253450 859429878 116994314 664961951 759504276 212857588 169175148 401086935 136017309 438048002 720466787 980637894 927235893 248691616 739793340 767497151 124148408 478676385 367655339 664938539 362895305 402796416 846028496 826063048 61764723 27374668 327163557 38214687 298393418 806611233 87250223 27931924 349807869 433348371 292353285 770438211 775163832 283213644 679636244 896633459 656192523 963055050 305962100 712848042 720986919 304649030 801651944 871749357 88698523 823689767 168714435 285587053 242197984 447116456 294041701 213177175 683369324 517748769 93263361 972320334 370291773 183916164 903222310 425777965 143209662 228884428 795209389 365460060 811672840 590912416 424094983 795929439 826847929 834608658 160206263 890428299 246012839 776307291 429105176 175466435 533581356 589435122 439557053 850368043 949877690 867184942 877504364 951271958 556305706 318137829 349153689 71770366 648921276 411963948 273915327 209597196 953165137 284582711 283977887 561071392 351696263 627606879 814797927 398236262 380783858 74856055 314006656 224855864 205901017 977007616 674026561 478951266 766650219 747144046 272923715 506407317 683255316 238320483 224210925 907581199 989770284 125710821 543163113 207343299 29811837 114811820 562392033 822328918 504051983 617513770 821175640 285485952 417077086 621564820 263957454 392445526 566835420 638319829 886955430 77279922 936489013 721555429 772017809 883534124 893508715 620881 41541102 390965781 590864670 502770567 459129595 923075455 829225686 807573694 360754529 41863600 304959284 897489633 102596526 704705821 746386721 660275614 65246978 777150683 201765730 228596082 336872724 709799772 377496374 996119026 562559992 934699238 657622515 563066632 630924225 601222411 464490687 749020612 237694360 138487310 868443473 817015156 427543251 550533294 167622457 869061917 920485549 818364998 140242317 200267591 549912068 626521182 581087552 450084656 868918991 834415411 158995323 377650424 354943991 468872182 622463811 755398759 511105914 724185948 890000969 410667528 626205396 966602987 487752567 782557372 291165129 216294221 57930878 461907967 981318768 961473860 382697009 503736900 306199271 788570017 188695035 672659620 484378820 296910853 198795302 342971742 856997944 990904239 612057739 51056918 271698748 143974566 260759813 117815195 512291723 636127585 557041955 844961739 81654803 447204080 960913703 504570064 735176805 115555256 309054751 991641109 2829181 499803993 922119268 120845380 222290790 779449843 700858899 808479638 608295858 386036173 726222503 362735455 413895317 37158572 924835786 512579846 941532989 684927378 68160397 566379181 151860737 562718243 468578226 964066576 811159737 651675286 777985034 120876707 857878510 644426006 93646298 343141744 169085885 361507143 573482691 166626159 328549358 521062619 306593216 224230834 291750317 860906106 542996574 646024402 600166587 203492071 295437408 148261309 959788244 916582284 287606453 820270308 341739416 902270690 296925013 471791630 234749871 423842085 941567426 253204290 940799429 679200002 126423233 219611499 932043516 489293233 536051245 994285618 179826020 716198670 980433680 893013369 89701358 363440778 496545228 647270424 517029321 908908703 492480342 526055701 142363030 920486979 697635223 251293391 922192731 141737391 159927822 387254932 569106238 260266127 516612762 363845051 214220131 781302139 857602204 691485539 34016946 990008725 714030970 136607774 100193899 938626726 367766560 791755811 5395048 555951993 658995903 792153323 177003907 145093567 145033393 901566712 991573326 620584708 234045012 346731805 62900486 403759787 115406840 399275517 454782623 140158854 479595625 616631781 444960516 771791813 637187962 938077584 645805819 159379385 479858335 707698274 969748595 922906057 95966616 766182413 961249762 48981828 40041796 855945257 211943480 522895481 184186943 549392634 860998082 730722944 257735213 359305648 124004351 319226250 326972988 732674096 511485889 216974185 917834179 212968173 973825239 337801051 13157255 54543815 177073803 501389463 629025889 263234186 747230822 992189283 98400306 160875873 13134453 653077442 43451725 70198771 371818984 48552523 612459654 973879058 893371052 567841163 459782827 419322848 969331310 893387925 374492558 475216660 782570187 785650921 392588296 196649295 242130303 754796401 220182794 262088924 853716467 500205403 88289997 532587901 581235580 687529961 792103446 510090598 973284966 780360309 271320922 735540544 150023838 981014906 309241632 762261505 409509359 49880311 409385269 519112727 82766304 734341581 256188683 525235753 456709911 391799801 162085571 161816652 361527793 53857064 703518700 579038806 713640725 851806994 154469800 281588251 277023023 34877268 926493186 470957968 710411014 641052426 932865934 529399985 582071404 520369543 543611803 955148807 292090687 968755907 948465260 573672944 956866668 714800785 777416268 130996255 167009946 146981349 857474087 934426923 926956370 210697012 764134953 818303699 961631585 942735729 729998759 905707533 298722806 598392060 398545333 273165481 422025667 211074810 237192709 47477104 465014836 192965412 200050870 143513267 7736541 945353769 15134229 163942867 626701200 178507857 319834908 472487963 2302172 650292446 486943499 153276250 395725266 147686063 369209276 434286626 536025008 86595367 83999190 193255818 39733106 859677096 420369284 127504856 346740915 677892756 141182779 447248294 421324483 469857563 61867692 959119450 944858827 310920725 551204471 607607030 818247541 852367108 630555358 115187501 383232534 991201336 104143369 721345391 921036198 882547091 385440970 926613374 970622144 411965773 236036346 682703588 268964398 66648578 152568848 355706751 247889160 263225446 188442348 252436055 101900456 569379481 37662588 440571418 979609283 403064864 328202801 613115082 835646835 926731034 13493430 510812442 591657894 308917694 784203781 767144681 428571486 15326452 365340105 677436651 802126093 899784587 618686592 174204779 172445155 710378042 245538383 260012403 372805828 93885172 282453555 575352872 43553266 684823894 395018306 167681651 317956492 261757318 101576478 289554250 556328549 863858583 454632853 565515438 473544843 210089652 706644300 704980915 429329250 73294356 279403134 529324241 45521729 404430248 136086058 730050266 638544549 276675555 359671346 726614865 794963637 167283189 189096892 796895450 663342279 350102102 23476238 464835901 216875896 139585324 781412070 952766416 796830005 949903952 568384570 703808292 489421115 332514008 903142446 652964283 648711156 549532976 104429935 70774201 992625327 486773202 865756986 373138452 788261327 612498068 386723784 49614242 303183932 186237760 850938324 822820306 681001084 939673193 251596389 695968001 889949146 689374373 635592433 959948315 976318788 728410845 429128959 8663039 472528675 672462181 267008238 719760066 803645116 879152005 846790942 193205405 155943996 342515737 299931399 478978467 922801686 186559193 582941544 819827386 610943775 204408458 894991957 993295386 435339067 877179923 55929566 199134399 53189893 26396592 299222695 667511373 654045830 536949273 504382987 834029744 166580346 511207106 852483006 368902339 925303355 156729537 436622852 240540718 560935639 146520965 897887356 120687910 486631459 167507966 618948980 694512577 370284934 972127775 604382852 322186512 275785551 390678949 979753455 270942847 46836030 191854018 443890160 400022546 86608017 190203637 380721207 935706239 972082354 185192563 47200642 751454375 690750506 640155770 967467239 385583168 499014328 514952729 312977606 146992563 402907206 394456437 31197457 797350576 139805959 846446639 229071542 802421074 964357123 513956785 358879179 232492670 216438245 782404861 628895028 400862144 794988041 158976971 257469116 630150608 145031946 50473432 941650595 637938484 266674238 995684227 901340495 403429510 278138916 763944542 12291514 719752508 244583670 170073649 789711758 799238049 883866849 65690329 416697969 668742942 970416860 916670008 888849118 400111026 815070385 415956476 962085650 983542848 157479038 217650932 788793972 247761905 433863899 16266449 726171713 519311327 607466804 550138256 354379023 906074 188361458 194887238 65900834 67032650 688879777 450830743 324081048 95217495 325122935 921006954 330502265 249829367 110568354 257793282 780723225 948523477 156974512 295474542 774144932 327258336 777672841 691562034 864454999 534433681 583407700 93151710 350604109 710636479 798746307 460464287 226367577 577761435 286119300 805128374 281338745 699717904 348961021 252492405 545293539 71148167 535241552 231838742 533623649 60031688 504674975 776597180 15209828 900672859 767636566 677779532 631269725 806398089 709666991 198027530 87951190 638991930 225667793 124221168 361256784 226792414 275472942 555720122 974105894 262462612 491594825 203874101 692804401 40294865 913872872 678491549 638127799 815703353 408345230 267925471 619420178 408924350 681441745 40347496 866931836 152144949 290723352 162119316 817058099 929172022 329129794 95648252 695416386 413220307 827724819 723975799 932048693 336498421 149531303 92918843 402944626 648291910 300384429 936835460 433927690 766981572 419896985 737944923 118644645 924673809 951251769 82567420 493612859 174145895 590727969 516482532 417577023 497894793 561779764 844795126 427676984 403287401 944585024 764954371 151949726 909332479 280392449 615970608 797251116 85919462 682349298 479234586 137286161 876435477 699135496 152375664 564492422 498535259 828332685 829625517 303840375 270176914 80078318 31293875 115793710 621695316 295111622 856851561 483004588 826197283 231983500 970146580 294456515 9277056 849382155 236327614 909397549 267004633 590572742 281856551 3612841 616881752 473105676 57343447 500014328 488677259 671094788 289723267 107441457 443300175 334567931 982156413 65808272 123576397 569414517 998111380 559306684 768422974 934489849 375768336 181130991 727264110 744607191 301999312 570000036 100181651 658054928 885146125 843562679 328592678 296921092 490350412 849886226 75042318 552217545 574356846 246469883 542283352 207826153 376053055 454109939 353720424 349888789 334324361 992749688 351949798 966800715 44279127 17273020 975167675 817344653 754270520 783549542 40416819 532066198 436501635 342026759 636989975 31321894 487639053 583188680 857771419 909874866 495127129 298643110 771610220 650297396 619008967 648537476 132378531 759483511 778893454 431056688 244806905 323775634 735998129 44939609 778990507 531060891 221358664 134873412 920272121 52425204 152492592 857651931 10093881 460596836 692844807 125690108 6279617 784879755 702036565 289530972 976189182 992878036 7116542 426851626 557292080 370877681 11613232 825765292 539731260 310127091 599358048 431155598 178843040 813381544 424054574 919682327 76683042 5967266 468654851 759390931 399338754 281471610 255659135 352841810 369212969 359959346 346888878 373763481 241952027 556695857 700530230 387678157 187056523 348711405 995506691 84848129 761148605 357788911 365620040 851621099 762104259 993405633 24959202 851631315 414155298 275877362 617899563 427590581 279367984 527986305 158317285 650699872 53541014 529037727 153582430 126419098 561288995 673413022 682719222 372815805 895391203 120616953 692254445 974503516 930727746 559728336 112924060 109548069 336774314 240969530 38982301 436597279 1700278 748456981 556584820 493332430 526624179 66171655 954366467 825552039 242621805 158357319 416961917 249398672 262513064 188754791 689755554 951023421 841479430 528696623 749958825 923776879 759117054 527327839 606903071 169855397 743411665 713789555 290530129 127527708 352882198 561610464 466888746 590993510 51656619 827833300 917610259 943016071 980227051 313228864 276164116 422575191 975729208 24783191 310323655 971608946 514939002 168538421 585276423 255602278 12049780 686578532 250845938 346014585 444109021 513130432 910231412 575506868 190501839 459371470 154877517 928477543 232766061 303252086 721179302 511313533 672903529 648724772 303650226 463925622 804190797 387805466 170681011 146991818 149406675 224120221 908159648 422664781 501107007 124293781 650382617 540714020 445977149 435604970 142715675 276960529 586338928 147377841 457367156 772677124 802599505 106859197 283147823 471048892 76353091 699345077 838132709 24103120 173743533 361735362 162330222 835199834 85884705 373717885 756787763 458559017 815789849 915416447 238062379 561510275 569004668 995506030 955629089 543633490 69885050 547043995 728532903 181966844 150245046 379982792 210162467 240507006 288369172 584127834 881867827 891402947 374214225 94132497 418474557 149443128 494909695 483521352 492330076 736410753 446522077 153485310 191759475 572137842 522346082 335763573 668873405 991933993 835069841 713519774 379500703 117980668 133716986 978605298 219716683 330606049 461325469 307169925 266101987 454418082 839156297 131045564 869956518 194820934 618019450 23210721 860132843 882513589 713703903 179994989 586443586 432156628 215859062 186404290 559321818 52224450 31629013 814396799 819362356 857534317 576946927 668442877 265142057 230841652 553035932 192748674 318914506 771516058 869410063 737095852 296486699 2494756 81873719 694108719 830845967 561900602 300540608 136791701 938591723 623959335 567294403 673554772 672319869 766946773 928948551 212866296 270904763 996487695 161117263 50177525 756201014 386877173 494913915 945230990 263037550 119595850 109052576 813223017 159808350 404154368 277895828 106852228 944701745 256579791 815493559 316036764 627385482 548342632 853600765 608716677 407796311 961988385 677690258 861261844 944067460 944547164 568304259 576107575 81057378 424980239 28497404 311190821 361749107 354829071 308934345 975511067 327845416 866076061 189902815 174651158 301293076 353383881 567297355 92099238 3399389 580719059 559472222 185073587 155540352 236908619 203588324 266722921 100940381 394570683 235365628 556914262 418065449 7174905 296155420 310106729 373995948 923331163 992583123 728475508 312705067 579763639 804833457 555615234 607787683 444101017 979179223 268859514 760982457 790060345 415192353 89762162 804466058 28078552 494097057 718521834 587208477 101246749 502478408 689524399 69069365 798512439 862708332 227059608 196136232 948839347 61329129 199294281 618613205 328898603 943820309 454139615 540351834 109324882 13453391 302238609 55830221 679014380 612910830 224468678 687819492 681808223 352248364 642430383 996502244 609864691 375877213 450692158 789200595 922824029 64062280 551042789 858614742 990435928 388128671 364453646 256706861 905746250 528706922 87459242 375744420 588915175 725970987 101444082 683754458 308813355 522563556 620902282 664066907 788503533 698678389 704486681 972707666 528851994 857575494 858353423 582759669 292129299 223198109 648001336 192476421 370228622 257523723 843683988 582455292 996352537 977044624 412102462 452460320 956543892 750093080 359506364 256153976 642331618 800597288 284924473 733268886 44151966 594363197 50895594 843288955 326987576 25713057 702397497 977796079 496989851 29992046 14794763 497831400 914342967 127030192 81246496 619178754 781583362 185424390 977755868 829040792 988746601 358993189 546129155 787264849 942796375 932618607 117613551 532714387 910184220 711593695 870575328 731309419 520812883 745051615 316589063 225380780 660717775 530818770 401180681 263217033 500308212 126088139 733049535 267477692 675695032 44203036 86647013 626774717 225116364 780644712 765218703 844789093 587043936 224891806 118864652 926072919 877237680 796425823 590789439 704013464 844073234 124184312 845390568 591304318 467323066 256632769 571729486 349057453 35345177 370892282 446246718 876176039 290529299 337733050 108242053 436962795 207835474 838308178 361213630 566647025 312132222 15426560 373287209 205829794 601236662 567383164 626044580 457313268 398805192 221201547 327241830 950216309 605684158 970503567 892440061 833863395 206924425 940858111 852045883 431771216 884546488 142287106 857147164 772500281 35732958 574956644 956098126 186131473 708303861 792010172 865281638 385295225 363475559 12432519 421663556 170642508 731330185 749434826 450361713 720340896 434277836 813463367 597636669 627151732 866800654 817621690 830138425 864059030 468471124 569655506 944294033 716530861 763894714 265799134 634062326 390455886 702601225 262327138 727413727 964529642 972661495 545870862 489013517 469994566 822882626 926820488 817483396 778804018 436399056 862417930 671389481 345087407 385985170 242533062 620754916 496053460 382013246 918313818 529031042 451779451 401095384 586222399 452161245 349373719 382957933 25470165 564109034 312681862 402712051 518422616 343936715 711311123 666149102 99361172 688202517 481762398 811731524 918744425 616709675 605747020 796157028 49724162 260978365 34602217 942894407 564222901 662946913 441907547 704772170 149117241 767182280 219388188 519903722 2201799 360564331 447497266 33263671 398816059 683755928 923440264 188137367 67405460 424328523 157675333 230772166 773089841 310178710 928496247 306324756 503426852 716172626 285139959 28354435 493222254 582939208 72397121 235530727 572792004 958444154 906688218 455990378 688727197 473570236 53420420 193465737 825700203 498387534 612756130 821452596 322562401 372775502 50395752 738510810 689327801 321579147 637511441 823874023 982010991 435554925 269317232 91759897 426433217 755200325 914537290 256106445 714019323 125156775 275778203 242240757 197454691 553809789 262012784 868767155 10167878 957832797 819891105 815565682 160259182 125326993 395689245 993880198 411780102 862610297 796513285 370489102 529279635 452235828 518016435 252592895 684523492 268404065 300966615 654212004 420776406 4685363 674139975 806223760 506427208 297888395 245407407 606707357 111892214 959207028 490522549 64616122 265357928 886595326 334226811 225653902 88615020 824617089 558674795 946788453 532663314 445557356 360550177 983349830 571024331 79188689 789858386 305182464 240243085 619562389 778395087 205528056 94047194 285451762 716219769 31572383 153202645 932271467 508509313 868042492 975452967 106067754 895666919 754137704 863346725 866601757 156121367 451449741 775797048 180925124 887987326 639936760 215556225 292918406 915896197 608463051 378980958 117506376 912048418 30755888 667856209 11892891 182575361 983372700 219916268 761994578 919739672 431699785 46805275 796534956 908964112 579187195 844695667 38255479 105658664 858095335 907200175 632075053 660930570 172365561 737686478 208777888 936437425 537078341 59817832 243589836 671792959 865379439 377259497 58130589 352054207 978695955 282762058 933154398 811262939 262976230 979803480 539819873 889713828 374421582 680369315 985151416 628590276 221663707 201775991 26264802 42764029 391882007 351698652 300476330 270657482 487810125 489901393 452037099 419194909 29740897 657341037 189808709 50827915 577646371 137279571 378706002 280942147 973326504 750519002 475896906 61990870 799082418 505152367 735380642 188516773 152871169 508551799 891498251 289359304 261521591 551609631 411017321 432974818 850169316 167307448 492033398 808851965 369778784 799499890 932871367 924534583 149900391 632216725 206634759 2790589 309008922 432413266 784471523 626603940 121072770 847086820 538653664 518934965 987897485 960469061 244130232 760538385 905801468 171037623 188182526 497886879 848161983 718121767 432123466 823694254 91857565 435019670 464718804 597134065 686828257 41021333 814640747 19836821 279067573 140877400 171995295 550404341 318432938 389323377 940847145 291837114 281866559 964839215 40405028 291403346 487495864 812216153 185834383 422902225 579932408 648713448 892921050 459745957 500454067 470382187 645229436 686667742 312461873 625018812 872823471 340812191 883636722 554262901 625204026 738680592 246566238 917482154 612678922 304525344 370271470 794952616 628132624 491616266 877583332 620518479 560613577 670352849 631015273 792534229 780813057 827041822 873209247 127582555 149524679 221878578 814026702 130903290 849738158 829467552 992743896 356827805 529331906 910760288 54119935 371970984 741605436 610332745 14907242 370613236 527335138 187831389 946406821 287253231 505191488 821124582 190904348 408152173 836705450 435662870 741698517 359369545 977507341 928566399 308495232 258357932 18456101 203521861 349859383 480236899 179995705 856589151 916137302 453522552 257150368 457392071 850841391 897676833 938988342 989389435 753808948 916869541 88747740 224451255 156417958 624165118 591987903 348190554 831660807 264213577 366406853 656684669 104034659 968068291 707606412 466132695 52756204 325255927 311441629 456154077 279939690 518275555 537750677 248238683 951099324 561558458 400347772 475716444 728641787 157372781 426090136 751305928 373880106 87027266 330296807 937837333 298618437 622315566 679114906 937763111 601520423 47866035 304405212 82925016 697399312 676188551 525520528 46790025 95073457 738933024 343010607 779752848 909432297 455232729 402264527 372778078 431419320