999
339759513 99431238 575178505 36977993 337651644 481645528 5595671 797049373 711159099 574853610 66553900 483476477 305818163 798114690 20347008 788416217 529179412 754676634 376270046 66529750 124129060 751579808 282172453 758339532 653674237 471766775 921983688 279590856 778462986 325073780 886203215 128676744 720702990 657612771 106305235 50362369 964052381 492191104 467894149 795219932 484253345 126957950 986005288 967715829 313156567 707506563 103212947 322393563 863848527 772497961 696810288 444036691 294202351 952904574 60854144 138050517 991335409 759381893 418198932 647536908 554391392 228227252 29125781 728071514 995844511 425466996 535452221 549010259 966553826 745120165 868392796 420833597 903454899 360197399 277064276 117185430 824140910 679836177 215643549 992300942 979146182 862473421 761530434 955219337 478242622 104990970 154220641 8140702 921922224 429988921 635118511 758271515 532219849 184490145 228485618 607994878 58984587 249060155 970878342 393234813 741696970 925710471 228549593 110669439 130856368 241676021 611412975 503138081 208800825 669001068 384905438 356020787 453202871 112810439 363150418 439589816 462251855 577643347 563092746 489817449 291988347 135120210 486434650 719959346 766602886 684737403 605977511 863339443 467550994 753446008 594698990 811812545 612592277 940678246 233449789 785461219 844857816 369837913 292171833 475355349 353670007 850173397 121990550 897611784 232809060 537794390 73213858 368065824 106055780 519391433 66885563 188177269 316780176 862418704 812081363 124261011 90723798 998405506 61956083 220010169 262762357 194788969 810304182 107507550 828395396 180497795 199387593 29602727 207715691 859205249 138637682 310024434 481392745 882119563 11649030 27439951 748644365 372985274 979276913 580126722 48303804 5137820 518739634 782042114 695367729 116031412 820750940 226792060 706687993 616205559 865534230 67735889 559628275 493110096 652325660 66809236 859602134 699205149 368997308 58762253 45248170 160836783 158799834 504541625 330724173 940011726 564872813 377047623 800081136 485315891 357981439 694108316 296370840 330830349 698168369 171410256 348161182 31215996 204828212 619147568 742613295 102606873 64714065 132454330 546982092 51991916 376505954 287285155 807818955 34889332 58474839 14849876 372326356 536836643 319569842 334897513 419439717 977681887 514026763 504382769 112700751 110247938 296949133 107104560 636193335 866273370 605894263 35038112 269066773 259472042 320423580 409426668 105703352 800935208 928477411 656476212 339767872 643971837 460026055 555424716 996156323 946684616 953003736 113533885 867252009 438001435 776355129 446135874 338909168 727785724 370037280 893405771 43391849 409615974 515272794 879902206 632760792 465062085 21299652 125440305 378494680 83475325 860118482 336871922 776625109 128143460 357244428 513222911 274138768 525345348 863792268 174024782 821319071 972450650 73845377 939208070 839732458 979049945 200968879 966861956 459293230 439122535 12621805 102097367 760252286 176561823 510541222 262111556 367173566 644484494 945107032 416504387 523064102 564889142 32343064 362066048 104967621 869877262 620193548 797390428 465202683 615871359 64723439 371894633 606122749 18903657 811084945 559958769 673200469 905877148 44015189 394340975 519445344 844315232 657870513 467032596 472719823 867920109 296847281 19486532 404126246 553037555 9247860 365712151 770406719 133905684 529744301 371538649 776430536 736869 765163044 529949321 101661889 171910896 23889714 9249118 452403199 771452469 776115017 117859901 972363436 890587044 682274410 152309316 37108165 44712229 185533612 693479235 201277594 129185169 371878076 991572029 824784722 265656630 361993815 94270956 967207268 294606423 708334290 178552634 140602911 453917097 913847698 658210249 298558754 113353943 218341013 610028651 978074341 841780478 63922407 123481514 120621358 974140210 713768750 738097730 456135069 920551160 254119455 118110626 450461729 417289930 749628165 649285744 46556544 78224022 635210817 59826434 33712084 329601599 260661701 964670437 30766344 351436314 114118552 203045465 244530015 843881330 756303446 34513618 137390061 915296517 138350509 866151801 280197916 976058757 515245793 280311465 441654056 425532952 300829000 593710963 945853603 672794328 927751886 537074203 297894643 213093203 682104947 88618649 963991247 448103692 247804104 248023833 796411589 183972857 635055734 259216506 54683575 840964867 967539895 364062418 400780633 898716809 536968154 266670057 276976821 494885085 832342467 276445114 585133223 587346117 984236137 309437174 191694433 57467387 625374807 568371584 143755752 818892206 577189675 80645873 530938517 80272127 804662810 62724374 123303829 663512452 524661354 847661165 65238122 950900169 107792887 48857260 164983656 182482890 281102255 56848186 273116216 645141370 894257173 297423796 256667737 359888191 36607425 970622569 208762266 364450932 782634974 140206302 222723745 117843430 26056363 714828363 728525671 435122775 844930044 516903964 213548473 985897214 756949942 915690097 391137720 503544324 211726934 22903967 605462106 820663560 55870826 9903532 799630824 172853661 151659542 545807575 47660158 623200199 821451153 913842190 353847438 50546818 118461349 18299509 689526109 406091323 808283955 891000550 624515459 943011668 208507052 202288748 195328880 568014500 674858137 484208326 221150178 197610997 682699284 441286379 971404400 351315076 30051661 857680768 166227970 897544068 423649798 445201763 770722134 331179676 218451991 844462116 500047741 56347749 130704875 894843526 182812252 905727213 71947521 140599042 918043435 960372790 104118892 79395909 123168505 48124599 105015123 647911853 670252327 658088410 850243442 533010384 733240808 385956989 593762711 668430069 903693000 565140338 865930278 345387928 574838050 511416830 738700181 246508267 299317415 248720989 833196273 240624976 414989790 618026556 301625943 363556576 676937887 770012990 224150395 182336999 977963671 990664056 537742885 280320357 927310279 288690165 675298479 453290894 992807172 905162035 210716296 583995979 469347961 142779300 150248629 817586103 272652321 117809198 966945866 530412195 329688653 10710187 723852021 895123219 319511588 912695401 792877940 386211518 895170589 728399019 924744730 324276626 666655879 444024102 799834446 623646254 107169794 9339014 634979851 136068198 220500996 225515238 123645025 115046850 99043669 228872283 727077875 64126975 455501971 30397802 414148215 327749005 243082926 356600718 816470073 329288719 756301677 938230707 30184088 961176798 198118887 118370493 45868679 391908231 465010443 267543042 86546190 551376456 546147865 76264907 985030087 31491735 665477926 475040215 796228449 403525531 544971164 85556184 973362208 656099504 493580472 203112948 960188506 196368360 912663562 374501702 608934140 235084421 216558585 917084250 14365187 767044992 874787388 443910581 353566980 345781765 427518050 657030218 372056485 158174196 211704907 114456070 760179233 73501793 503266476 117805637 471100872 665067541 895563151 16275034 487025532 943481867 978323152 663643148 115927605 472910836 842671778 78829587 967591294 378362548 854878728 997654687 819705334 704010978 698069852 840276945 130421200 925041484 387591372 176954944 146785620 317591920 587641560 822495094 216235355 417280516 278087893 839285872 612138454 336484720 755592557 283067426 792331848 54813775 574792476 365656560 318730312 862611441 758852789 410013238 537743360 303635164 310009819 549811905 4508848 303314758 514356104 663969107 290025260 90335644 694655625 317995555 89748057 271743742 493901824 825468507 830215604 291768257 17921505 398615193 461844428 486158316 508393846 631926638 339885251 782524348 726940123 336874466 374490321 849627168 313029763 824985582 38352065 776820029 294261169 574569216 495674481 612503787 244121855 197859450 819796822 875775798 34475994 497236020 543978742 894214878 414220804 526991605 710641005 852245463 266890257 481235198 631545833 550769098 611125226 734956672 506531629 255284370 952508750 383677985 868187154 844324032 230784076 116888443 409686529 194945560 888700362 441796508 146408314 310268945 28920833 93382023 633428112 94493785 904092414 205354673 631074155 132152142 316124451 552150917 39495876 180070534 200555428 993894881 216295021 746149193 447350538 485536151 37711303 117809938 990220723 533624557 310616137 330760721 164037200 299908893 223159296 323765675 510734950 299990742 31158282 1772281 641417422 190794424 865754905 485601093 989368373 859402716 398807030 154108048 388380573 599463498 72653819 430392847 215523546 326937473 680033688 361594025 474096917 703285491 15270096 351419258 62851404 740644486 434142137 14368851 838337744 757221653 271523071 2858040 241399750 371407084 855679585 808221153 928329127 289112655 283018546 9713210 344729024 802509300 116421337 907163875 40933298 146564996 992230226 684734640 487355891 387013663 412617643 612804650 74928203 281616085 332230280 748377612 56770648 884746029 749691551 379076039 905672715 355628450 273772348 555591167 940487721 952124448 399354559 39744779 957353163 376209036 20087577 848523641 245972445 746758457 536820819 412421255 20066723 892038004 201549575 245794475 265240879 859663353 878086885 789207565 854420717 40246652 365404975 584806664 489590040 67408673 989662013 982863020 944139841 330656516 22627065 821509950 99131855 969561778 662872932 964903094 575174266 103452077 138203408 520131393 747589326 887828460 76569252 764543421 30725039 313419865 882792796 47479872 19674319 356406097 171460998 106405521 901138233 872490280 417750789 63200940 657744842 168706210 664947154 14886722 605496755 549271419 89598070 271466551 724641528 867052256 425748113 893989155 849391348 458714100 329718102 58615250 682992339 937770572 931086861 984566468 819225110 961875059 144284304 539907501 147229970 710298214 903968718