1000 180269695
68306839 19475202 194115593 724933922 926282956 485427092 225712706 12780804 896340713 487371576 826181322 941806633 850795081 889708167 729964426 713761928 108736051 893904139 785388706 857154228 165086607 736836202 632334005 672510216 20483587 970070976 116737237 988579106 316367293 778103189 157912292 25149230 921278725 818275311 410912258 344624492 189702669 318798791 111661190 864004196 83953139 155144838 712725907 774830579 599543374 483106232 55673662 783309191 479797244 44904787 401676476 621282143 847978982 442472476 717849142 897663058 602064031 69092773 506425376 464905999 986673303 678907057 338054033 485158816 239874652 427152168 398229073 63686410 43003496 364615613 196187729 70022762 319367679 36942705 70382594 5999644 290263634 923849813 790101114 677530756 905400292 988256780 792621348 469640779 561818683 823536115 616018378 50680382 361483533 743905848 168817279 263237083 436240887 977136580 732825316 665487993 62887598 993901809 20732969 320102806 770548033 789016965 299951979 214803583 701164236 951107933 734667716 334740298 932904598 501772564 400328422 720565507 358437886 371916311 806566765 158569728 764491096 54427598 652614740 810966576 40193084 642214815 228065338 957444050 457411661 333874417 284480049 728789755 949833293 274773797 334364110 96163363 611631962 973850199 365670152 89584726 461540282 290461410 75001989 110523461 19343320 139550943 759649438 611262448 452759131 389294185 622833989 428318849 739951503 548984957 418663404 395693282 409335831 169028779 924033113 793872394 740415910 319209524 734212991 875294536 861492892 648056398 257757494 696066146 515368536 193018049 196304336 513116155 334082862 36924093 437959160 594429915 318870231 107211183 568289643 658692310 860326681 575558522 711428284 255636807 218003343 725140534 302164645 876682446 438220668 91414577 163219250 300979164 351376230 85694771 164517484 343713303 143578608 709301017 73369726 973968216 432935988 625224832 523535961 269303514 305120945 656708769 924234555 626997813 752812489 825652196 304212952 533693977 697401651 911121649 781131117 415503641 459021552 286044632 646155248 519007699 890306665 922450200 173774792 723911249 942415894 493912989 841800597 497496316 154158308 648722153 556937968 447771115 808209415 550639451 738348944 971175194 321289462 932413683 911974464 840685428 429466025 127048238 952722759 414152955 366427181 743364502 911795441 300180963 313679128 250496370 930765910 238346071 186086912 420390748 671942879 959962639 490904707 595486663 648190395 932148603 158774507 538850253 908951706 228036856 712962881 301923159 521573476 172208 257079707 136484475 276344960 919805933 929605104 385269998 956058255 36185159 965930887 359984985 357789239 69568366 723604762 553927242 35349405 736309426 407469696 648046434 267638915 52932810 685707346 705884258 423653629 55084799 12500026 846496978 31586397 989081160 247799604 13307674 54115283 216691432 979693286 979380407 767216250 605515805 454197801 795657877 478256631 652964749 187296833 873216995 53179795 794145793 613970306 647771860 312544736 489030018 681559032 249076594 947950003 250866448 360579864 40929715 246998113 878325848 52951845 430871466 831659924 552398191 78379785 712672703 622401965 706147599 239627996 911532805 690718486 814440863 284559338 190721582 557609927 175903469 664547523 961387726 452217033 291037959 874041704 790613508 170790151 606280448 299090187 176787022 673490119 248419675 341156926 202829957 879256025 113117673 320372445 311076268 298707842 27732632 718381135 422659955 513570786 65446560 636726437 574655934 158613485 687936227 63931421 568305811 436295830 603726515 524340789 599650064 586885945 902647408 107974792 531029406 861392641 420433283 351971579 654332684 140625880 816710869 221877083 54042339 793282027 58058959 571402594 772537731 252728212 902836818 418336378 544387182 965708201 143222630 152669395 623496595 531753723 379497176 407628744 908447913 897015398 223638455 739612022 234288467 768809033 482361094 324656213 493554332 159248267 187765705 572162678 374335542 496190656 668170988 524209753 470520008 984112649 59719704 172624749 415307510 166881396 415809517 870484462 447604735 23839763 330034329 273992375 317721880 950411252 732087040 883006766 248613080 940708948 665122568 758890059 509928380 433992031 610503445 937504159 617005613 300661068 290377562 593215858 887619064 587434200 867505320 440753968 287881721 250368201 877548280 330482098 796669458 642919251 953333477 284021564 107511325 346195702 170442445 354102606 797014532 324805861 828530147 431810291 545785291 648330455 18369856 493977332 741578596 926148677 502169761 349300992 778893212 900140005 494563610 506493291 310837743 982422952 839288400 607715828 173345024 103500674 278276519 950078022 484147846 812906924 953208645 115211993 811525077 338688439 993664647 590020610 678349543 586419047 105194037 972351416 755283608 179794317 556921095 119313918 517144384 316489164 380870469 27951229 314647093 585639317 890504582 975785612 993776460 861231901 175214825 59248717 211501175 598753774 667034058 618210787 142609092 822965770 693450079 984179201 209100274 946817961 72569222 74156976 376332243 840361363 562484720 271899418 872551334 630246735 33044384 579464974 89655273 548194746 653145088 713537832 671321022 274329506 124131465 825468802 96365698 793336782 27976280 168732209 648734044 553521773 279856753 377484777 240992923 464321554 664548980 955537589 121000419 736256927 536413209 414005798 90924837 65749381 263186417 668533170 571864087 791614467 792360639 462427736 391987708 402146053 261028741 701548790 819656359 76041347 979313761 278282864 248350256 905267376 833309906 948955803 375421618 38396086 265688462 3064118 563253593 767884120 259089098 451878257 563821306 762430428 584654714 642983030 400998595 447966353 116622228 709980966 117072347 604527207 569543791 15716048 466120479 778896737 882004632 137016797 780284412 293782101 654928080 352106281 621578713 30536276 816612357 465618660 291342425 990246948 394105105 726797989 630656246 138890828 820955768 864496380 321388679 168478080 613833113 272256242 243757839 438976334 835598900 98462932 181341980 628335480 595237281 896480021 478715868 342197788 879498169 956378936 653417735 419628079 144085268 535743788 801277385 976730876 123179762 710033465 279477087 505509252 416338173 754557975 635387501 473307296 151948697 721573939 376475922 222349057 40823072 76895525 938233270 599157222 592895365 523684011 955907056 460686104 430730936 117477393 619160845 934543958 437734124 111738411 982533449 967464920 224764716 318119077 822790413 554919788 939989190 675322038 960593661 804034734 700661383 711904441 955235003 174978039 287239513 856641646 400685951 618198708 240864237 295559218 869576281 596432585 938637940 109291403 72023129 791989762 663570111 641877308 116482826 107040761 219658777 939666253 291741314 594665902 473715444 683342024 297559679 402072122 551482772 350428851 146985591 753319337 601174415 450568320 500658993 407101545 573479759 681783175 157684342 626205440 891526127 262937176 115159306 805633298 547118587 30375724 139191205 777726343 698810288 273518286 49743343 995828292 92664495 347737208 488581309 625763311 942375944 582067834 624537880 668657626 872819704 217167730 697575504 195111006 36900640 534559999 345527785 893827247 938132596 468800560 134443218 433969894 825892131 304920161 376992546 159736456 383721207 668873262 645100098 395340970 392928977 882105823 953579804 43190133 109727610 874349319 607927469 92369288 733853629 823518114 615667100 458025058 625254536 740174894 733444541 450887826 261254529 158535747 348081483 948189656 60211747 642477968 810909659 214816931 819463095 596514224 590662583 209629494 373487615 401936903 684036637 595224967 610267975 726322302 107937615 33258281 192566896 217844953 458247932 896947953 516157478 807967553 857244280 576731971 349108433 811518403 633248625 369707170 750045834 187725661 162400745 279691454 253182749 24974531 277763326 364130996 705214696 635500348 950877163 841972147 761302945 234793341 533088288 705766711 388172906 752439544 241970852 691218942 738864299 963378599 377168890 579882757 224697083 443556014 412440698 536798750 640139060 4761805 959708980 6722739 839366843 493600721 879191917 376592952 992354381 134981086 238331689 818764158 641454637 906659704 522785230 714390083 396406742 271581275 171658852 53353977 774113876 886140350 900843877 679132328 970256814 419487032 471682036 691731618 309672472 939242877 272283784 654838780 555756435 668343619 4232491 702097139 554949821 915681918 402953372 889325728 134932770 279362877 22428447 127007301 277815120 993913982 364026656 602614401 247454436 2242840 457303326 30861093 937987695 189353882 793131157 381499752 311779576 833041677 796574095 131062508 910162849 352377753 734311832 550892734 609811182 769362928 140488452 861842384 574969753 255980095 796276209 952350237 696634705 434852272 235712802 130970670 520397583 158978675 377065678 437367524 624834262 811835888 122989224 68984250 596503508 217505331 38622626 801739301 506784926 823365270 810326436 200025138 192186807 56228074 654033200 116387510 793942330 19110858 49768394 935297133 522609544 577825614 141826918 408425159 600863134 780710702 112441531 489246641 540550290 429578684 946995433 323763777 28605375 922348022 99400347 745384985 201959423 454619062 814693065 895133471 240285526 131084128 272021994 969687644 502261693 856807603 922997656 280267909 659474296 471720200 580907874 499586688 39576303 445856899 179988145 805090636 755408910 199896029 361160173 504394647 37931303 131025754 634485994 871341977 424958819 136089158 591106874 663279886 443700821 204076914 716200523 924843017 750361016 293595182 842569094 638400389 961977905 765188999 103293639 736781400 184128657 426678643 710763563 358573763 23501739 315883804 270204786 342055660 360564072 246704363 981575448 933391800 458451959