500
692320574 74983910 947751315 600161207 401876006 170787409 219645130 796755619 371570422 286629417 194874378 657996477 749581098 58597612 21624756 218383456 215996300 752667275 823109776 461969518 270905723 825576621 677798577 452007937 975849511 675948398 954220449 45024646 193012866 735352729 898908276 602342749 949718113 943796149 843259224 729487177 60082847 881446006 379703230 592467368 790649965 836767906 257364841 874617178 964356926 544929798 508939479 548285655 423205975 462839563 723664501 31991125 244601786 941412897 184630063 78517778 211115820 429517874 304388489 736305477 776174894 661348972 66879973 816537676 928763995 241074437 488481641 482433307 605549408 63239270 169278911 183788557 347104295 628367487 396125479 895627037 756119335 899982484 798014533 134443226 632932143 736012721 578949793 614495651 963255106 150927680 608676225 262565979 316237902 82745120 899187348 977749760 601568001 407407409 653866605 754322715 630147057 368008127 965637164 925800951 580094991 460635169 383292172 915825170 654262263 736336820 157919830 153170325 37312395 711846250 613074964 276369089 91026365 385156930 510018370 778569771 596596686 391526304 213065229 116030544 697336158 71536185 752611782 273440670 275183272 379009638 116732653 216235191 322736483 643537283 878455776 711690059 407304107 99956284 584636719 868087556 302774486 908566345 604281818 230540303 460370174 700129527 964406119 614455843 106473453 415574364 42587411 45060568 131871737 700949893 492275844 7305705 509072940 757858505 966955592 722285152 204227588 615866482 86287190 477713614 255285126 447152010 971757679 359258342 973078360 4352325 955873223 15310735 990550561 275915040 24272945 701700901 4214269 477187596 537304351 162021524 90653917 99908267 321079943 849925752 649489554 819731890 361394004 222040731 333561164 468087403 991050815 980581811 517103436 237753053 497732137 8413220 172421396 747864245 429238954 676971585 442901563 980755197 145696481 354460434 588968592 277409633 171729036 767855322 255879760 821125380 173419390 714728686 228450495 531911579 27746962 175755569 592564434 138313110 692930056 625883732 103152324 482762158 813619790 617690515 681820408 78887890 890048739 475596273 316552817 796322471 482522324 858986328 896976600 213308863 106406226 709280776 497139163 615067783 187432177 8596375 4817906 77648338 731412186 386467862 146128095 34682366 192129694 482824051 455400196 944280412 125676086 595254573 924781343 102022497 295756179 334563913 863204495 870899350 471385390 951145954 67921406 231578957 89519446 398738614 739524126 78326839 891368986 818020475 996126161 900827908 449687393 81822975 166058031 652102785 287659637 184778565 210750614 149352179 843461962 968295564 760732401 482991046 352658465 245410307 184867994 822819363 400438201 903074798 491939154 331622772 777115941 788384051 965791352 141218440 286681224 934480059 558777375 256244162 220117157 615329566 628998199 386637006 38528786 637574384 546150444 702202976 984310608 572597714 769055602 576627632 447945990 234488681 296374560 470061727 100941504 370925976 464875693 436050331 895265174 487087526 833180081 80075634 574290111 573571669 650668185 56973154 752168531 104728824 141172040 605793860 393471078 546700239 586978246 637300310 615885438 809124789 373242275 354216326 228429480 109908045 885990373 921809531 847174362 97863911 245319401 911867466 694202724 5805489 154883018 747552257 456902458 172770767 157820109 665054214 128663960 985820688 578191787 91936374 361371797 314868850 428619507 756224820 441041539 865963266 71779423 326589033 407960441 191555484 288580563 548717383 241323059 456092793 969678907 678437753 381677753 222298569 480316550 781741468 563402034 965388377 994173805 500887251 256219886 419030155 302455154 968178262 157882339 934908728 932959155 281356890 934667694 760693914 72466816 777068759 515181487 321699937 875246480 251016542 541275307 102003345 127949162 766880243 154723316 672713461 751828072 475897177 488064855 342410501 811979798 177481183 98774836 308781096 991902194 911319639 904735728 42933835 879985331 90274280 315127906 156898843 680756094 32519341 1164760 138955768 869651755 368272168 580690739 768965822 780585003 549342103 97972681 179673265 307751168 429116282 897828124 439976643 862086392 308311310 94667190 138633227 926904478 91937395 112368167 812240681 71547304 66812484 951630630 775360629 270319236 864695828 136609340 551374726 286188089 126775553 631102679 528397722 407238770 442338690 252167181 455316533 866093230 553723128 846827759 802103874 809090456 199191819 601743908 333689801 612664546 162168445 858623447 834906949 796916130 888551453 301326728 337843171 111983609 391104129 461809218 445158274 588322419 659301887 713208614 52172810 707912791 717433414 842371623 861117282 22055599 874840121 285819581 173222887 296084231 179381519 273083589 218645406 435080202 139207365 187498815 623036647 677891484 894641041 64737798 269165420