500
872787982 251329460 182943320 877702409 698504107 401786976 250623893 255244790 506836534 94002916 804373869 215293678 56574960 976112772 783291220 36613662 237790425 133757825 127332354 381200694 99381587 873205458 248323719 41154062 237125607 766583270 256717492 305201464 767624725 208836144 256887885 495970770 100542357 749451221 339319405 241091458 389860772 831613298 245444767 40492078 774972551 796685694 349352918 730159749 221993144 608167994 368262458 53998602 42984757 291645522 287860552 768891650 838410055 792043650 934358700 977765280 526581980 398454627 645093074 91692397 904277004 684290399 785974128 795391966 273162444 855857236 184555368 957072960 920947986 313573116 606332606 512193605 290640032 189692177 617820375 820448597 215938038 88678215 771948219 781028475 498104879 538059324 684607476 261585559 758045599 639034549 6727650 539930559 143780105 913437427 966362405 26879853 686040807 609805394 669604561 867285677 260001352 818892188 326721712 736117582 293541619 88985311 23760120 246288539 172379984 809469666 649422471 508451425 363297707 829648957 252212723 320755589 655521358 956412699 371864648 830279652 167451320 742918030 941617304 253529714 893521959 194320809 169709164 364610890 791940699 760886734 975139500 686425186 314347155 969429932 319349072 120101211 634068943 418484993 598736946 650308049 372043794 811231855 569906606 679892571 32558231 48175987 18483899 178751681 839650161 886171312 613889001 565388989 822449302 845211056 431159828 791587027 366082286 991786264 279961649 38852451 7416469 939967378 850709489 179643248 659903347 333961704 691981550 54365954 689653145 579275717 471749136 128605348 993061103 910920712 211347263 39260342 469366260 627533214 729311506 651538161 344888240 154985385 129556643 150232948 857872383 665773942 688489757 651430262 683048147 108550498 760066077 248337790 325837459 423789073 409711073 183506240 681956007 652412021 558375645 813895173 521114794 402779248 976304161 127716680 431036174 1918233 688927598 623933454 124791694 767747344 439215181 814252162 21277643 175508433 350606636 786229663 935344110 139096957 641477810 228720396 404159264 434416101 365665893 290537783 347210669 37749705 725030285 606412020 70368444 321309074 59401209 977643454 59255801 965323917 927950143 417865387 620546465 587699074 724297363 381912221 957934095 839219601 142857297 657628681 907248989 855299431 433280706 215173014 28144667 88506217 337225235 680596013 211048570 464668934 292793231 611602454 370026089 306903352 629940005 47753546 207632099 788857778 26157926 120102217 183173470 979367265 205320828 309987653 269709315 189261962 78801927 191240842 316891287 706700162 369112168 97065122 886516526 852817481 971087258 233718453 469699451 865335424 455607808 283981666 730112563 361661451 792259861 2649687 638452680 153814536 968582609 142976691 229278405 499326477 995613926 556553342 168170966 225410104 408271380 837117733 835184005 399392861 308522718 286144708 488997460 257932010 888919251 177273352 153844252 289309663 354381510 798130599 888168947 676721068 578929320 269135080 986500955 140184723 422991507 174883548 741692583 316243058 565861283 561155754 392428509 751975432 122402810 972415104 27145433 605800050 791598021 40352419 458303595 675027217 858865394 451198288 177345731 574337099 441716761 782252536 767942506 94196877 514818950 408242050 900478305 998538167 594574571 359028875 843167027 397091425 113127746 119468481 56419923 555549202 824299656 487154113 102927103 791924508 937792613 871617210 488708887 883727451 731360109 314846445 752742386 55455918 872649349 999421160 941750911 835710138 292947647 9298698 292193330 744928398 798604327 803990099 111521144 212437971 937507004 14078102 444780764 581228676 762211065 244769222 200284172 261819133 292180163 115621846 110458339 456112767 790236907 994562159 322226141 383113219 715517199 78473384 410625194 682310909 886175245 527115180 856995952 86583357 510680907 153170015 380941731 898711985 192961936 942912022 168220523 647844007 327052894 571061575 723746626 739001311 179942334 337783287 954356168 73777615 705683680 876917324 247180751 36449562 222574492 294934214 926334768 385096207 116328491 295148988 476738509 685566673 65507325 628947840 957757589 372587131 740961652 604421448 862342795 42118608 219415743 344264891 584838507 165465583 844860357 51564293 158027228 859803106 434818460 146704394 41291492 207567467 359907109 76772099 261590809 659233871 56370442 987116266 876725260 26609329 407665537 250791843 998976710 662177775 314837383 310899861 274796876 377181305 906851605 483241844 895146686 699628160 152216132 805939838 680603828 149523730 216044130 315542070 101856473 796108847 954969429 935855434 696315022 185661841 994828047 974787619 527263660 357647203 339098992 441199689 784475359 830749167 879835110 598950312 38530772 394050777 806158715 866592168 21846478 4597180 68443562 170861611 384373843 337273931 61899936 768827850