499
999856969 678578804 389805473 958779782 453423515 510167474 455583653 364725870 511170382 581099155 928196996 193186548 109100099 390333007 193230517 822021582 531472637 986389058 418493146 405852528 853621749 929211287 976018300 823294313 832860998 331912040 246790418 220980901 733844236 120252287 967877545 982662773 713060121 464228542 600579723 803527442 104171867 673767060 452208206 606129119 341933349 864354436 690811248 835592073 586741182 830319352 863086233 512508856 688004094 341541040 904182262 861336432 843036521 761427989 818977859 70621553 510902456 630272001 22823845 155881130 935315261 50019693 134542758 64781766 270499963 180033091 707931410 242591426 707690814 71428801 685930619 787297760 456285815 950229823 496553859 712450364 108890602 890679378 912060153 259344450 853367944 506804114 650599972 946771614 963237526 128010921 109132182 824207041 57333172 2360390 158845791 389462642 289254645 972165353 574202236 745237133 890643119 802139743 501593596 437276545 533768003 658539631 750812141 703124939 997072925 405713132 867388968 999856969 742005267 840843279 662108691 574651617 516755874 289627053 949304713 812868163 456776710 564543305 587844788 270045067 952012777 554112355 79825162 69770492 147874774 291883945 70727703 327757616 293717755 914382971 513073199 898072359 771607735 178548222 607182858 501269005 447927909 142233814 619754262 409267516 418134469 338329120 762340207 169316047 925561749 925724866 256911650 890422104 293239833 251541694 289265135 974740386 722182525 607828113 941686216 449171820 417852753 956616671 342157313 219171986 555010385 669174363 190554481 949990290 974277364 128313631 142267643 592538547 892929390 754114890 478700687 687511632 483312677 391355912 79441632 163695227 318054351 307881863 130206440 540639800 208251352 694087633 204324662 817326529 128151383 53339762 588862427 736379233 75787527 399015535 710099292 472327890 593695856 376799406 705970702 923914829 378822681 53710005 424409443 631286731 164023368 13844077 802553320 252443949 821792979 279547345 136856222 326204245 455054627 250890277 587426150 34315950 966358830 423863447 156263102 475374029 679018621 950268866 993437667 712752745 381381027 867472935 39130035 869769508 702888974 515873555 992421085 30870283 276430636 253163686 863990306 156189822 757928913 914160187 560714057 613140819 634437398 799681310 644971808 376695655 757158354 985815616 702414025 736939972 74783036 756805082 796112701 109470519 256534301 997251722 412861061 851997030 901362856 164470199 120431064 369071317 808156135 664644639 896351978 189636547 910966336 228181381 368208446 389988963 206523128 847667117 892577752 304036852 631163648 103988542 469748882 984434874 682332388 211333605 133715154 823350094 891006843 861126759 599752880 292004527 612003513 785332723 36439910 405338786 509703141 373306222 605421185 75653458 609662259 732660033 696983139 981605760 84355267 604868369 815721896 642990498 80095468 45518491 50379194 207400394 766309911 686724646 989701408 877185365 139099181 300394959 360116759 728473425 473364627 816963942 200706358 691039401 428185585 813003047 413896648 287513403 726733345 559734008 707981485 681699409 984153406 850933791 360494450 226577496 874531677 349937423 931925944 659912128 831666074 807145475 740263426 713349049 934799126 892018658 383334728 551634203 833678685 496591317 716695602 286726261 502335712 859982151 228743206 51596830 628017471 894073760 897245109 341641459 600653571 274525996 971641163 233943553 923835013 149906196 522020020 25135775 986931344 247238695 127254783 199718596 984182948 491698580 675409554 367052031 761903605 852775853 303302519 366911604 499808526 634217962 736434672 105961177 262650874 957592432 716553018 172652733 404436630 729585884 491072011 151039363 793616 108266192 25171113 842957314 667467852 380808455 399393460 508300886 939455869 540253797 356786212 344274047 235582899 217528082 736029643 359267670 496249188 704881602 487781726 575208200 565347161 84128971 652082391 109111040 366690387 758000080 64950417 48949904 561383781 178074235 564316574 152278189 709882270 382843469 225111339 544372097 977920267 891824515 745853171 669248138 488950940 382704459 75271481 355109897 906104698 446985613 898922947 186658554 763334948 822976874 737622638 842329985 169373076 469661765 685242660 952544149 385485017 175806838 339248677 811680160 260731928 675374199 348203701 545182268 58950857 954657720 739590133 518891973 536316500 478152459 93274382 583007358 375673235 66828945 874656369 664533820 252886769 654037275 697444941 18716337 199338281 909865099 386820172 389875528 417255645 106607098 672865588 299519647 553818030 173579009 294637332 698655861 800568927 437453006 293458423 51285901 593838045 317354042 879490745 131310423 969917339 706152861 101194321 905669616 906165077 764787682 853857710 320688383 981943100 874647624 529615048 335848056 248389651 26956337 556335371 506173837 805841885 312715068 662046888
999856969 152497801 281673161 686845908 522686256 708844160 72376467 783845873 571503797 90672906 472610855 53282523 681452131 180571131 446293603 450405612 414867829 137782531 712563345 40443951 373486295 924539012 870235134 911649111 26284194 748664841 870640042 279408963 699754336 841007687 992369215 180078024 979116114 859343940 744150171 363862425 833297629 69361936 517026292 421596809 530016089 372026972 956696586 550240449 425242095 932987199 24489932 504432818 236100139 181626075 783226024 410522328 902658877 745419375 45747685 693958632 776475058 176940912 730154937 751208441 388050967 694455381 401884951 970813570 808209337 80919586 806821245 680752906 278479635 170952647 712882435 519358051 28238108 336371590 62489766 251061697 15787837 496813929 689780770 422831375 384612496 84838247 178614393 122067673 773925190 688840386 890576221 124869068 856116625 779145869 274761609 897176640 788647516 10555628 84996547 542980473 880950566 627149529 940134430 972137322 242143938 662511123 300733910 779960939 740697482 144371337 149271259 3959339 161712937 187760070 606194110 430136474 927877521 451437815 997419172 943176897 296940812 514729269 911087049 953209797 496144586 716380717 6285576 232027472 211277312 192376380 355494016 237532505 936643618 77716213 190013104 410130683 549852344 62809176 650549091 29080845 534349035 198170260 505650625 209481488 245562364 90118792 937667381 745528006 295976111 974429713 58550329 844674285 736726877 621317594 682595507 764277552 249446574 729686143 263237058 306932116 477632225 368033960 679880063 820846002 876884563 73393143 181604427 308967366 600881724 756683083 93135146 642218293 210538996 110518036 786025494 565643034 86675000 466085937 784433811 898343411 690928541 190711825 633694752 148443633 43254467 486108573 308439439 887492888 167516466 463429523 482755168 345079777 891035991 6360069 298492282 216833513 356900012 491698080 51793241 877934616 942150421 548071109 108578864 140559200 557409175 351300326 684557446 927054306 152953963 302173189 790482203 621361332 240662294 661411659 75087943 925087322 925720388 497185231 25949852 625677704 661051488 188402852 842291633 336841565 567530925 411623868 529874106 611627767 754867695 714638668 112604050 491067262 86929649 756421120 592834936 940245925 938565174 52059407 515696545 998376017 691222964 85939836 116518956 83422294 361710155 221374957 796930258 524745222 536868061 171947762 345960320 963048882 567298652 305109495 793769183 361134136 76343024 337778838 493623603 145583699 396237380 563818274 304957896 975199811 450548917 779089393 303144968 192152896 936072588 429171365 256159011 458151535 979404037 520685087 623176018 590252264 380246528 218937918 575616324 243621742 28018596 230210430 911520165 247588153 711303822 811828167 576975029 570247518 157377516 733226390 120071284 38880069 269963647 584036965 151579512 979741844 464350080 871736329 845533002 395109029 207457833 482012304 317668984 456218323 250185581 931987171 795157768 966146466 725274997 511788221 58659315 303988821 862198951 870404661 655755363 24911840 797460292 828432304 643499464 548472729 690375587 454685764 861995781 943959894 513205595 170613227 828965513 52906838 360115182 692594076 770118611 958816852 600425358 464914079 397333676 228926431 202761346 115264227 541614780 184051010 517950710 252714007 471339390 118623653 601046194 717263469 808426360 283437547 66417866 793098770 845990608 99671762 140013777 116334743 989955037 851043042 482483638 523094164 7570546 25546589 458507752 980068120 673769421 46524493 464194212 177576598 441608495 102306101 245364295 737965520 993317643 493253426 593296576 151736298 191845771 775965090 314854940 237045607 432062312 822234598 900970817 817625865 422934157 83092572 977036868 825146100 391448659 364929253 657456324 198906849 679360620 925744973 231312991 626565597 315187527 209334749 965274488 342734078 774038912 321740041 264604936 501335220 888261236 217383173 683020704 647930023 993377617 517890070 964632129 705458720 886438662 809091593 495907150 669550284 162397921 635549810 185734027 756304126 645454421 744302561 948396636 682600269 370480248 831736873 264404877 92627147 383683047 77485465 378823689 722989948 911677939 674471827 882380921 692788668 925896895 68220953 108249453 886475264 281899168 138050915 226022924 572824522 30311756 268387772 673732924 610361215 499188841 260749979 144254566 625877680 89902007 600126958 430813682 21459118 667529033 56921442 813727793 457757447 545153248 105135371 194947483 655270373 967453186 424275189 842463381 372010020 755215219 246896535 156581227 641603280 800642310 513706316 654389298 875852597 779564279 903437471 498117070 463513604 326954266 287054655 241914262 268915888 943849333 545852857 473027394 937831839 974727777 570786353 369064494 123136962 888904739 353956944 813290664 756471583 8347366 258457902 494060628 656321498 400463072 362610641 800395655 452629158 806447855