5000
554209962 575701726 473213933 136304771 527802353 959705606 21222921 478120999 813569648 950218688 100003356 416693492 495959369 357570123 535802303 474102262 223464498 908294310 849062298 883059772 554013116 313047819 450629610 131210598 873416026 318646444 683222817 354347953 156304691 82041316 185191150 661187589 316905887 642805613 169173698 75321669 572921567 617631370 843266567 928089382 765901183 687822301 796864770 915912710 805901571 977304444 105506911 59069937 226860001 452727936 99845969 279875539 257959271 631203721 818412857 217699579 967644372 145139739 505708732 733590725 726549254 652647780 166161856 621768965 15017465 879475917 850833465 671790560 290071896 112696229 383158170 605489271 87461385 272215544 399509146 183757179 203393998 914732113 573765252 848881221 991355606 813031980 469269176 405690551 662231040 712533395 273380238 614734449 402005737 930367099 554307682 431228574 489573882 309882311 338696406 98718354 32974958 973359033 976395160 561667468 345903922 913800751 702970760 171912623 755762022 847940619 115740810 467076957 599005496 796599745 336522530 820022560 662043462 535395255 868165243 846574153 131458482 810204044 219150229 810790355 639620930 490636358 955963820 544770637 839275205 446325793 752646542 632139323 358135041 773689554 260468173 605918241 345339484 821678238 707578734 157459835 475309115 776972587 904848967 67513740 508488317 585863912 610694169 685510779 504835075 677434988 541145807 774647264 86677794 643547243 400645143 1494581 973823894 745624270 36606221 125771160 340689929 189288634 419928019 358921269 174717178 774974375 197583324 866170693 275670543 862289906 791063209 284245509 928337618 952105367 855126588 349091407 436193126 276927050 347134686 571258945 951754390 666696026 86193275 730646438 991400195 976284374 370465451 525737294 245939178 889042346 216909906 291791392 404363753 880935822 483740262 211439949 696869551 339238835 623894454 158767392 28000488 547569127 216080260 788536691 336093995 584464102 824488271 351243399 45511889 227128124 536287487 894767359 256209867 772989221 884933718 772131000 607294757 25155937 796414431 485889345 165743385 427201692 327788484 71257984 98674072 943566504 12140377 975472464 752118946 710702726 939219835 501789547 196828997 31027448 606008475 402113054 609562272 635450493 95241784 645406138 344008415 464110959 904499083 108365241 243901985 296229727 278380855 685939716 91979600 907360135 46149305 492630964 226769871 149403421 920412651 587488874 907244622 876990083 80590591 643119336 151035171 312628792 310960586 771475996 237654874 805086765 177335837 710145123 999882819 459465275 651303010 279920821 159471710 931339143 100379655 233870181 166186762 575300360 761734386 894875969 539072882 259484217 135314820 975963462 745113507 289594352 975610057 95407231 244701305 827125766 683342817 376810156 156153100 320439080 292403565 637589582 174168401 309888397 78823120 668452890 306874559 688582942 402117835 226757693 458995964 408935608 331277111 150923188 63443274 550098577 606393033 347340959 963785623 127630670 288766497 159420721 460023907 628736154 40326855 341527630 854000140 10651562 682349714 548807969 563234885 954233593 882795423 12571427 600559670 257151256 746697741 480382347 980231227 506233262 143732667 276010539 930324573 112709318 619604729 843383655 67915305 876803900 620615057 709002087 92586784 410000446 758337886 50073373 345336487 886856272 972586673 443619535 550202985 400995480 720304784 560742533 905396649 406532308 380886755 832338655 751892493 315299415 423285830 601605767 615483905 414738203 320610380 156124963 728733219 513893933 690980617 509416171 890060768 46060261 639392835 346678200 268928106 291421302 527602611 478463059 60488975 40544611 89054207 483103720 177879211 582161151 212557980 662765510 713276876 653192196 491616112 676506666 22283238 332502343 103947439 59476721 715036614 32865402 592691122 940263551 752464784 6759927 931207420 620777239 367853394 157214978 357908305 418368504 832261847 710374769 436597040 751490899 943890200 597201441 489632395 131481996 567778176 108156232 689927249 642876068 387913709 237842201 72004948 149070014 130844860 354895028 305315632 552087436 117297660 63574600 547727685 540969287 38099500 219649212 718243766 390460931 691638622 550855007 889355847 672234284 186257081 9001121 906120856 968725150 152313888 342484295 154677094 480498114 677471570 473655652 371709218 710520312 270488852 787138259 606123321 873294185 616091383 621912490 502138289 360262881 253329518 647978200 986732796 246046388 831501347 307174550 702775989 816126571 960260564 729188854 701769840 653246171 963274345 917454917 135522360 627870718 205494868 186308661 966146799 635789020 998645693 929582210 529722838 965864582 367782996 646510291 9230998 650275031 993444643 201196568 148371268 520458863 616019684 391842280 237813785 764436986 822648408 160939721 950427364 186230420 473471485 77005678 747629760 224558016 799320402 714599416 132724287 398414927 89100637 100851370 567677707 605281944 118072464 753788301 830314087 162827374 804198079 955222522 11438397 380960230 532455107 915826256 763806553 809323000 926154493 826677923 974274501 393569779 790711926 144256694 363368419 228693328 271574215 469531376 421395309 483580362 589911839 937193970 988361152 478291841 592135954 710360785 201244305 933859910 177162261 555886416 993511833 192979818 651707057 388245896 380024176 699728983 9103228 677686095 571250255 465394863 576194519 39518380 207114277 222685034 151960222 498687042 483481791 837484270 693613048 633059882 679332977 532864909 311863066 653724451 586460517 958023103 132410520 70381280 314020692 81749171 487691103 422889163 250537859 528909656 841685488 30359790 334899529 602242995 654722881 675558616 78412014 787612580 447321537 737014979 770679343 965017852 89162895 859614327 622576806 882459159 497426168 653856358 930861875 774479636 820538196 399828424 454861481 169294406 615794112 603682114 722662432 866274120 994157829 578331717 736104093 785252616 322226043 468939571 429858681 940566155 431532664 401250457 788749954 190287815 227419273 422957616 202047412 274205198 928023872 826825962 144517985 199683667 403855505 372549963 664990526 568525016 959171602 637284639 58443386 67946606 784149676 51717914 576390089 370627138 740775294 480145802 397973081 203891208 38420 173038628 939743146 914655891 476902564 548219111 349633390 168531975 19161830 712310256 704422586 410765767 842679655 170653525 350494619 235786666 581429202 395623080 682107143 128040620 868537494 424772130 508269129 133569975 602886161 454515685 490385020 848456829 586398289 37940363 703222562 423933743 162001984 719966955 82902016 328700142 239147169 559696002 666322708 860230522 818295448 726622252 726181820 898711195 458742053 491776214 679031358 652437965 523238666 899570740 593991370 890826309 214032811 192134034 710845934 294245599 384070320 525317691 622959133 922127873 215170994 424415454 772437962 416392368 511962233 903965942 425600034 131923798 835605346 623953500 216741955 902842888 593934319 575107427 892523846 798540828 674077695 837931357 98192105 398112099 242547389 721643406 695289399 857225909 856193480 495581091 510999005 548264811 494056483 914099947 779058709 167234777 258147462 928144813 978777486 197738057 497456008 928832607 835593742 964982685 931534672 471404912 364403760 555913781 640384491 497452854 761985706 665921965 553951725 92018073 763906800 169594608 893923755 888940125 490085741 336837474 513696353 824014232 694297071 342001015 161051772 535798877 570785427 450077830 126891144 831834895 470087198 23084632 753153465 357103915 541719827 805241320 429758245 641508749 591039410 155197068 14122659 743382119 494033168 959962614 188998876 55308727 668361601 842777082 821277392 954957000 923784471 565634460 425253167 591695714 885050719 272945400 782299393 527638919 246173293 578958643 77789336 534019385 697323488 457525901 410602062 596501559 398525241 644989710 582994708 953279317 379284758 685130038 662782488 746185294 906391485 339789879 988902830 864360709 930983931 110193939 990140718 785432116 314334947 782331248 415481123 795026077 468327859 391450102 679156250 773017406 403752948 909005696 712860197 252845844 302634026 263735428 819661033 69856536 892917604 103403949 830457574 443995062 135955694 204293956 409717253 403958483 717965094 590346422 847580888 13565744 913553128 670490704 168001128 910091326 89706842 941307710 882595402 895087473 515028030 382586248 97228434 995713998 397327346 931673079 221430838 374990923 400665603 422734183 749907936 262023641 23242542 532404434 774621697 438727195 101742627 227246809 642385707 17345254 217481725 518400552 24724393 890275996 939607570 420547549 885267058 509625527 656004106 98501608 882401604 958963401 46483882 904306053 901717801 691108767 582381226 80009896 501187683 338631597 745757865 351719841 754734541 829483140 945601925 382230469 980060861 775440061 288680706 596131293 632491267 195062226 627608945 8914696 450631437 253254274 656479115 204771042 345755001 385551442 479834479 895304023 552174691 23041397 588993364 948175065 954154784 646840252 791907897 247926212 806381986 188739174 152474794 180107717 778267932 455016591 423002695 742778898 793623684 985368977 62262096 34803049 274217114 30524264 31004782 997191548 520598199 368366223 97284295 722190999 191673668 90088643 587401968 421068660 16630440 36345045 562461374 333487334 89868591 995808964 214580888 50697671 68656844 536474920 189756509 647435873 84236742 360401358 401312593 117364332 971071638 417466228 62741139 366171304 64822715 544098417 405432871 540249844 907661249 634977345 789919623 141449131 345508988 749314880 20328695 879857031 220071979 393014579 383276013 288923018 493588018 679929821 267986511 844714080 843051387 68886417 387680247 275666691 91141722 639331578 581475005 906593966 264504967 616838199 217613581 917828375 843324189 526092680 338517521 139771279 966661466 768731585 180954951 401499390 864508915 500950236 602362092 112411041 565120921 185902620 801066620 220617870 486890248 131790026 67121101 727488617 527891237 961432028 225915443 679435141 283989779 192848398 811527683 927534866 199467806 316221439 869735961 453591433 782090978 697497622 518158926 807602062 466574639 89080048 718513072 782509184 894298316 799073131 582677026 881584253 893337662 793499946 954842745 198495548 552408439 337721878 808326409 10662867 46372711 826816806 335962418 984698670 702768159 23703499 491818638 311140058 798541054 673529161 859569031 94712094 925570419 310338152 936222708 188047190 61264421 318672288 45781796 554745970 646946120 468240213 941972295 166778040 758970938 775536640 718383446 762075793 615735202 306605293 751138076 408938560 369763427 740109331 596836278 515217041 88243623 117554693 889278014 439077907 844446070 728830468 657315280 355426800 63739395 678640988 529502710 940040035 948068848 623465156 104163130 298506706 478437819 727462668 451961663 845142650 45285404 201643463 49416187 535495648 995059328 333428707 720825408 737539570 679166130 669004679 824992294 278031163 912342963 575340629 914020788 96521226 779400820 649593802 273094799 546405590 806088822 192076108 392862852 439351518 380460603 840816273 390712170 149266415 742146928 619794862 887765878 18756592 962802312 695845139 528021756 677167804 341182729 905938654 644985299 254815144 589727079 671042860 289187022 594472876 867007874 589826921 178960946 585436343 178548468 144440767 482447214 534075449 776514342 824713699 916513480 234067916 510374469 116851387 938880786 541006885 753224213 781293535 148488454 79818230 854508678 759379774 252924048 676664076 577501815 17741441 965864582 309530978 612422183 219060831 235895043 998016222 976119233 934800687 364612758 462284366 47245226 244523980 346451036 693393761 155009291 41139702 797768567 928187664 877564759 324532742 762761848 466328914 520174425 90112501 858094246 79151452 2000789 68833373 796144546 232749610 545172819 444614550 559270324 230100717 855652719 321191200 375933988 166085743 74582158 735867786 116843466 158749026 106334017 277909522 336445880 617255077 58531830 423055625 845479265 88689449 75596955 281596976 778067297 812042051 941896876 427348148 890287754 583049394 953651020 106028162 924023797 627329790 320233767 397575405 890215263 982999234 785275914 826332588 546990058 483319556 766491088 135750229 232321601 729836680 557377364 747142788 657522517 616246651 968140309 328789682 455701778 847165859 313881738 410113376 931168474 267845951 623209619 784442111 103599799 361058110 122591467 30346925 424418481 640442650 80988793 531968079 480033605 634780028 472870130 722909828 124105039 799423789 235723962 82006650 884793716 45472668 386138143 476079210 679253043 903345413 890817432 808525028 537119662 634584963 777617335 592050713 820687553 878756193 902542353 739933184 852633862 322758480 642580780 6718263 148540184 311084836 183812735 800638562 948450974 412296445 961710519 924263627 427878826 712722323 983682402 367539961 108940490 436237952 311468086 678341151 493225155 701854708 646598062 832389831 278198092 437737021 521184086 308894672 338242865 967019242 822922992 672011131 940849485 91452993 516446908 866949317 874582866 819077661 442679709 206481792 632238480 476520501 663913941 137753837 983274033 254952138 271050788 963664975 473145558 592016507 324432057 695485605 218471304 672696379 299558416 883321949 608798356 970698104 80005178 463354165 304521815 462088087 769239128 765484921 811361225 409352511 42761747 92895109 468617853 745557127 891961159 143794532 729780792 616591903 285367474 323468038 305597791 455469195 405135567 125225618 569957467 552347789 451600651 775210257 757023355 233253764 519957468 32519923 982288433 618532074 801502289 937153839 450319974 97607188 150987129 198595348 222908840 780912716 545618707 302919990 633492656 263667537 530839697 94826470 671843133 913637750 611478902 176663963 831475718 74149090 710911973 696376917 719906411 887525975 766122304 416990424 144783167 915348188 917821751 990338426 338437153 125946419 433447388 943985480 473197654 685341927 984773271 765646764 55684438 565649807 792657236 919514994 739290809 299966341 602050784 603593237 26912214 877261599 518437877 146163087 175296364 765928172 531466258 912205608 186410584 190300506 157503808 12117803 128690515 874081832 852582024 976328995 399257865 81735546 268196547 455134135 431246178 278226881 257092545 570404491 814899250 917069070 151522557 418820720 472275201 861952099 964819101 536837128 600439494 356972589 253860739 513182023 424940553 175119894 55069205 869014371 222859547 199854555 134360033 349587607 333742586 656254052 622947839 881722808 521875483 154990453 54045350 743083179 876802673 888110854 671459305 51434535 823344160 684889356 821728654 235579748 934395558 835993361 873638000 876308515 636839442 413995051 44952341 991388090 523915660 443405364 912583438 909478524 706084546 688134628 827806573 447017121 978856465 343524283 842413715 656142841 952489557 184011114 683866650 791641994 91898211 494159154 814547142 418261936 870727633 567063579 747308192 79753480 299216013 984644470 678827581 841531962 532115993 333193477 123377109 181727810 807014122 287288607 516462005 701887484 305207833 486293989 211926915 867097203 339446378 769724931 706066700 829865831 242861968 392925100 618028468 936007937 400919892 994310287 945556560 280382798 234671486 171170721 480492632 360525800 114690727 352140134 514266336 654556581 642351527 913617156 170691087 12644157 988056680 250236341 364154815 616139682 965395595 803701314 52285004 345599614 327231058 509993158 968320273 601413970 193788052 959482836 277014185 962977231 622395788 906057812 995999293 387928734 553805561 195213054 916550935 379826146 175197164 922264652 155223346 504620906 366605804 565009887 440526966 930518934 434615461 229049112 799466242 162788936 993791208 910158121 57395448 32893592 220611545 362096645 131336862 934379969 867912301 381887864 540828044 215757416 50401700 384311432 51442690 648959821 101534911 57438018 409695998 106472085 483706943 410870898 425514313 977687431 455660004 494838791 59933396 332884000 445175557 231763509 394367711 744742983 861301470 478952150 560054121 680885449 776959051 354168248 253118538 419865795 932984098 811869331 833865414 11093906 29094339 740588584 144648676 323724351 392708083 981181739 966840629 893142837 946440044 331280551 955792993 688102700 941805517 82595256 468131770 850227708 341688461 362961993 647352677 910299755 126087170 994303381 586536203 55983584 927367449 964008061 90891939 480159642 198905177 369140896 517960005 824176929 720001841 390386235 50764309 487868722 98400959 142453183 368224392 746935655 618999836 651742266 87590050 96888554 419852137 910048594 38152552 738851033 558907129 122727020 638752201 455535499 35247353 710495777 289846989 973507261 88254963 311284603 159054935 187310215 221712107 732286687 336004750 323957238 379224330 141812819 492774939 159237507 396442681 956643611 381762669 133013505 396834041 593143318 858552798 559966822 57095071 120205418 332037820 556401748 895474182 137949366 443902258 742067328 741726109 832445100 916616871 636085089 381177979 226846381 86727832 987236326 319501339 969838262 506682288 274366915 268787896 390146680 894209018 648337257 801615597 963813290 633010719 310628744 533627109 961580543 351387633 290197815 947509674 746816433 26566002 530584870 795132499 580143628 262220975 657422230 752169755 503339489 765797321 933813981 326012528 784871154 562207886 446537532 779864003 636814605 564910701 223959958 898574430 606202004 182000591 576448991 864972796 166198219 578139223 861824982 594667069 92137522 98493718 425866233 829106506 222081048 743052838 434558486 514643666 288411197 829844828 968702257 740906427 371111395 729031088 831052970 952279844 434658123 206908769 251710195 559779791 103373364 952160968 961860764 576015760 552768273 719973106 575219816 735555787 559350291 931811291 503000447 719875916 633600805 786062587 658827951 819157223 697683494 4652288 438986633 685045519 407284726 180689960 47967904 259836161 205089947 905573028 210065182 967008553 37928343 18915878 641781586 964566809 757552575 413783357 619609151 935402482 724160341 200626848 558568579 719729839 707846764 496794973 988738451 71755767 249788945 963520735 65445323 887418506 847489390 97326761 153932830 972778383 823710388 142810534 148667485 984241199 101440307 823823873 826339620 224942397 906154880 185934259 358538575 342796203 303664862 207078136 85404103 447880673 8480322 156674742 264807454 884110568 523299205 814852408 254553922 201058137 57479239 368324570 171217857 284766216 278559568 600070026 449443674 630896964 290493825 715365884 531776075 54753632 933867423 158905899 816836412 115658022 933240155 642465841 531945716 2094899 458421058 169219311 197515354 864794021 950080377 497928224 662810347 879002211 369342873 154030382 697595631 751951155 824234116 956567994 897715452 92683283 162810356 221710222 873161757 436731332 279940426 478355356 438496425 610858261 773327446 462251294 871670543 435342675 635691818 926927505 593818210 534239340 299504875 666663475 857936296 742139746 208187297 236782053 560529434 658308184 727564439 577084927 342169932 172605995 651412494 977756642 339619436 887318984 649808281 323319390 836777829 657849736 351961681 268550266 264177449 851393885 536987705 690088391 697492716 381806344 871531766 518729801 302953119 575959001 166471406 358000345 939048699 597106729 610403359 246377818 185653323 521131252 136463004 303193534 883899168 754989629 613065394 557202939 830458290 872998701 137751595 970206500 394958522 697089118 867188155 45747369 772253305 428245139 473370300 464798185 531308858 218011689 499825454 660203120 818507640 448334122 924600874 154265063 72843971 454326499 367994446 269727643 769108749 729615423 345413710 980873396 680921452 291047787 898674787 793493641 969751481 582242579 123081838 592622480 647174140 193960203 420396280 651101378 197576778 219214863 827844875 611507989 576117667 961231529 784662005 588161136 855334983 384023425 920862224 128190080 897774962 971274358 344216648 338911308 94978554 698107513 391626499 475692547 842587609 254265940 423506742 567202338 306911938 447498841 411554858 570246196 628813901 899870261 409208641 764097652 498902040 112614299 831435237 840812097 144389784 680162650 259318997 942867888 771869088 263383014 567439929 94317181 513841585 476311304 368136979 824677920 826287791 927915126 142236840 853490246 532222573 595385839 76581625 677904028 584152727 373719992 124730768 197277823 971011249 22684876 932924902 313712526 985401272 13341754 108969199 662943182 472600657 435190639 574734899 419268318 102543344 416011212 80407231 566730412 418823298 997586438 499590171 527886720 409211762 792217469 945501901 580425270 338912767 927608670 502139275 33146551 709621943 408932468 76177194 344198803 74431328 528092783 190677597 278344100 56892424 316331093 870793395 40254703 489263169 701777631 262457055 246426483 131797943 815184762 898478042 494464818 64743227 450788689 913087277 703657726 911826028 249028804 202937766 780803791 927352187 826524406 351589912 391704822 95545703 257447529 356084664 573674206 591718307 347094758 875637196 335842251 908102718 774014737 523835576 863000999 595766613 322255105 704092955 28874268 60768964 766624564 788638135 584377504 408057151 610750665 129346233 326957226 895928557 44342315 124700701 296565370 830527379 351635274 309792313 63061624 178111031 898897681 733551778 197005591 420846242 355006732 31295633 608763637 630945264 95466615 182304118 253296374 317319533 407073351 747360695 414369408 989989703 177297695 35560257 572056339 151800164 416403548 285551351 631385767 235292732 734663777 705763553 618073699 125546636 675034402 112467035 588342019 116621963 698866883 431462422 416433987 691864290 660055975 964309823 143249635 152889570 478874277 109644738 481964171 907852387 399986978 535466481 773895286 10232288 41041629 656828295 798608201 928062752 924524027 477249128 321261536 60011717 946507965 318145489 972488856 85141374 61193400 32210630 264436717 442482945 539595718 768245449 997038175 982032752 959572854 785876851 641805153 648506681 47128950 681375741 477908729 320867626 549232974 441307356 701245094 471423905 634887735 979185529 835699206 888071499 134062321 847496802 506581348 908438377 199256482 938793764 564296591 6042454 7858177 642590451 732965066 193216238 887735737 700868202 385118206 949544335 634516715 15470148 725681785 89730323 617966809 823387537 203240085 894963559 46774468 549810660 18908499 583611934 144226560 741754915 199162578 514492697 473212911 437563482 537359108 438677708 265746153 900345228 734930073 823667333 679663671 744333131 313219928 64123978 264030825 826467254 534769932 113936363 973665680 798186969 429600560 906160083 211741624 742251815 463987925 325707285 308517598 263033537 879581725 277052501 625763938 896676344 616296891 730898173 312408630 661858082 736355385 852999475 694519013 770844282 48079329 659661533 600022664 39659647 299474631 644861983 568598933 823162599 529079785 760724956 756227358 795289127 126770630 557835506 813530477 449392310 157133735 413227215 671746663 770382846 761610376 786549124 222101943 566432502 355583320 975021165 933642578 956605255 667588576 678575896 269770752 640427040 416292177 674873461 153477424 769328122 703324349 158655011 914639132 388292048 607661767 886237868 312917056 383435320 981552997 700016511 557394618 456966945 927422381 287915246 57117092 714688576 384123005 378747621 676113742 676268495 642070834 561699187 939703423 677486388 860704909 92296550 927591680 551881637 677473171 418412054 651599312 9848712 858736535 324201162 185968386 477472042 740172764 548828128 135847762 17855981 835180835 284583700 955960573 489956397 244270825 366347599 81969067 650961823 253655169 962221831 629400638 370685846 484705348 187240239 368521221 674050466 19836110 299397181 737403793 751915594 126241527 696367226 24512264 954161796 604838953 13256451 788159281 670329956 226015439 573332081 547757544 991587481 404266947 432695934 465519471 936886934 195313113 998893945 304799045 513227545 596503373 797414786 100721903 502654457 97375247 346690871 313906708 21182616 606526312 262566715 904033626 708416805 125249215 72466037 200894744 214105030 140739407 297782169 354339690 428558640 930396253 27094232 572332805 927312520 660868925 929072586 984208590 943363104 854917338 774301599 751159831 268804439 375572862 85370179 213936972 804825378 937864666 584331581 477745128 388528712 667239107 309970891 274579608 744956823 33770417 54503554 814186334 803619025 401890905 501812502 131719642 879387710 597103397 463991234 353750846 576874464 140423297 686701317 847772881 445790064 627040409 546793002 942097876 692454769 158263043 397044904 661662503 193473223 204334164 822632495 255651543 322197168 542456502 561008735 906316840 494856820 874318618 285405901 684529756 541047437 757449838 889931817 903425710 168644504 491910022 851749428 953478576 957821634 488124207 698113371 366219625 195117332 796821519 985104817 828093422 296041044 964513566 715557957 644070534 615197490 404092416 924079085 448440535 839658131 758861559 394782980 554283492 461224512 941689024 523232287 259722778 491162642 119296728 840174389 850557236 531098059 510103493 622320593 601925664 619257306 474354235 297883419 309957439 444969999 14444082 883627949 748136916 393447994 463393675 300543312 359236680 745436942 861691636 836681735 238128217 471012733 409750446 815173645 130504362 391040161 729995755 17612741 605649070 74350658 916669980 633404752 174822348 399019502 575789227 797362107 791831328 915394881 162908470 306468751 88724611 278216087 578799100 51623502 131561673 942964138 265885270 140801909 779408972 154342504 239914160 73622345 531627328 367005033 229082058 365220574 163398422 395434422 246654311 12808933 537587619 918052437 16008510 371503921 659238696 502335905 5916394 399436852 904672052 103984366 465008929 845349245 536715812 311230577 612168624 706173774 235800839 599426134 276210446 821029249 389899693 735086681 662241387 587922967 513470412 488813036 490020504 95221986 679653730 513366407 830626654 791521833 661611703 494919952 275064956 679989520 305973686 459579121 177012952 643789484 212218473 556503306 505356427 595140681 195517599 409173266 563051946 670133254 349094479 758807028 536350738 947530662 840182116 630490009 963160681 88041866 595635366 47711481 314831577 564332236 677231619 245250667 714326858 748991330 366037061 183074251 557070285 13192505 667060170 234156640 962390022 536721629 712564738 164157202 969152025 672644045 684010866 429926359 226819940 76924889 927445849 767737684 640459707 823147941 395722373 788507383 651349218 446820727 272642945 474098325 40834698 453414079 912126517 697512387 422941545 420133649 188427774 462871386 982153449 41155110 261742806 379646765 227941163 644832232 975084226 107137748 382695962 155062885 518967723 310774210 699597696 25232538 794823583 108499597 657577344 566616280 739094548 832362481 391110843 460897104 987325313 136163532 771774788 722160244 607492833 912057030 171175450 538938141 242806681 474193698 144887666 280588528 397971483 378093895 467242374 226904540 534737552 471755253 588153780 152461226 27558782 940140885 896939758 874617578 530570103 590802090 523898928 276340775 493305531 7878007 760111206 487684217 215688289 930201364 804153864 656073605 213925335 73020350 378299114 139852986 95647431 330876338 556530692 136836056 760460459 991740364 653268007 768399805 9621890 55449213 100133946 551887748 612686721 541865873 83780414 450472477 478173858 475486222 411087015 953153660 651503869 327821554 739805434 631212229 408011796 112717285 24464569 636120950 307866136 557395778 363314466 416349364 500414938 262631731 713503924 57453527 941180564 829977722 16031096 528322374 668287207 908498688 582042109 269270427 511383232 87196671 41769894 910290999 15646268 741760510 2314277 906757111 216715314 59420753 359526825 411122928 469115716 350530711 181755820 334833323 568609803 239367131 224716612 774227488 471505630 118679079 799139048 791382927 82530784 115256258 606728563 721546189 53915853 160275946 107202369 985154500 579619269 872383367 531397200 391542844 197184450 176638038 879145951 724271025 798745508 182358478 488342510 365193137 25794928 936648401 220193781 442693078 695078178 642226372 375067576 363862124 726603702 571652914 650656889 750964571 838331327 783576285 590151871 332538044 369307807 230602390 642704963 230545006 266585639 34400026 715965639 213783431 776339809 853418955 752921913 572522592 15900685 835577940 237788159 321669310 352046 943699752 297840322 193152428 906721980 826616876 107598759 375883416 260660572 457592312 592830969 435104380 472300356 452655467 888504919 890043595 154370208 983349595 384157823 69568905 281260557 297160638 106418486 153731252 817528977 385183117 607125427 643587220 321598843 198783839 110621621 89276116 845360681 675318356 968568935 9473886 71097424 151049077 33677932 746525085 405769071 91379057 877087737 449542956 455457723 864184842 628677374 296046288 429050995 32428528 514244339 129761787 418957429 480390561 590087012 889515633 565455459 928798782 517821036 555436794 304608717 612055100 795589669 444509419 473660688 384802768 403738240 987244090 267571495 467210297 69162122 967045312 392293775 947857390 118715595 125153081 511423423 24829625 279416197 192329615 324180181 427793270 13555431 521530923 335251174 943444284 803361598 488622273 311490512 115895128 32682126 950951552 977461717 618125393 766055361 923966504 89220068 720525870 489655604 435490895 658952098 512998155 199373548 518767511 284762448 174968551 144405950 117589845 599507139 979464276 211152796 74760947 256733281 623248942 942649388 576671965 869087690 431508210 493965951 939445760 648202545 154504691 748410469 394168864 200911778 281410569 243658316 752278982 803814537 366170384 719605767 109433976 852908676 352914591 40717167 21921598 288983466 190985676 8748198 919541923 134550943 729828150 867104459 479748672 988296577 556127874 741626438 21317133 343809820 331181882 260764777 816424564 115795404 640355598 301142224 892695998 397352370 376458194 389215435 905388257 252719581 653115806 72534617 695154868 231716883 789744227 922203239 999545657 627110540 846502730 854500947 15474129 883394763 151480187 607612642 314441801 191221717 802305033 162665839 735497849 622106263 26111647 30154222 281895425 15191685 189744633 234922321 704529869 819839160 912679851 746880432 48226354 406788978 231032567 28743911 80019577 437319173 932838496 846264878 820379753 543714312 261396970 929286075 519510529 755756998 841825016 70236538 633794253 976991303 974348415 383813277 374162283 551959814 599871120 744223842 218434534 933971291 564144121 725389421 145404141 357501863 634946832 33705005 579737303 134648345 404841480 211465433 574469651 695465219 43970395 264755919 713271232 575070178 605626359 215315094 732125103 517845014 249157086 378862890 149550083 551242786 25243747 740514468 853344814 357663797 502275640 258982984 716511515 924910877 276892063 918247533 193492663 139072118 187649701 371198226 840869257 930587881 977441255 470740679 611743522 530817440 414724467 778234351 342965886 83296698 682116053 834841392 395970232 511978632 495007273 532326916 368882159 497791077 302582702 678116449 756264198 796050076 690626319 675778343 500366164 826873819 280007997 197543949 204361674 931999168 468649215 27066465 61028017 421044948 640229858 699438661 905424246 22370088 258002650 473523261 30773602 500437451 675479498 747316033 343682407 49514299 857896625 418748771 829684187 103691459 971900443 525081875 63790739 357048047 772770387 687144178 643250676 137683992 369149319 682128813 921723363 64848181 910845515 135539966 637879221 511864620 795858572 422565401 182255437 81110771 131780901 562895362 220866317 203485525 812594368 424285177 492382217 148660732 132613295 601411683 355479077 577332816 797631712 479429141 669370005 648187758 669370555 866395681 381882579 355546198 178682339 241990772 553460606 673465254 693769755 379915868 879979368 972083476 507856176 985340120 703966985 951735197 867706317 393526388 355399881 614544257 627954301 740705886 747309037 606560739 235080633 446033353 833909017 544065702 545496675 127055199 630272029 123514234 294454951 816151743 914935115 760616870 196604164 124038081 457321370 800457979 712551742 109970097 318073537 410919347 698823309 658340337 370081456 405502073 695068501 984860181 671589731 713092287 616328626 743600495 496128512 668586282 91857744 403616756 703092050 442571046 523386693 100582469 129030460 801830666 659214327 912564149 609063658 78853553 878723349 359175107 938755079 387247322 147912466 641861860 965990331 30206886 760069276 330028511 765680529 878029028 135420838 12865357 905125784 989360599 366733748 782118215 891286186 639239739 717828599 135185585 998595095 316919345 504027560 388828942 100414889 301777088 464826886 887691177 962627743 175379522 201201686 511941600 459672888 40631351 356511906 881285666 538447004 473276836 566621244 230670307 210684850 182083254 550472656 126629305 514953460 606903638 713183170 558516917 719118557 575648168 466169638 540320256 718791647 480670445 469653951 805964374 834824594 36240048 695074325 778014187 512476356 367644945 550605754 538824269 127874305 118192302 504847617 578343073 220567484 167622402 31586081 670902438 675740824 734858641 944527895 792358814 849895255 59803067 963212913 169394283 656806303 589701035 554466242 899855186 57611523 684869874 711430811 254090856 653352016 668921509 987574160 339621001 363945068 391999976 333655384 557528098 703231417 63119284 315068520 126929027 255037760 673998898 235529684 770627805 218749328 106294772 422286768 895733021 771318679 839488379 683047386 148407549 336696172 343336083 146074265 415147658 883993789 606738528 648375535 919332702 951255925 415312937 923882228 478323892 913073424 213398604 325755826 190875653 844947844 270111608 312592556 989888803 825267087 580962041 243043106 658107851 254820809 948636119 452942583 476433332 577183784 76913546 985241844 681764038 254463530 262028858 579190737 371331919 39721397 407238188 911897815 584294006 917670548 808498041 598936866 180097839 629001999 113062679 663940397 580063628 476626514 956624352 295843552 724543728 479781184 972067016 631908397 89620044 335253039 99304436 602163243 441597497 294531537 262163489 354913013 136225163 871718951 211107729 511500674 50545071 559787016 883449640 990180198 882474166 779127817 898825007 588690102 275978544 36129611 596263087 159958970 492385452 10666825 226856371 871203727 660951826 654465818 269549030 873295592 108201420 577860518 316487373 290737746 903647339 842237822 708470252 510098958 183369076 571163788 91017443 56789305 437730970 284988850 678463652 672201656 710161724 185145664 379552983 394571448 18285094 133917978 768769424 820636042 328771856 162872071 327559032 926549389 819967052 156392158 738407471 595888895 416120338 806335969 779643443 197596941 88382526 519135353 570377634 158218819 353025013 781782644 261554198 170161072 958500609 459301301 650221446 944390502 243696710 903742471 158301079 76405198 517655699 849360894 588124028 764885817 847494158 742130852 239229169 517500970 740654206 210150494 719097425 831666362 832588138 662507374 517827245 797421847 136465974 411933076 185497136 58409377 368320483 556795386 670358261 946273061 415469074 583999325 554396265 138262652 204862725 939721361 304118288 138940669 325900496 198882768 875989626 451839051 510341420 486408246 892279149 760444356 315352287 956942562 125455827 416547206 496946449 283963051 832655483 134147600 761890966 350141529 410344150 710461716 773653356 547639162 513494686 341986383 106405835 180296316 987390584 230187858 164314411 465086424 284697719 723941687 90946777 867964112 333047425 450305904 369889030 536037178 332951396 335574349 161912691 136570456 551638077 184492165 320491689 621888747 442187898 778670884 59461920 263764824 605201151 647662292 424528023 988388378 661117727 555676761 815411074 410022050 211516522 109233261 614529428 734871662 493510046 839010663 762311061 236040254 355652152 263473107 173192472 75363075 246296610 332571812 723860663 421343287 25474380 110880684 456107001 251489322 2802198 329112584 638807479 796797094 567850542 461145796 371080736 409098481 227001763 682624863 662187391 193078962 787893651 980081904 716550860 51353842 665885293 693988524 975386453 545889913 832328336 978345025 869687653 527610914 415152567 954660710 816883369 926947233 624659805 568589657 153879102 115133115 760024904 797574943 347661248 505417285 799486571 306970422 691337446 845682092 130687908 954139876 280540099 811375820 318990989 914010080 495351273 532945001 741500488 504206802 461968314 862620780 761965561 32080425 55446690 679216895 191540635 927196810 503317320 151692907 251939111 934818103 987496198 666192700 334453197 96967113 507081299 158590947 266096582 275586504 202319737 220355864 134583129 326600763 291587189 168839460 857290475 297736612 406562952 534445581 339198076 78810790 929333141 623201892 434946269 300123749 743081137 581057869 847783261 969371287 882646503 250053072 593865081 572326254 944378238 865148002 981805970 148618204 899265751 750017837 206483851 294637366 59584538 786808138 146725087 694931440 741046428 828596129 476308054 972016039 695237229 598066978 39690063 230426699 781980418 9128752 748382227 875609422 131840177 218029084 99097594 349641674 321054013 819054094 523757531 838974813 274270945 661126728 129561489 359766953 144142623 683822630 184414187 213938049 301633375 361556577 637176559 311960661 896133973 352845175 641881404 552553102 49292914 555633159 399278800 601456309 718763248 741945526 158651070 765084676 287744153 905299308 207906979 524969858 259606224 829525267 536111709 853669680 384066302 940631933 147329944 330972868 518097579 784384283 462551680 475208153 357989854 107013889 130787128 837260918 991115031 362803186 477532964 123558720 828033457 797495986 940565735 947566391 833620091 729884819 977786362 782390367 846536886 347213846 324109253 10238077 391727995 637885001 406239595 106095412 93391365 115157445 220550862 339161832 168211062 371515917 461873210 674271224 435268349 668913348 814549184 33285900 641632656 463322632 422415817 94249315 140806151 960182781 530935428 496503381 257931567 147052416 433478884 768556189 819808114 399139822 648563947 194756258 399843492 577700041 468361732 870039677 627576482 371852161 303190894 900558734 734922944 748788812 196099505 160379519 486869328 422784865 523853519 774970258 344830541 176493058 278462260 794448785 312904944 969354258 815981916 294339344 766988046 12455307 512673284 796812096 88516504 874868674 186150586 291948512 137352750 160564693 246792983 863925205 763216235 612558499 660245885 318387980 741615697 238422586 556279991 354539275 206780694 110963087 625175558 113228130 783503461 110999845 286200497 251349704 389850279 42564237 605612544 589477663 597744916 354465009 874246270 159584475 927146524 386464814 231955653 863920845 369271865 652258196 291099448 656996415 696225728 757932257 344464982 87507694 623351044 17867093 902045308 44531911 708178758 359426840 379492550 739100615 149126564 393421486 29050439 937429611 195340482 525945900 810579861 25518391 160686209 451764556 114856915 721397350 420215216 790772849 14203513 514234355 513051187 519550749 175155467 430088014 378794546 193373245 820536175 152706132 960895882 115372663 588594754 770101563 355399273 319667592 526904062 224088171 580903321 495527498 367788852 180918264 414504338 698451911 970895056 89177589 562917046 646753552 310379500 399074597 201726365 481492423 208692026 285586547 189194021 391056590 260866736 51812833 795906118 307153670 373632344 345391959 960253660 809981769 966946002 881647221 389259730 441920462 145269865 47581120 850891124 270631490 564043890 580960517 248942025 259517928 43725000 448790018 221708075 706204622 341821308 204871707 753641087 785083757 199917625 983850337 663051757 4638283 626525215 431862937 140939011 823996311 654317414 357496496 255310228 646282862 253362602 108209480 598437896 106347206 90978975 123982172 44436020 378199545 15278341 557706829 711324524 983736681 411278952 122637672 450782886 978805324 631139536 827258491 371778744 278448502 875596255 883666644 233214497 761787954 737495765 100319729 373208376 364436973 871459167 110317389 476718657 348422386 286594628 589730379 119231791 356999157 153186256 395229213 497746940 751866751 951753452 702510720 19628144 228642180 398807951 650275450 244136765 169058593 737211003 123123193 249394800 308864338 801471052 291211278 980554971 90662724 195957244 574014233 556086678 243343207 664092599 172584891 779174801 491387955 642140572 133354589 562280028 994057998 528871744 348198729 348324171 655139949 487089602 131722255 139559176 115676573 820415231 115483490 942094538 125503048 628806392 875437887 688915148 995361708 4166630 312506843 722710405 16365624 358480107 961509953 539802490 59410358 715355742 813632884 962680464 534740033 457002317 193838014 770201012 232302814 775201526 665030704 628412935 288660658 68213766 543062961 769308478 892428629 771405970 182721122 295772971 919775131 270608735 134553002 54650514 93602644 34457051 118467739 483677491 181201720 561522008 631758044 325008685 795367238 578554075 863891394 3610161 61872473 453236752 935331306 388935411 842496965 676514519 633955822 733561354 146127328 10623664 794650111 974500913 986824448 472596687 385223515 144425201 630453486 72945855 73826080 889852097 799341822 870085596 857297128 69267234 890252342 335349591 945318477 441560500 951486837 255125484 944550819 793599255 929601578 42426652 823425568 667976441 767841626 186082764 71423413 595931677 131245712 581471780 627464425 711326816 928733666 954721748 399233109 823770348 252058824 447359868 983267351 249981569 551728042 438259764 245812587 673482099 562110032 235883939 655625942 637315196 702063068 585480226 580112371 404895932 124246502 744401707 731596774 949345410 285295506 623800266 730360398 242999692 986374296 113427948 258497188 21351789 919838489 815476995 45305627 208748185 679087679 62495534 648890079 329995560 722460106 509873960 938878975 149495212 43482650 876742432 694204865 530825199 701386390 329810320 983733759 847194282 34886936 271642224 162689040 891796235 51700129 673636337 783907945 834311018 69336197 597712380 422943370 625356950 449321738 523797078 12552935 958471825 738203785 111799503 490324983 360041694 658246948 259891008 760033040 731349874 192024773 508499446 869187723 163206449 393260444 871588361 449469828 917949529 906581507 310771469 680508247 147826745 491906907 914228243 206049366 33387456 580816076 63031064 619469569 615496826 513738953 954524800 473157619 605583472 60745114 988042369 404656554 502803156 765848683 507609953 837710582 144736096 461803267 674598316 955381141 765825314 740739735 56402608 478418556 903504255 400979961 382986690 24365328 321704257 789808685 394687174 135677688 713380490 266290160 422471747 755190746 589216710 93887842 839411064 967371275 371286430 788696346 376030071 854685076 451456400 125949589 3360169 907019253 975115760 203768443 931447718 937484946 940217222 959758908 416645015 389768624 940587167 786650986 828262193 301629996 573248983 721758254 281013869 120353282 94245502 336297013 252578378 306802722 928624078 957451644 923590266 470865861 699568899 839188808 363514081 803106036 960044377 619686833 58900838 114179929 911741747 616061563 97803142 451211317 976090409 939414915 848943745 463424465 146977413 655735895 54247332 92565954 970578192 651876921 69600509 1824784 53945994 392352035 227823744 229288142 220574236 478609966 578094699 36027796 648857947 883466853 951202575 818929966 450901451 48634686 286882168 816190361 809551433 677939432 434421824 381411605 108526038 748515230 217130365 214333979 809765569 90355300 222342570 847192229 488257285 812683691 849705045 525723649 868844852 797898509 893221824 832573821 84893007 192560148 675512439 366617191 546612192 638684773 805105841 278620897 957341696 430031882 456528339 728051815 865434582 213299720 924949879 463472401 606157487 820613917 842709265 217744992 895545517 466045477 225477964 486721131 428673882 870737936 660299852 673771729 343735435 666180207 773782553 507863920 126779049 278984933 484765842 129592176 731584227 377634846 742139190 740909599 47353346 270969401 401340372 642521358 444775394 456915661 830473386 282270827 646244420 8390898 813005129 335270829 705375141 74498805 327783691 999282201 256252404 369636941 853772120 517016859 712832051 568143622 97568543 446240781 218215792 473544548 669723190 200415099 762778576 938189330 343969926 578642200 939648614 91671560 762704050 271434372 480427913 318419591 667773540 614167944 240643505 979325399 355299388 798073407 797800698 127712876 625040960 863384885 643636857 781018511 560768484 170604600 916217226 999901763 455418408 779896915 489772944 157759938 107907046 567302262 21563486 811021684 955732559 974214679 15037534 677564627 701289286 514246036 526793052 726253273 546721564 560316603 656879559 897709943 857458465 623677209 314449626 926311575 896096401 697993655 153296190 312021960 391412894 151945163 292641465 801688623 86324834 67138288 91978120 684235740 712351229 974349475 592316538 655533690 995031091 691649372 486722712 739120237 237120334 416170694 650929953 473012708 555985995 928510707 103710173 387652769 355111397 108715153 211675310 406286517 676497427 450599167 920660193 385060009 329516908 404989205 417899367 49598571 201112236 858169597 768776680 345470546 330619933 40789868 196788693 472699317 952681870 817955045 129549246 560958791 606766714 295725593 912677163 670617682 835663516 822233483 766627794 538845769 42651834 384215853 690138353 224482549 205566290 750658863 58757856 437848651 638217 862451828 34722923 575958693 218263292 697954361 918652335 176490203 880699148 786104833 444498437 269049633 965585827 594836129 556709111 998358886 476029983 264660901 918887252 288542771 76333805 427262047 674301528 573904139 574537350 480460629 791759277 832908757 307690896 394036964 830418864 27768264 750122321 572265850 107270092 296962103 4122385 48202556 763870862 836746900 916902617 480394156 651650913 428531164 558819591 460453305 575690459 723698989 628915424 349975829 927279309 782872977 471691708 942826897 255482414 993528160 461088731 153693158 668073336 719645143 825752572 508206349 49626110 971315231 307595394 244936222 969732851 914625037 168991482 624592190 333705374 12258445 608987609 251669562 942072910 630521290 801476472 223285128 338054606 31918736 798962302 381495372 520872177 320832819 357886391 270850321 215351173 205708951 30724203 686278148 196830812 711806587 181662182 108307562 406198084 276647053 933991304 392558013 715504224 957862587 381735423 696118142 200845909 828243211 613767846 733446485 70797238 983032279 960281890 531303018 287349943 681865623 992131071 647567407 897126580 250769117 715273452 269072155 14604958 667592639 833022608 173605904 624279892 16294421 175493603 653341079 361567521 365331720 545631584 987550554 939184116 497796037 382149616 497923253 183037966 293664632 615708179 334950356 694706090 330999580 787150056 393774510 526464703 810115537 712235973 361642613 740241531 337200561 363759338 520226838 821401980 868246743 212963039 987039672 254881778 128543928 953004834 562942014 263663664 990613765 318725773 653018476 877985586 592978725 506683248 35561340 152705112 922580141 83315601 51945300 568878509 109238638 33954328 119411483 479257937 549903552 968264755 263211069 374551732 998920175 308618047 824842873 272874945 713000371 793204457 418130370 20711883 31585268 189257423 904369979 385049663 669315722 628105848 628321155 268023668 532122416 388071176 160242786 570646294 218952027 407312302 206308471 233928220 395500854 681520663 914980703 182553037 604589967 212953970 650847058 294013524 862335916 592293975 573686401 640988262 640146749 216222115 710262552 659456460 394204636 760573012 683220683 353390349 932091814 542886501 875305286 768539375 411700623 871510104 261821316 565513129 468373370 64515725 767841371 281077707 446851397 80594680 758868108 81996086 426507409 122602118 390132445 422791407 656856269 27718497 473966705 445057642 958316443 624374541 539546822 912775950 377655323 605178667 308637293 358519455 465408325 978103438 932629707 954856334 666318032 606515731 352847155 873187947 809715419 127077646 778505906 384609831 451677923 855641121 476484185 821966938 625784331 848253518 520303392 880134236 804557940 42997928 262069422 617503023 541373762 784672209 345589421 863560646 20992959 238719692 152771739 445411166 710873047 310263674 404567393 437376031 887256839 547322627 865864995 964900331 16189860 939080694 507249297 335903057 463837081 775903506 339970371 653539705 913414501 542481897 39765756 912427000 336609859 618466036 48258300 509343164 538179153 958813873 568395193 284379989 913307611 160026916 976159811 310798525 263908924 952226763 12445332 915713785 633621036 814224302 773026095 906605544 84586770 215893953 915953736 948571930 47352608 542305994 986250032 383106156 560310773 27694234 342222004 652055253 544705730 210429596 713639630 338722057 382756833 892735109 440220908 693598079 120613300 990822868 424199481 766864534 561812459 768078152 864281657 893462476 275648265 26117077 700989937 92054236 185600115 900215097 630006618 495691277 53060732 940140580 757730982