678 415
506202327 755151490 627110602 674064950 282573147 846065152 224306041 81071846 358431223 101789026 487432957 756647109 449402426 679192465 977912727 885470196 853600951 512673347 145871594 765204919 362754383 538420074 286275868 768762231 814930705 338315786 118047321 148807134 471998426 610002078 463174034 961548319 2774318 283921329 165410884 606010523 799229866 263157510 592931863 984727956 33117450 853668155 744477897 626313653 978721169 459624724 577170904 737408128 745533468 85909722 74145402 395537190 68289443 554437164 721381029 783490490 843369248 430125540 646057852 471973195 325281123 956429081 231856595 772167989 750530461 567424545 190429759 426951078 814576200 833653368 847515248 428364664 347626475 656997486 296337431 649524350 376085660 935471117 160153755 425533617 269807391 47331553 247178338 956520951 846522562 142745866 425125126 382530772 350474027 393701420 714305680 554816250 365660144 927503835 514155973 803141783 627588615 450658492 292548260 952499503 544416530 818637737 745691352 117707363 831348978 360981443 948829463 281398878 938050278 459425891 687818827 324344133 401074496 408324293 198865239 140926 742491226 578009866 220644403 971189337 364569967 87626127 48777018 546030832 247997568 290017167 711052579 78052666 858191909 727623736 223564330 533384861 52618037 427338365 319099919 780393217 977888223 666989620 254612398 350541265 543515730 934570484 511324730 217856812 779419476 920009567 292223531 475679822 648371594 719655913 441111168 802496175 556620881 207649226 408161222 307097491 535971305 43105401 539798239 66301363 499506548 297562697 159448939 840913368 859757888 554900977 449877952 59451775 346760620 54186064 827128666 427452121 591790116 551046913 142628314 488935775 342232913 570587148 195179356 245552153 819129380 732533685 893661758 455354488 873401789 380264176 945208989 787055251 788843339 284889246 307121395 551592927 815172279 350681530 657885890 205734312 133921496 56665543 949981836 136089149 305780484 408292109 794873342 574811913 925401651 607953005 116049559 442551945 194806061 872718746 166167112 311560905 525857278 514970213 396641133 376639823 618963073 661415538 307027990 220100143 518120157 870987898 880314362 895146129 941169316 938297907 628906126 733118137 196867336 8358792 286294869 841639892 654308613 913812158 199122556 632087598 512609715 497722343 261376062 841795367 413427619 898052496 875380159 773503645 700404000 748326018 526326853 410968475 154000967 179060516 762347225 87185213 360536030 355823434 694118109 831924109 485425596 862241920 94213103 37032449 346195344 92185763 984525467 503641318 426390261 575247824 20220275 743895323 634950986 61762214 173790748 558235907 532037936 558553765 93690056 712701523 205125582 419719064 999707622 130443710 405357704 715660921 177935287 906881625 677081811 22010351 774844681 795533544 807700188 578023254 347590659 123350066 417412049 925448368 263942949 401786690 207258908 942702237 842193277 658185167 414191487 125069601 569549303 189190210 674716548 801877370 824604821 661719201 34120764 574915898 769792971 159246686 662851277 109674810 283101423 440914181 299890232 508780305 156455609 404963836 895287116 572649781 674191544 372688757 558407752 16750842 14121963 704467220 473399996 889925393 577217185 826958885 481790132 36754159 380828963 678819086 459928828 828249028 760479697 894015706 326874030 853125249 428381364 92285929 919643897 600989274 567404954 37225363 435833541 330184781 674916276 841324706 345638452 71050505 992479234 456916881 119249614 113369003 677894203 388745950 717631989 383284224 172253961 539129467 679437610 908102145 33741603 85440652 914668827 830243946 862435510 295042698 340775186 48047023 32425129 619831677 187035979 884334197 739354497 289179845 646005494 63126264 239956641 396663913 589182696 194168824 236602409 393716723 659450607 120195764 915695756 945868622 759979913 244981591 474489820 938809381 911686147 385220171 985969265 188603867 637863471 808060963 526432111 275504202 698057006 903021359 88184640 791733659 558332081 693372158 73710091 507921518 330027897 374377357 692956984 876631373 473183406 872663284 815181888 155417287 693159134 31099982 67496187 43855421 289458070 340082707 125735653 330867411 815517325 455454303 299933020 915339118 590456532 254104145 495922447 934004991 505062837 91622114 921886432 280438512 189770258 537657010 124419783 658816569 329704108 455659185 56941056 505783907 46749338 30908716 807271380 923972757 182699592 578498917 538631527 32243415 498561416 851174682 273581362 416037473 898236516 978050622 23254519 788106687 214573332 466068665 779796006 985895094 562305476 939550483 729636531 371292555 354973427 703432197 938459679 740328284 989114474 554167796 248646753 693445862 129258791 893442884 828313689 736663591 488942173 599409933 342924549 229036292 736441339 597425115 526937567 857205211 478834221 674226520 539941002 678847909 290317024 221669378 839524717 360270693 398853504 378537840 363019671 977279115 580835088 286393041 698356145 982454891 953375719 654490134 528571222 211898051 326344271 320386192 771865093 927130881 615435139 824867339 942399387 594180066 334209213 880903720 719975753 45721644 733421993 166180350 418906051 611032893 628534098 534896713 481335227 607645812 432996617 198253813 751881241 736136207 977769256 857128895 152912754 990198299 444872750 326869358 291842206 868661701 721954198 98157009 818917537 178092119 501937096 914062248 604679607 963759601 489057512 643663618 49765933 263248729 613642706 960524813 39683409 107641967 287983675 142613839 893224004 688158057 448283965 105924358 855287550 83625441 207391321 754787277 942181618 418368909 593000082 598532039 611636305 522260071 719758134 342215166 28476125 173092028 864442702 69200306 754488077 941266575 142962915 306981697 405004918 886992288 27880471 495195898 119639591 122424451 359673135 847461973 494482047 787686678 891258572 147292922 188911996 719653955 291044983 384951366 125569306 92342606 254248900 286280160 665793150 726599951 806904945 510411210 162685104 237678085 706326706 436997126 122429563 606225960 861862140 12190875 815969436 248476969 795595328 898854050 544472778 324276105 953154413 531407075 559621850 620534191 713497065 329296498 700779732 725607623 341920001 790654840 158574116 691810587 924498851 352128053 26746333 339123265 982778623 412921295 622557335 486495961 338061766 85517452 959801080 952938881 381527452 804601748 944681535 613007152 140525342 12276912 882421365 944114732 368935928 24529799 690960017 473366020 267697338 28345212 992148955 24119197 895782199 563063497 6958544 190887265 920778142 495446971 369404830 49347651 823850922 646197785 35380008 926437243 139582044 913070475