994 801 255 393 423246252 557473216 516612843 749367951 811343841 966696873 41598927 54588619 383190466 608844415 439513436 637480361 624239532 57856292 159881124 393876000 534119643 982682450 672687641 789200382 106330638 675228421 244639947 216578988 485688987 319236034 918731498 904311743 886615591 244211721 763286502 937187619 598904740 920411814 486729373 142784385 764421298 87136184 966627248 324931314 590321996 754148674 299999509 63275510 615370860 901905639 749426042 290558294 31460350 413194970 683554445 143337173 845954348 291557840 34921301 952761734 126515362 893443309 836594390 830049040 140807672 64444667 970260630 750257242 722583366 442663315 963421811 148863163 520600287 115111990 285951459 164612722 980628292 170544396 75621904 634711789 71867823 765137001 516943543 181774631 817634467 789777049 64190096 188433317 690165793 781672758 290187083 332691709 498136491 392693909 849992243 771760005 812993500 408713509 557311023 289512739 674451323 977247061 988301517 726831205 150456479 756143662 828424386 980373743 173111328 799133047 189421695 604936895 677944293 908026224 839301056 469102768 860313570 135636282 938972038 866359187 178950769 70674951 821268499 562842242 499484633 374236910 643395287 809297024 797627398 500187351 255005780 527148 5270002 202998058 923032043 812501333 460677421 73106050 738264913 645048637 797803165 314781215 191136326 261790960 308062635 311466348 389110889 240702403 627516670 265195947 220111448 508842624 297617867 56934794 843964447 698186837 699061696 919093566 727443992 572234766 388641787 973296317 309494582 616169558 753112903 664658774 286617580 886809676 48430142 775099865 579150403 180789381 850404787 805644239 611261138 393437308 169439396 56136508 675564272 253536243 208292845 571381555 970989744 167914790 767692643 366480717 923247465 573078971 47492336 469122196 686150739 689856329 190875011 189728185 146469624 769138816 136132041 827028691 644042067 197218446 738976753 228685666 668602149 767989824 4351069 383115778 261627800 924085863 410198373 381782640 14410996 700410718 282256865 910296011 651574806 223933770 923177171 264770927 643216249 819935790 66007083 534929435 858021462 731877729 758763115 221373159 362048511 358745817 845809527 622544298 738584816 394036939 354411099 888225095 776114695 208053333 440823928 414974073 944605765 157324005 965557664 662739655 317147835 554588075 418539228 648895508 94524149 279919699 234187158 439204302 311701164 193246029 9837406 715139265 359128164 983735161 805027834 258715716 620075855 715443150 852806930 695983672 336119322 433307518 399249759 584868911 796331421 462838445 640100963 995059993 352137471 817016724 485077003 246296007 456055577 158959922 92037222 785838869 729273508 389658236 176479080 403440364 826791194 139524079 350191065 411331821 503810713 897829168 887539065 167301250 338058465 327513467 30556938 836904488 111560715 156652982 918908982 701876860 594504433 564733384 975533565 827797495 175897754 75874401 236187212 13332989 19900062 417311954 706627661 232156646 881136224 407747569 732036612 845900934 98879349 478008649 47813140 872420188 532107147 35330397 228925348 845443861 119640232 420004792 444228768 584077817 907877601 403168780 560279204 157022743 343114103 467314073 804826358 46557884 887803950 761234491 431093381 53369331 688098409 614182398 535588214 595471507 832819810 636084823 748939371 884414654 892872408 883413238 866256476 150561612 114446612 13249648 272644539 779378322 716148196 18887490 424486808 610409522 578749966 711580037 492174073 967738800 174698003 4453401 664456545 515968050 331313943 511606898 635738664 913183176 749022321 408557978 423761299 333848152 381943500 580828033 549270788 906345755 81873364 300214503 120590557 15879748 495331104 907018356 420759693 991917880 734981043 250009301 198110861 302254139 900039298 239570237 534841193 901036795 222963135 158828126 248294397 431014081 855342340 33097389 94513859 621464316 10717098 282342723 787049162 63042338 549425029 908483531 771297200 257696794 836032467 219698396 789108253 430408408 824241639 957821536 31807971 56920204 416073441 219880984 366205758 475980250 688008937 819536746 806050575 749264840 944374427 878249411 377219609 12364160 637854243 458308418 275962991 430546631 346412318 654188962 175208973 57423144 103236256 482792037 52530808 350464700 683222478 890651348 850921843 687036451 4315233 910247699 309407485 550698959 946864108 94453165 951677581 255822648 486990107 903429336 110192729 621564883 706960645 303121967 354095625 508462653 686080142 291999998 777086243 805275843 736611616 771335768 765720458 666704959 176043822 781018641 786225616 723912201 356138621 220431517 302966405 254979707 42537011 284117856 813645591 543102762 241618304 81540039 220095125 829335186 576373494 563356192 893186529 124815911 89667264 43135514 832791992 673554142 131234336 539130153 98443542 311458657 589766441 314093479 808310124 265439645 863735348 851966688 993983150 113517900 616244963 63159591 402335359 653120116 495505244 396653727 937722425 746023920 925224418 158040146 972951484 699358236 718637070 213272554 183211287 85072859 81739730 93544488 58059411 392449032 568276796 778056246 564337100 941247139 210961332 969533172 185205308 773863360 931015119 614708022 612829804 68591600 885991868 631184031 701885911 854316286 867033067 766092930 282842426 186280237 839211771 522060394 512724179 700180706 353168346 720392581 334244525 583203098 595171449 125757559 151384270 645550669 630839074 876301031 822334464 461914610 886982052 885920349 749275049 869728344 270434266 429016958 182137379 105705230 306232749 606392917 122381053 231233831 60195674 860181133 234464050 166057849 636243889 604945333 558477554 587373950 904800020 92244814 214288002 143625042 752321645 958343894 971085739 919263898 800270068 554280464 370297419 88090266 264962780 916203586 628464861 2993980 755027040 12452120 332511705 694044017 43638045 459192375 349006262 128623424 808424846 947359891 97430296 81958477 672656815 850468702 939042248 678048989 234110461 226802470 786267317 946253463 339408871 613392565 207590431 496909715 317663802 438378446 206158935 513605038 342012519 227254165 829221918 247540359 923052697 773118981 840399857 345760125 791134550 940612389 827327487 810918952 244554307 980809929 86685505 906667132 664895399 621543750 592988183 162938523 228600529 526505077 83183337 523822843 360984491 776031422 951215026 947725876 586899281 685651763 75727545 124942263 754113461 224557340 5962712 524343579 802524830 428188283 765530698 541030984 837121352 743709519 852951975 361956944 386060239 369847161 147812236 290914169 875273151 928890434 945810072 532259169 356296178 843288044 516915265 638697190 700151043 852219001 85718060 374846411 141253749 428622930 926646253 900021426 236574264 591764205 327292632 299604168 654502574 281490465 65647779 851262560 491296199 118275300 55550779 76897937 560655725 3084339 792113321 990206422 77801988 749874583 282276364 782532467 961705801 112792388 594178901 702094471 883829318 324768314 603121335 949658407 911525783 852462693 398534604 919390021 594125164 685646726 482026650 125814193 768165415 439616236 614419993 581558156 637360364 654888213 408943025 963517686 593093327 391626465 545489061 582025153 54158708 707475118 96357746 213064897 89738592 826202761 958244636 295457970 823413583 110966100 565141708 250648022 158214028 138564476 230665539 279592597 230014365 780794226 267470529 658615905 709505739 836855734 468204715 917143440 692514640 845630137 618757481 356875400 70415601 699429905 659512 97865766 455684089 920903177 648960112 869121799 811807174 320292025 309340036 754630530 486658711 61731024 972451855 923140143 558861798 237178132 926502018 369215954 27108917 170831517 263438941 332103995 150936135 403867971 652381334 903054151 663493683 471088359 804334182 228397215 926220620 504345445 110074440 429488232 452172820 514313700 181410257 676394522 158509386 633588399 767154394 99006458 733050968 862223312 92038632 205175115 872695851 567766869 429233477 966169613 900193420 394548953 716277748 957852054 890211728 139456232 728873261 389871532 606885400 360706963 124164865 173929671 505088511 604122821 883648173 544463950 675121769 377480313 481328836 463135970 961609206 64795901 155864967 433117838 739193100 61118768 65109265 492502803 408338961 369920706 583466401 994401314 706308527 948241014 480583644 583997856 324917517 212863074 899131650 248074723 41237018 118216238 918861114 904146419 139530181 774000465 453312458 830510044 298291627 482813277 762812051 615481655 229433371 165497993 523437139 529257999 127839390 754950760 282189428 165097159 692792588 819315051 866179330 368435325 150706698 944812975 967662055 599948535 999241230 580541528 915246181 224755840 489970080 395201070 537754028 262875813 371057726 441157099 412266778 851028095 794672423 900950832 91409725 886282833 144626977 769690775 338580624 530942599 246100949 62794857 376884882 454182721 15389814 296631580 6579163 779490678 383954903 723919198 517822514 878562212 88268943 854571696 122391424 75171630 444479345 921428068 475063762 955175008 400245114 66519835 142828420 263353797 827217439 928969159 585988734 171249179 668433624 437820103 923263332 664377335 533526536 258819410 887087063 361709850 420975457 888235060 897924686 833369562 894268439 569695294 289126936 284442981 756585908 517786393 383825557 590376437 49000722 80909727 61664937 405004310 613958827 161330720 916196087 895327463 577942238 484810397 888413062 252277957 23022873 429757454 74129221 693010168 19972066 772090425 641864862 50735373 680537760 762328280 607506803 615163615 312649647 746103029 417156606 342008562 855083752 429303348 899276672 999766753 902558573 771620704 734302885 144968439 970383575 812280636 22099771 354785770 687665752 395261873 575095044 622990164 734023906 540201892 640520420 686777515 177246621 130137168 870832008 456438545 663412385 715663533 486023427 230915394 268988479 239900729 282586903 222464724 114594341 538099660 378868664 553815328 11447613 381180227 547010663 724006206 91172944 505144226 329379661 477621161 934058296 425348353 841089479 612876608 212319031 556735236 793113847 65052181 710142722 504575351 340244728 247009249 406007174 639599287 89444666 764114608 624318115 62396468 576480324 246463835 821478049 950474339 418081951 547972868 896380321 837124963 195118078 669425017 133427033 661202908 570465651 978960180 557755054 398184502 968045087 869342761 364276515 239418228 152685054 498082640 225986696 766017892 705674786 747857504 69589806 36593549 294346628 63335424 692004729 497814602 508005547 908154511 925351998 365883249 222026656 114732407 839925486 159981085 429914941 988860170 962986755 542577250 441396664 687767810 294917233 636145736 836789673 896332556 113805930 642731622 170257670 314938791 342884057 845864108 246456832 323012328 660766628 15136131 353377025 298787884 572567669 134957141 75670815 489128093 887138745 574656238 680925549 963605624 509191192 399685669 262573132 778150825 533766125 449366495 216652393 306429744 912401310 185610508 250411116 229361602 793411499 245617740 626610592 803842897 286737954 450820692 522542070 679871045 750787507 712227359 208699897 434422848 550555259 551341911 564292706 100341479 544459863 735451248 981049832 356533229 707529629 680937461 250549149 875547493 596364532 879416524 554064258 899347290 751963781 75358585 146942399 181754641 945278457 436932919 27281406 873143408 2147119 279892718 59939894 813490273 867691286 180156653 866586158 216274222 979952554 447328251 164522292 152375196 946024174 72414735 284409735 779002600 616843785 668236800 957676553 343825542 594714084 924988045 693887907 998458382 583503865 488182415 380589779 8544927 154003979 18748525 306102704 894820658 841000726 587782780 208645928 594312164 315095898 191038209 755780456 388733790 18891213 791696017 182100151 585452315 999071642 964600934 522630960 368327552 479381150 348238733 107154781 615286137 120133419 52167806 839210114 915238334 672416076 746811804 17478604 834912224 802758901 632729754 207038588 415245500 269677965 80956078 922574150 477549187 343241140 515851200 776482702 544841250 778683689 401102013 703283105 454713787 921672888 522961139 765183985 847843068 68029302 962767309 723964396 43909994 559342440 720894908 961810583 878658339 728690639 981014859 166301364 419204900 335430457 998545017 765646320 711430179 391323610 434987484 865461840 69753999 57557979 818040912 866825823 187135138 862526861 541424480 394500317 534615754 718632469 544920649 182050939 891216444 660035321 132508708 386907247 735866550 376411132 790335318 679855540 861060865 164374063 743292216 585702049 9125015 826524156 549860543 958038965 282028807 656553071 800217595 699144176 259882947 682901104 326862063 544426968 661012284 23462572 671638854 831002418 896943053 363771597 927631911 652374869 298255900 565916028 862455647 489894870 553121964 201662087 947301498 218436831 580128884 325200891 327147486 450603689 475346722 492138175 261341959 490588686 161965885 341841527 229414517 888683531 436933737 667811144 602476641 655345248 510116307 425217459 219700004 140295003 240801929 324772325 825817871 608368157 625406906 677401469 981144690 620916577 859687866 966200540 612718147 330921765 562492605 791216997 638061090 396175574 925599997 437067123 186584117 696322975 724313178 428526092 319068414 373751588 862698911 922496002 358231953 107854602 866145397 942519019 933783920 999759752 434806650 30741477 842094823 70740931 635848256 779902948 475327845 686127550 128227471 116915907 146128252 126357043 697246165 476515076 170742635 953605294 940190991 720257171 890934030 256819722 901607241 443381511 481771253 98568040 398532074 249994974 660732332 606969207 496541686 868302011 200195489 623488669 582876376 28496952 366240987 124132586 325465269 612569323 4592164 410472654 537168370 75483942 970296675 448214086 405993671 395418656 527132461 660734031 156665659 749019696 885621008 55236394 953956884 741030442 866298483 161509880 988282163 406321363 345064314 141448744 884979850 182096923 838030158 361855931 797934020 174948712 989055968 975131149 703379848 701125998 119587878 197741682 96493113 302467746 46926122 873116845 853991709 609324587 441913086 801670746 446881947 598170148 591945968 832336675 569357438 708331993 194098934 447847861 140752009 498307541 453695008 337751947 410459269 800162414 527684628 764004623 421938735 181159434 589662309 563494306 273107232 209500181 395451908 418751624 508803837 903496257 480013924 473595214 878885065 895598596 91425806 3240096 327168477 231784368 945321138 766843498 290846602 793991170 594543468 65589287 899423874 75254848 607440446 63836357 930799794 340661799 908041674 510828985 64847024 50864514 740394014 409871064 671584407 256650922 597285387 236149717 962687065 116696694 896790105 910710308 671107723 895411724 195149347 656513986 36264568 872416542 869530564 989507800 575171412 752254825 287449730 758654964 499356442 903695628 72184251 946460996 434837866 941772384 720560315 703161299 423533965 247614836 459681989 675554938 949595023 820042669 241133128 50364154 205275587 249286709 659327669 896117483 716735541 211665716 994528152 840736298 489125745 895268070 638067466 598697236 844832790 485921893 502656912 331624141 285158160 504617236 457502842 849494477 539600069 458713298 814405524 584966008 909263986 782526798 879267759 634978198 445788882 62464834 998839482 758759329 544368980 32729006 812056826 823410678 5369703 830291234 88125522 472519457 691570548 68542170 494456405 411723130 183524964 734305 554302454 795664369 734894202 229221374 724390324 467041295 427558162 271470039 414633117 973487114 32075765 465792280 253553953 424155056 472522999 269442402 688463299 255687400 327159780 817045317 41579485 991471517 592924569 982015548 909674291 561281806 419425321 541877272 118406735 516690611 962799064 392580854 935423601 759769148 93990814 298853854 428893187 943462521 621631413 387334319 507177865 282235902 9426050 77484410 865020028 898760428 481575686 710146728 788664168 986583056 17077337 961074672 704691022 620166326 636776474 580630225 279354719 768704580 200999593 146656303 180261390 322580522 678266754 381207945 888408067 337196209 829437317 87970614 70377340 52099255 436362000 684114932 566410909 980762346 20077422 962531365 599226822 950410324 301797306 343036716 795155204 466457752 748930756 313086250 471772604 585049034 364699460 91118324 851040598 28529704 669495233 515592535 567317654 36869937 400582107 16372108 747549917 683500345 358899476 895574154 516157295 863283766 974136231 267957737 758114397 428346210 900761901 974209791 3934913 333545202 261828946 821114811 701659423 293592719 77039397 908754222 343972279 244201480 574686567 574870522 701770997 800133379 270597692 896624942 76991839 612354901 399241511 723958742 269165024 665705584 461161727 262088173 629153767 705523254 304796142 643224159 529805596 634304507 811135192 676675167 506256732 513967004 486770320 469952736 771438063 464918792 821717841 347872234 353386078 283326712 520906878 282014683 141669078 250060872 896669174 530402260 830905891 55319292 896414731 862350896 847586083 824416260 935160878 898643593 279341022 715688888 55821203 727087374 843280450 430651437 330100251 3031747 873483620 923947844 925033694 68990206 758694847 383221299 975326758 404523531 53057448 509804456 23484640 687709508 2993122 779029040 897115606 120458096 705928614 584600951 150489235 127826517 179908725 636426003 313321701 865764304 288536067 281891252 262724524 699270666 754770574 858138414 325668210 128050853 853296281 474245446 115475072 567198493 125561591 247050097 743256167 102059359 997132973 886384945 171833965 15445447 152906521 308356656 210452756 877266248 507076345 309709173 597425436 480864078 182744057 911417893 390673514 711885391 873788412 210911619 856922360 928320922 526796590 268147229 70023584 136452843 382617792 29381794 961699688 609130644 443191393 360850013 189938823 851839780 235900820 142472816 213779347 118518436 608752352 761046808 517808343 144607702 374822170 343832302 710387070 52550005 433193626 43760673 35000550 821110139 507399821 504048576 612089296 80502357 638446622 598750956 238608813 102555182 468376523 1054759 883099089 601876013 566060698 918431880 6182591 954569131 870491478 312644870 891776355 56690564 742505022 407198549 918558027 89854539 344062177 600236096 429080815 814622374 810093891 452856108 370294744 239889406 207386373 373677050 248392602 399290735 74103426 115259608 778936309 211313764 638225337 447820172 737633191 144832230 370822707 843224009 504315456 128083369 734482124 851001801 670136370 667357230 256290899 600462995 690030744 506733248 347201678 361519535 695997365 963334764 119937314 839426124 143066010 356464697 446797262 583410782 791934991 548428636 626141436 915284231 471750934 136718561 941600112 732378570 925748565 902723856 573001145 575665976 957496804 216843375 721131143 788028850 781760408 435326458 60055242 892906340 215720657 230050152 529945886 15532524 264781021 141322388 883331320 376221367 738715809 338705226 925981170 594292010 519708458 929190043 601389068 998578158 446605244 602203216 751636527 620051532 539036707 858468323 714100704 626177605 990834800 711267629 610705298 597461464 125767233 134713248 363770332 397031992 212899879 324519514 194031146 801818374 685937438 363327856 310384497 951869823 234102092 566162050 398009594 187060924 263694310 317088966 193508093 963991978 674062165 804795473 143474692 997188114 56396781 918107483 663010741 48838191 666555671 965218 963671699 494012412 827344524 245263679 86847310 852307589 667479519 399518519 179912900