2000 10
584731026 198044853 891736778 368474657 917762258 127226962 774730506 149585592 800097119 483762396 619186761 220539015 842935312 32426433 987517363 719315229 769510735 433153415 880541528 223398258 668863414 957782831 193602210 726587619 651264835 981417291 633043132 646715555 781687914 91322234 917573589 913094781 127892881 581311190 476232768 168705813 82755956 703453645 100890560 683838907 35471623 270665867 353761713 993090949 352591900 649019083 928531437 390129408 472133882 735272793 975899998 446775754 701822879 921886234 620109192 120300685 429510473 235492098 514895139 406966381 477853789 70495131 60612601 164931443 438776642 426301101 915017471 700053665 754656083 784246529 286451877 553417357 711056658 683871480 467879935 833396028 193986967 97490985 239202005 462190622 683931030 425815449 877721197 157313092 880875555 648965109 424662845 263508768 845280224 863781643 629417875 304616111 146388509 216687553 170717157 144717827 965977852 149689197 470487238 832433412 770773416 697437416 47415757 374318138 860911449 311172144 28934719 128357779 226808902 320974936 708114959 587786738 282224805 316115372 843006984 336192165 731963591 354567426 651243416 136710701 360038172 105854097 403904496 214469306 610574130 197661227 509194477 451485237 116184280 744232318 249156880 333448874 536904191 717966749 641096403 557032734 243907593 792060005 667534311 978275627 946685075 357992561 496698313 750201862 644320116 303815365 506766840 675055270 376926419 216343625 568944044 351361533 552122537 370665254 908495847 782194487 595502548 72225525 61752979 531463440 637203295 70180002 58680467 360345188 46805946 767167451 568502864 144768173 986884805 899963957 913584677 439111878 402100973 984848850 26797759 456717556 210468388 302441298 327074276 346774223 221808882 54389450 81898490 563428037 317153507 343754604 960768855 459482545 639368892 932747708 272581956 693287440 606239608 178226963 302873007 108618609 978460830 830052262 617748548 155967318 830315203 222352854 358198166 369126408 761069656 194178807 608562118 57152403 378159181 901469889 978761998 640047663 877280401 383479953 995543049 212368799 133163583 660729496 582670139 310894487 264815464 998654379 451009697 605492068 613038400 868022909 885947577 899751292 890096027 485504620 241139978 325728539 221641592 180936473 349615316 630173511 447563112 828810524 969527347 36379169 616274061 552997742 314160165 820288277 823699035 930086096 655052543 61567466 75554431 899515123 702107514 738292241 205984956 504611315 275957448 716476727 568473075 147263769 283402785 854461659 249005303 787801269 176964444 280718037 512323357 755086480 568992847 716401703 681923059 501001841 642907054 31496623 839918407 893149059 222905430 564053410 670617160 344947016 869437077 593951839 122330579 589902153 536988060 939803890 776945593 355727767 746276271 700972235 143689601 631427453 601693776 677387097 422719844 156875862 265292446 251583401 509461918 341173133 88163794 735696642 886385685 344686201 253813553 170924043 990089092 52780726 289397569 380862464 64528079 991833509 118442468 851905182 977160674 987809432 361273130 206385494 500824799 362994730 998263727 88737938 504651009 377496355 958641266 17939072 217222968 903832087 731437358 521269706 852302272 517899149 234351382 284270102 306095301 809501830 487569138 4289449 739235760 70970815 496499135 901787674 905529908 671985481 356790874 810454656 986249147 585509868 66735887 550082549 770480890 891712557 902847494 323356532 771306175 89905286 133754600 739149529 89221552 420951629 680307921 922247104 116586228 504699909 862442064 949672347 202349105 591479206 751664669 432396822 4391344 705100408 452178168 379437052 917839866 218291430 643733326 675180323 678880008 988986775 302616652 20925537 281086661 635761508 395017938 906520971 150121938 534909400 458620864 311324974 922694502 43239833 975819538 216741429 544441620 49066392 722397035 425179143 922294914 986938075 557650732 856548312 447910502 312942697 353868093 236007733 859207207 39741068 649903008 251872419 751113845 140449374 758932307 865101659 851270472 611293690 449435232 409733795 40417491 495098851 543552200 319837842 530885108 778961490 91826755 611473097 770173104 884746902 610184989 818464571 273933226 20134457 44779375 201063630 417501195 26427580 531804651 849755229 49131120 852453274 230899438 963371435 888635016 963159914 11357904 825580050 120980807 418936235 512299421 626741951 588332461 570813343 424860936 686721797 232652544 610693772 926201930 976934197 350119884 105688162 477326936 767142018 327200337 788704526 572451062 412367816 19597992 149445500 413969500 988892439 873223652 704948149 561321865 34715076 285030553 823970486 705463104 807362996 787306659 597911050 42402725 979042006 433049197 813160894 567527304 522642230 826063336 730069003 747690973 467894321 113041151 38653889 14154869 126462899 832199061 390884382 254551897 365402323 897787122 545080660 104496762 998600256 326372687 594412174 660470088 776912301 930083071 657599295 740283231 555982402 903918707 337570316 805468355 528961038 647990821 142007173 765628033 25401575 605409481 521913914 551222515 742967733 432890635 878553767 545806673 627652248 522246649 659758077 9860014 152115261 101748282 104729889 145394380 587723789 9997978 353164062 838529848 928489785 137827880 264211868 861714398 766266622 47275241 38197225 831092088 829555638 324132747 57034891 228599492 796070851 196661638 506192369 144462427 298971720 604296771 671940594 534035458 485520342 611252501 425578742 57342218 98649114 798113965 631380097 664981062 986351371 302347132 812627992 180785249 138810042 412094908 560922123 915439462 30831370 149248707 352073722 580509526 165645714 57876571 323248014 87309050 853927369 758012516 259002958 958854423 886923846 196515090 299227721 424077733 441634925 440666778 299657395 287364276 360052467 491403152 485401607 815812042 199460466 447984866 875193698 224303951 737309768 97283384 547915227 197753719 417820301 412692780 764469903 839017994 271570081 965276468 857358835 882743859 178622452 817793707 903430007 150099162 766201547 32553938 693257257 699890084 56510917 150529607 416882904 371517453 970643706 674545855 338626080 684468066 635254884 479955825 117672940 435198626 80019347 932012376 827674105 601691231 599328984 760798719 144100947 315519811 292449101 573359496 357850722 838647504 636498900 902336670 737151980 328742510 330720382 378415202 250691195 954161074 746372324 614156118 303377336 152683455 835659065 64965708 499146471 831239175 377799438 473319948 388877311 294138191 216414690 719093285 658325236 507147253 381781616 499426204 679560072 270929031 289119257 182956254 122456028 624964822 107232332 923553049 635542348 856748195 548840624 915565191 470453901 172322461 541594487 278784417 888730916 669644545 186361938 543380723 750573580 385440964 328756616 518889670 578640013 194671925 664256618 220321214 964534158 319188796 203888771 640303937 500669327 89258897 10756291 619151469 605463008 200262983 707667912 541152165 464794152 504948053 896974318 29545628 280404215 660984319 651182437 876185490 765952301 647240475 594736880 784981285 933727164 536230437 827628147 144342441 560467922 404284666 156380102 641151384 424572183 967532273 359933268 964156757 485884328 439428767 217471430 422525540 79973047 808353726 323730699 502682065 764676009 670044315 266671715 199655049 532870970 714802648 293811415 615454226 417515093 690631661 852660911 324331679 606612698 603811077 639209973 578797101 533581217 636583133 902108587 948857591 548187960 419789108 871048172 124978631 358017417 509708359 285811529 348913322 402742724 942853585 649087946 68381279 249607152 578880086 806372372 822704189 920364394 178021328 3503156 198687429 999339705 348520973 877780424 723747832 272378200 856588181 88820142 454344013 585119312 773175448 222517990 321392314 289685126 222982901 477820477 694949000 975426122 652072744 409179966 26002181 807399977 989653118 166088264 651602903 930423028 158085826 915414891 908173146 422569758 540724745 372591950 904328827 746771799 491484938 920949697 987047852 750853746 5166104 290116720 392178567 652435332 40277172 92108381 811026005 767624106 66170934 252512238 102057528 201091145 142293318 991195126 879592288 142056147 33612156 411774239 415885630 144915793 444232870 869535253 579710617 868649673 158664103 304621282 655048157 288074410 322406139 827717661 397464300 764925780 682529455 569229468 918055254 553473646 890195601 602321789 466843211 434595134 405536060 74144099 968588131 13791123 701399798 394359902 458609178 50451059 520516381 311039930 545363988 181234473 21120218 918460036 563608565 133364331 897750257 387962122 75031298 53450364 441020283 379039207 755887002 701049627 315830155 579192929 844723905 747763610 332506959 502195202 776228880 682854948 484303878 964730758 682595992 493505728 556668367 249013909 625464277 80890036 909443269 743356461 805470673 698628277 417343566 384846022 379280737 394851902 805391732 810999959 92612340 425577424 641821014 222884363 290301054 673151148 6690117 331256089 866851341 796984852 671575009 393588004 689268738 798302527 648455136 969376171 994080479 130444936 654034090 25802848 450725145 213755309 759156231 748434033 312662047 853843817 881480207 691076840 974326823 172520081 158456022 416191603 636950954 885603770 219371695 46017688 51043137 883363892 379042451 753191325 100561519 122343435 78929745 245416099 325880020 319400723 363429786 327725864 927816431 851980764 444181217 535691901 540311324 99854799 258883573 979379076 223682730 629826662 401761581 323360975 809379582 889418664 796361898 72720172 217428844 340198690 380645224 754260170 876887472 583060354 884168609 638602982 238700427 307844840 732651219 159457868 580853563 674123900 417217318 871463180 267560040 939566589 702144305 402769155 471708374 424423284 732299217 968113023 63370593 613219471 709327400 770647893 280845459 482792576 758196094 989687192 931546666 351303452 578765204 211111625 535037850 974004849 899955371 661710613 270955238 392010974 960291929 679688392 373633055 449193001 532893938 916948895 105390880 521018139 170696572 923553963 376172009 893365594 536702770 326380958 359852421 881338096 515526714 248721437 868827517 407239197 14479531 101009685 141821734 814046493 994099754 161715548 459397220 183213930 383295487 262552395 376940216 495024405 440090408 291440424 483285989 436067493 475510103 996595622 798317610 808027986 949605521 142931529 94895568 26992223 881077616 750294231 7742307 634655 383709983 819621813 805431689 494333440 770946346 401014450 558350314 362323203 573234125 969623654 840155713 396471510 746510476 494485500 500229442 474812165 726280231 635857314 876196056 623172933 828989211 802474741 64636573 552703732 264023499 546702795 793601248 477323339 603181395 566992301 339218091 560667655 53999271 745040545 436942977 972270549 401123748 115322069 615111250 372238756 842059391 84640035 453607285 185170579 636769585 361093392 440221459 390163903 505674920 111503896 904151657 698509611 44868785 225496008 417145789 834604976 570483768 522951454 715477069 680159443 161177062 122023300 761606508 31408133 577135825 368797590 486758935 774760790 834069013 149294401 191078944 656105884 987155454 452409536 422840307 994440783 65263826 201702378 52549262 75476760 282400236 53203967 842931256 109606390 589627220 276673145 938530786 637575333 206680552 574647768 171630294 347434909 817120166 573667161 519448083 624290240 197511400 843510174 744341215 266605145 704598464 701357042 169966271 782420130 554719566 216631498 261953249 724503600 59245900 280463998 70761196 219152711 628596551 580522494 347219750 242286003 618631427 927437291 729536297 21371124 122384793 61917118 302727421 514332759 393001002 529718278 3558208 781586888 235654185 414731200 851109208 990151372 633431039 204945514 951666016 857711326 437158985 195262130 885974894 365433480 914886829 12241834 324866410 31646397 444109050 155129525 535682852 853524166 337877226 100471318 371982159 29877443 80574535 848194272 8984248 355548597 981984933 955097936 88384478 133543396 705577208 585142333 359235876 619857964 375114613 365538746 390365533 168928617 834790803 689046420 627626081 470232031 14531501 438252455 668206726 341730876 81894069 919293087 871126134 862466223 75562454 281272393 125971439 417384683 249661869 886563079 964272053 651358066 839196122 658038231 576968845 91026362 688532162 874143323 883464010 103437580 769065741 983773785 404201221 183173149 738697018 296874473 210579226 342410821 776486747 737155892 881300031 120965378 722763722 641849618 584174457 167527692 203820179 789301130 71109490 30399724 728588408 593713262 532089475 858314394 275335010 257785432 725963071 204757875 91995817 284917407 399537676 841633505 371324545 609980715 706833130 274575903 763126629 74744337 687302062 823194177 828097668 539125036 831879010 135653607 608446375 356346033 883609935 942622473 782308072 704221937 300027669 439185451 999263669 225434682 292280086 995070225 423078044 582757582 512837588 107914755 665095445 953689927 971788090 768563044 15817322 509396098 557597862 747900692 714717224 326249785 569657921 887950504 958944531 693246851 193044548 8634376 454723360 394593772 701101620 223395589 330463535 999385836 939875888 157535087 563715416 393839814 770227709 248164782 554818952 304306571 992595831 302551032 959753162 905384356 745077636 195239740 457648829 267099452 309207028 798074757 359365513 880539537 324661738 543844894 965453870 548205499 357945637 201914986 440976106 578918251 472522114 379195557 420150890 224887265 51883104 467552302 946196335 55650969 253879156 208691900 417678701 233978547 613258187 697573778 624793339 639468018 13075246 293745490 416161207 291602031 213442088 908092848 624717189 655521496 572072379 553770339 382566865 989904388 898471038 302672798 806443954 947325866 567974511 482344550 855149269 846207333 831081316 239624806 48073061 818054035 962710671 188797975 192591452 396587700 445581732 567814920 397120050 840230676 257755664 709777631 725490259 186467361 625094657 183947322 803476162 611147895 634971883 99719665 248232983 982335693 160911530 668644587 21021402 330593713 597814742 333648948 916770645 59933724 270894161 522983059 134572408 164811843 122524702 267360744 371831324 961170024 663293040 686119522 956010787 706457208 153938125 322287437 238676568 552428370 537725440 528104543 912720691 1528280 438117021 592874763 317666454 949139890 227417817 469501528 76574651 288440218 887132239 76536811 889217440 235013938 360411265 447221175 848851691 380456147 224953306 247580793 771711990 380878731 606290593 776671645 442916803 959563283 664013359 359709498 789336771 698480029 668072295 879120008 741245143 487712400 456981918 536676552 982574658 152385058 295079884 366659086 478356523 598796506 838660009 920165104 620412385 652333239 790849208 423271503 878687672 992701571 489928522 93105191 294093056 172747214 563800471 67452836 886379895 618685456 756357923 455243498 246886230 691608098 205539376 575976347 488754690 778332637 507752324 633531670 774073776 562527517 787675947 252236460 603603355 458661279 457849954 824158920 441483007 336199301 328064330 318913148 643476260 848970411 847327548 972188917 711469762 386356108 73325041 393323029 39583898 421383023 990642820 264661469 173527364 648204366 862713768 607799350 143219502 828042524 440866733 172610801 365080952 385189336 44246954 498083877 145782239 544337248 95423842 744495618 45696689 465326530 258275762 958291574 857030990 999031676 646777877 178475709 85815988 316105988 191061614 877674465 380409867 35925841 525929992 935967596 70838866 874397048 61863488 883629946 683509084 760258188 498816415 211155447 560115221 437166404 701314933 732884157 782597032 878410741 541031039 459012089 915944595 632917141 486926095 2854096 698354453 319844820 618476457 563668232 45732403 348008489 567914384 264104931 979905849 87156169 864344500 72987400 403256669 983749878 269519539 255481707 251370167 23771764 893579143 197064911 800681904 705567999 850756978 114842940 691351906 2433744 307798718 115315103 376676036 828027897 6895736 379122302 322644675 680025888 995082233 282351793 698938948 861384921 287439447 861832039 569744480 38331405 833801288 95354272 991217565 643135687 403261196 438168379 25227713 752007064 747528771 661908575 802910300 748774135 176939694 179123512 768902593 632188583 849130817 224410909 153967733 116439506 256253248 21760418 19239247 892551658 972120590 839458757 49447426 367759908 71181317 590564183 920338446 905390843 705758946 26600875 44344286 438185021 104885195 608931916 84843718 643609359 241628100 1996547 696387678 696097711 391876535 577026041 434897922 27822928 107177348 561590583 698913993 630461626 130959059 105943351 499069886 248905194 997199160 706555444 56984676 714687806 172861877 99607973 641359886 357324316 139260473 821836069 214931233 877367750 847680926 17351789 216027809 138034768 199429783 273787307 767123535 819995073 895268733 472371678 199363526 986180160 311869202 279655693 987515053 268108471 612171074 478708368 972768540 151298323 832974461 269802595 847071963 86280447 39276023 16525594 194723443 344756328 192806337 828620224 644833942 122677776 212745859 88121618 753067929 232804252 440769240 655539808 239539137 615936592 355914271 743748923 772087031 318665331 119354746 219702327 583682946 455096440 543275423 180173739 388602624 333327274 551645765 628442380 546702328 987292557 545179960 250703886 778952090 690698003 432843646 321886265 43842330 362679971 151033932 972370843 466559460 427771854 860448689 706634981 312510141 662903231 161870484 828483002 497251974 777859860 21439065 727364073 438940422 639297369 120108386 649847186 293944159 490671121 42551800 369780322 940630820 816792066 830234629 771468052 686684266 634402711 19444114 680796510 410523480 195577530 73226563 134004857 763272784 557277868 502724682 975327057 730588838 833708885 594467102 956821540 844395384 492889558 365272928 228929781 255294305 273999292 523350876 737031916 348842499 852733188 199479114 59416167 474566359 711964819 53219289 302949240 290687489 997889634 961494137 834079135 300343244 641719529 739122602 912552885 937630506 438510323 935672693 906832855 122828690 7964595 308708220 68835625 706540943 513620953 971767677 75240560 151339274 806551578 615427871 438866383 545178937 724871823 482482924 31388248 537733778 390106936 105407875 164924745 534193720 473298163 28272691 346981061 864608273 803121073 282895934 307834545 319854933 461879841 51022490 973735625 579717519 989383196 790837752 881072495 109877803 802799274 383030940 911372033 532957939 165777405 505598581 28961182 539982354 824861389 795224930 286502785 784785958 266522538 838856605 851709256 496282828 61746707 415947484 851306017 647693497 207144442 866969498 584022 509989994 500682215 63065949 832448912 304964148 513781902 736294658 486418697 83497700 337586797 584939795 253567899 841453190 117173775 722544000 687878755 809606803 427714536 91238144 133145538 351206749 77741157 749974744 689151533 447982110 722572680 393681188 866068428 229986981 324977181 838433091 430015966 975127679 730897679 571270372 576463636 138608003 390149344 423586196 807199757 676353080 53950582 508252903 684611372 109309662 834067250 468885379 849925589 876076761 758324011 417875943 257283974 762083212 415626869 845862882 221395375 630622225 738891575 603520449 232604764 920692282 800075393 23360795 543578832 105935203 828728407 349888712 16525720 876505645 873654489 478411921 295467716 651252241 434127352 457241857 860481692 309524228 981454550 285894295 669014710 876324293 399446202 230573163 472808853 88151511 281382023 82667897 546280274 357954946 963590607 551693242 530527375 360234850 228862080 394886377 876262413 214135252 381826492
177 720
721 1318
303 932
896 1114
1525 1563
130 481
776 937
799 1016
808 1432
139 1092