1000 503195138 513597392 1000
722484910 931359038 343065489 981840058 521519661 226445599 530176715 770414408 102322476 673203111 507109164 694874631 741867637 279337383 424160545 294330405 82544373 48857855 815232637 669279005 52910855 214526933 849319059 181639810 172299266 889272850 596357056 666876449 475341456 424700958 787117108 577977039 991567495 801796148 327982914 892063975 262163101 612545089 8723911 593900987 189914059 724906977 836849814 371767780 197415916 107082403 142667841 152928618 807107493 475195382 117110484 107150515 213684402 801095033 355503167 642238621 851710131 639939445 864156342 443743736 864015147 218171421 614028535 244938893 603925141 88395644 680663614 267981332 689047568 516917331 184504985 8905030 416734146 32893938 945127090 888214997 499304609 520229617 19512561 456373366 529325504 422754837 290907762 540250345 426697302 810686929 505225714 178251766 137760403 351738561 721273166 966663873 781392733 720980180 337423869 652404782 989428122 278834312 558980836 623713657 887760595 949691035 285035724 633147037 520796780 961894918 311000613 12114296 667776633 572348415 880572798 403479492 600215044 9829532 922453731 995426030 153951063 811471432 805474157 940996237 180453734 639006177 211106595 425565724 288845337 236811722 807422166 395186972 814268459 570466712 393294955 153660025 214971464 957909597 975445446 421466530 113176887 567178793 967823548 95495437 821542156 412924312 425514906 508497438 405284036 864414994 495949009 659692021 781263290 977105675 407639519 724570306 547121031 850159737 352271251 10509181 534154416 204479262 709129637 881318435 50498669 475097721 623205704 940529112 919410043 306027519 181185671 55769454 409913716 292302042 351594188 442271398 814500725 179194080 942837869 926951052 346230609 490912319 131190465 526198416 479127769 710487559 81601776 312749025 406653949 266222668 122219358 72649953 183323558 553756087 858186741 624276014 675626686 437936492 972179581 292906474 846597997 619640783 80710561 366484049 514328753 701689302 385668020 816773897 803423658 837997896 730154846 990946167 22812863 89974258 368875121 972619984 178566930 66012634 299044365 926925381 988519935 47329336 895209165 510013676 118883934 922503834 763765328 20376156 263362871 375984833 206465336 803087230 552361618 113106707 461413760 417631809 87530450 97983358 760090883 541013208 363233861 649243632 473329423 968200679 914633671 560171674 237024873 94883729 204233808 878759956 112880065 947208960 444732315 299201628 348810748 905643956 867628782 822992750 96995729 267146036 608879805 683313083 774192051 242400790 253615977 842444774 609640350 580891016 574655053 993523615 392308459 753490929 210994150 683194659 931331934 961261981 410655092 941448416 264025019 767288034 170695606 916647876 53185160 529803774 944845962 458272399 234118430 638428512 165975755 566637094 453423043 335370724 504943523 804168343 469025213 568036980 358986928 138001052 101359010 586365805 247645358 352240826 572906433 595496509 162306726 584920595 654054425 797690612 45716066 624525862 579854728 337631813 926094120 976151610 478804820 651392834 87737035 348831982 188781970 873268541 47391568 867408969 349812726 566019026 802963998 628693444 831186874 376684389 152751373 798411983 358638404 722817529 79227227 132151452 571371169 562118225 740461228 264141437 576450116 24642978 783937601 827102468 449549451 730169617 165468944 45227346 262410843 481377589 942256880 966985988 340359154 593624300 908336364 734662152 509577044 296602675 691622441 843134902 397469991 530263146 75576578 79644298 699421211 920568229 444298394 522484145 330409238 869110554 120423334 272136721 735460367 16986997 958883754 168241373 470543138 310007095 493926446 323748846 597051854 533177973 746691910 830248528 712030520 244335135 551897687 762570822 345416864 772952213 879279994 150159134 431288316 905426790 438945291 747186795 557846135 880146773 759461678 703374604 793251323 596513488 74795199 804992904 368778234 417990402 745693883 162544495 286145287 582202765 72650606 194290125 185262418 927921402 548775706 904785507 398320145 860157719 884621855 810245610 604178449 50784310 980898714 806478405 639531601 451973175 663501189 655654878 852958595 148037423 205171714 536018746 173173260 682647538 325795471 634939877 588279199 193795208 457118583 169294145 984612966 954894410 765063242 359580284 446867336 749019399 219917085 327107914 144591084 264619014 13143764 790176133 451411089 880206602 691265857 218745135 765612466 652983729 680670546 384487456 302387572 207880381 963428428 314899419 41095504 276160024 709370604 636283510 622149140 362727140 722718373 560204385 786807053 735600175 168793849 92330859 247820658 77282456 732381783 838120907 952851679 792621677 751471401 628517003 13218231 968001179 933456007 153343297 260424682 385966191 459424776 274774250 320976415 171694044 517526166 753518418 673001773 344446868 576356794 603655367 923021547 875033131 713826464 363994885 554880522 429204559 243469646 743839953 142047463 463653807 485129512 650059155 221172375 295082948 919382919 923896274 544184291 99140777 885479193 187139847 269624304 385190561 308313248 705863403 746556596 703509777 917620287 290361081 896592596 139018376 19645899 549893081 357154309 475686401 853474052 221388634 363361613 648896253 3631284 901464878 423091767 584989558 739382146 381621263 448663878 878729735 565632532 749618685 628432072 733274964 817428445 400240942 930746596 787171030 410510673 661673526 2902299 460565638 121889061 963799215 104273990 186310784 294206168 141985165 490344741 255575027 482201595 832682017 809482446 662582983 255760569 379372115 228205668 46885340 949169561 110548390 413452881 719247905 214098775 249269279 801935486 522353033 274285098 336002203 380792841 484019030 239790777 410533846 412928944 503373334 183805584 65240885 213160804 590926438 662534721 518354555 717600232 438954478 901601107 565208923 72473163 433231095 271716914 122215059 396660 224230485 881719540 349411059 257652698 149911724 568035740 338137844 841030952 469862516 681953199 467208360 96968071 876031450 312713124 877007665 613831277 150840754 76115597 448343797 867829082 968209380 137722920 795503604 869636432 205827948 827925349 321058309 474353082 992959913 581845357 508136887 787954320 690355417 464653130 100881997 85401079 816866960 220049852 411030833 814068058 423552575 813596850 20144080 332894964 770767916 675013911 876445302 825872747 182723251 128072750 740103359 691879692 871785165 886103304 515998500 847839720 14451178 215304938 120156174 830196641 913699131 959485246 613841005 314347653 431249157 247289880 820173021 447914462 94455082 516156444 281170654 97433361 106225892 779672993 18796163 227032238 726141977 118649941 211000550 790759459 591694760 690812289 111820524 319364146 991576372 950991887 673610414 910199744 127346406 343608213 439717511 840986453 795701243 970138038 340431625 737894170 69262168 153129305 958828432 312177939 472079555 362755446 124723895 290480599 877114568 263066351 761082310 24057621 609518914 687399811 740352843 589998389 97200707 490977408 151399465 876436786 682744335 878929230 697319527 593538251 535852645 602739223 557774868 756104127 107598173 221271240 537804302 118250297 313941224 42839492 596328702 190322368 71155172 830343055 153253758 903034759 959484898 607983766 655971139 799639701 591808587 456427435 364321364 673295554 987048438 11932794 838497990 848034719 70565497 583343338 988641614 510282553 342932379 892143935 532300594 703993332 454794584 838282018 439418785 115274268 384389488 803331446 361941039 395629152 729794955 310967247 525082161 251562251 685201840 306284649 207802287 724635990 577330196 857495429 162928589 299153801 618724183 781533310 146622697 50200353 830009826 995133300 602738667 548421773 324934290 119706112 782197371 570086093 438682363 623131596 768746183 260040083 364470142 975909994 712932002 363157580 440939092 971012077 933405313 375071062 954851895 50522040 867902521 55015006 145504211 579158974 455254393 62744173 126861740 787761339 668149221 391975587 527611939 613897116 183663407 896889113 827612301 428369691 170478472 488510612 567890209 39690378 282519055 211430674 503660763 719657493 655601753 266159534 134859640 990730298 689669874 238604442 872896148 231033358 327230936 64738191 354325738 180533838 911572281 647005875 444311347 740176813 852679246 821727897 313447828 340275911 268301022 693376684 261925945 921639895 202177857 684121448 401738901 337131342 30870787 228033165 368844486 457745943 943812071 261535538 802511983 547870104 716709818 506151909 712425602 442035772 75551610 633090699 647665838 798882849 756298905 160006548 580542998 94234048 22463476 660277890 168759760 593147263 406968270 180306598 313575072 331373769 973847315 405215997 794633748 208618749 488277522 945305470 665022187 449264500 235965454 542847999 62053316 326788200 139858600 182655365 60854571 580575631 642696879 447406625 149173211 624751805 82303031 287590155 615804318 25744312 899913292 115381226 34540544 702346721 697482514 549142455 626276605 40907837 343257822 993146915 503562500 141901479 157584366 673111014 32968305 47529612 213785832 358345396 93190963 744953284 600198984 813650935 929159079 949309995 323347385 292139364 838690512 862534906 35814471 638409743 924266995 332441197 660498711 658881240 317591731 193626701 846255308 228784281 107957620 893787851 244317798 260514728 825635893 496876963 520972588 695466100 189672116 953538270 521004959 165783673 618921403 874984379 968201827 10779649 784951201 682808492 883474106 847372587 753273031 843749758 97043871 2526807 592122535 364242353 419107904 200188771 539549574 460007567 406057772 983694064 543294025 42219534 914112831 396348382 146397435 559189213 904672022 638461397 718665546 90075877 411038666 945725693 211517383 887237102 741287176 187197364 162570699 726555915 633263369 328505057 4053368 479237902 414009243 406347627 486586335 438821375