500
798215847 293293541 156313458 137859357 633918462 420950498 279070364 43438021 927461414 123541718 280732286 352464811 384178107 65624933 546888664 380203503 410966823 654271284 361393583 170193351 910651322 391457555 187656064 450839478 117133392 682740782 122329684 957635170 212815034 311522564 892029615 97091854 560958785 329342472 832108223 211309627 107512948 528227690 874664585 864612175 233578530 207069894 565049978 141627627 505987690 806940436 353684761 953346485 504047702 832663510 628302618 147551726 438785644 17465855 30074483 682993026 466490297 168179403 861867757 48808772 10730196 23570165 406969581 855385874 592030827 392322911 881066801 732073243 168808412 523490258 481873165 981747381 5193007 729103125 718185708 687208021 712616920 111413641 495757169 224816425 621250635 443221469 618710688 957383892 986727805 854504291 265266901 129397775 503129198 611144858 234239857 154209422 6633721 652357550 561611645 36547337 146205648 908251350 142366859 183576312 782991389 611402149 323295750 174246095 831522478 449429473 382049429 10917455 214641290 959375986 51996066 770887376 611765917 103046753 838682069 871500170 73147941 545840804 200382967 11388619 638480530 839400311 234142988 828376088 130548735 943113092 258547330 512382766 946197556 788210945 329498948 453586069 215326164 954245806 887265625 137480861 165144764 83414050 366871741 771461989 686387103 423444362 694030655 231036966 902237745 843005428 61252374 227127177 31985076 941159813 780645009 623499927 470457412 614430883 316290572 905474363 745719160 664794747 98505280 196783982 712948400 436366005 338110338 13096600 763074113 576409088 463442801 543551926 946906781 684775809 445381939 487746136 385268515 795724831 938625817 972648080 255617164 232497108 897745096 578454489 319691994 74340778 227855941 52842044 221663502 116032030 255032969 329321458 206472732 464545291 279473214 500160839 240122870 712950375 631874828 494504565 144687971 917003085 283306676 669254381 609828243 774798682 746770351 106490086 20186688 147255959 149176942 855215131 558114065 317022542 485645183 525150820 298305487 540353601 730374972 992968328 907563429 224444147 652669464 139438063 11816414 33111687 717709065 213060395 534831914 558967137 516638901 182888362 133665969 327306490 91410723 176330565 679383138 40485604 480339160 145731987 864139740 404169487 350008590 368891968 932742159 548379648 605569766 625267348 224812708 140584247 261128009 986870318 692300210 530911053 458740210 360419821 640833342 317171226 244000131 276903721 520859992 668531378 87327857 40787665 797612483 557022619 542533198 492542371 591905042 60042034 605463405 442997029 166657710 368012802 921643122 117747888 372527231 318980994 982343245 927462475 284294273 823928639 786051044 286883371 814326136 836743273 271476641 848453549 423984648 188531064 548516832 282176070 765650111 983320169 17084507 173859591 526294802 668672357 848267403 482417673 341694240 238436258 837086354 961026126 237081752 174782483 502954541 150397312 115033043 783948401 876587880 775063099 167589478 823749135 707456592 542907822 209471237 71754539 879460188 162866496 109354013 23781439 802275274 69404113 901706264 258693358 698964253 169876469 614378158 998705763 471049531 149329216 682012142 960487831 516715827 247962851 915278372 447605770 653009193 697809270 531659721 817061797 74389452 904440837 326281513 440381684 832341061 292142061 240731475 543166651 929140290 486632084 114443694 239243639 917475399 971177102 456655376 768267793 309115641 217053672 98582834 676674405 341030169 535732612 746312743 173476140 252269554 455185517 770601024 282788677 662162462 378836561 527858256 590738541 797956023 259388771 684687513 777830740 44990012 831395227 911866408 553894733 746542157 79631988 142216980 240811015 361925098 272527339 905290354 495390954 384052434 67722519 640330001 782665717 52045843 530410836 747873939 117496578 363229319 381372113 664803306 972833752 78171827 230129728 233646306 946070511 86863907 747169723 682132458 195778133 387103637 121062776 394423269 361582765 610244184 715061717 272650466 962474044 56279809 478091888 65159693 910487283 666430782 650364266 139265480 599200912 769530221 106132806 246978453 918906081 536442510 601308602 759097850 799677672 663160352 571633600 793753828 856238183 510108146 380990572 468645492 581355498 257008438 843247760 787953249 124080441 961086829 718795077 698521293 62440348 508638435 807210653 632593566 553671006 383851491 692960555 466071971 615810314 534977392 375211938 777100506 208492193 786872421 208660691 720877878 953040572 412057485 798366179 730493336 45299646 144475119 789463319 34397787 896906888 434132802 571421597 278134023 316423802 74357969 604340341 781531572 522483358 663360147 258783650 573210925 263874016 281715750 612208523 227172653 929663334 653240294 926278190 989923115 42440340 810442686 181894137 290300000 480444137 246924783 100067136 691994596 254412779 735685967 995104884