996 495
532819475 677233965 682589342 34596314 522335366 340757998 986243344 323258257 21672836 104138279 43391579 381346231 763023147 384362637 61200273 701340686 292983503 393578680 134901653 993856805 45748169 31467793 565868276 384256694 369552730 100349976 142140694 532572848 654531852 744370835 875986093 339708370 982824798 697215731 569720809 318599560 334865102 150190802 15496093 69017491 161097365 752572739 688194135 100834449 566606485 373741764 762129172 576440597 536875106 557270603 10457193 750430919 351453291 298050253 297815852 76900545 312362741 510306561 359708345 746429477 732627390 137942035 87254369 326593945 50602802 58769727 395016827 408895181 683766768 524020369 82940837 999331823 48915883 509142207 311180582 54684116 347768928 330100673 983177631 293512887 382098044 3822191 700047652 744214138 509632043 385421530 304869783 99349812 531152174 687631891 507070253 150588463 9243731 89548043 397977133 329227748 998097595 737592720 403817339 2007077 164200842 498770205 668337303 72207378 125441517 735658999 702732714 694919968 302457410 310445410 690779387 664553538 38892404 741790899 574918125 28878165 409514348 524916286 99186083 123462707 371079866 497422600 159353772 392677818 695836549 503918068 744219705 372200610 558142993 58923325 748155848 492798356 174476501 685601013 376463876 300399422 703832287 19483852 3761320 495979899 91978911 343501395 510992401 301141821 401979538 318992541 681446272 745230602 23683630 341588367 362422091 388998791 692554306 80040224 383577187 117782857 998906555 378557315 507147564 573299020 117454066 334011602 65056277 70058787 571970410 981134618 733557493 987955371 360206180 110890245 573961912 19885154 658243501 38505383 568412064 139305753 92659672 307542028 378070154 662145581 685072170 94894353 515336774 85453952 981408450 119698545 701018949 54568625 120979249 511024792 319992254 144827476 672278114 683394105 6503670 316160449 699541743 979988445 2101299 336570506 757014637 550960435 985738945 734571614 336767800 113056071 693319330 669240703 987530453 113849531 365622145 529235047 60603015 575678164 701561955 39975826 338807040 16427730 675196772 95544041 395965104 996440130 309344173 342435580 993244632 3251212 752010364 406406288 754259575 488278350 485762331 127167741 47662636 22440455 370171036 389221264 33974885 659795222 564640256 108619180 359390049 736079437 84262974 137101493 21058847 386000907 310057480 736861533 333030496 165968183 406388255 120126955 124983975 49267597 105471017 69645892 324830259 752344363 142623044 296463426 994715186 375146622 303537350 140866439 80556869 352166175 30059869 141296444 504933093 85145156 750225243 549815987 738917035 544183284 518514369 996587333 657995475 24900025 132531219 678239692 980892394 363555355 733724299 72072388 690229066 145352201 94689933 157782637 655581571 751092267 22900428 44279192 299670605 114183791 75481573 92052920 573035027 91502841 146174839 679612630 153336564 572193236 35653639 987186644 399921343 520608109 374619623 136064397 655578004 143843161 661024889 14567831 114824418 536352844 93998136 340615997 110294454 33949951 321404660 65675297 553601712 43502053 133986230 701224260 678867904 691620965 502531661 498128330 147410164 14325581 753337474 71877556 360728253 699443591 756098904 73790637 492324037 706497730 510852312 117496152 338350409 31657012 28063726 314742493 572429115 95907484 138518529 26257512 58995175 665587528 119562625 297342447 43614102 530193227 122571517 658643860 179678567 148257803 526285542 487599424 366548281 406436793 754899464 562128103 697691524 349217960 663106429 17652559 516394227 137525337 747511640 656551824 709019368 349754060 368688841 708643919 12880878 143076326 561014623 34806718 302189242 674468885 522961939 761344923 741264582 567261698 42645539 128328542 730997457 56883140 496892191 551301310 528315326 410119560 511724113 79462589 67122510 345934449 126374969 77466067 135379758 688860656 874294864 123560290 488398998 704725320 97386240 687888072 5903958 315427055 305170579 499675850 50427731 379474413 676455326 673121446 365902433 326828786 20898206 54987744 669308026 371956791 52369710 335895216 407075201 666521523 119202192 660443147 360429594 527149383 15506944 155593625 94828751 178551503 688794832 707274370 53694457 31663003 120287354 12196662 672146457 7800286 43310988 676168802 982330742 878503655 322334860 151437244 62026817 304673859 334808591 555123259 685073862 691925961 17932787 70894661 28262221 121920422 541547686 149804117 155826699 345227434 749348852 129295152 695136701 369596029 388468742 299416899 339101052 106819510 74570840 357208590 554189011 60905910 298901103 29127194 39735026 313464997 358968005 367572544 762113551 105980481 506731826 731026520 676304170 328303015 11216334 552612724 490177655 701004023 743211177 754543334 176202548 4218984 87866010 546448495 564314710 385135043 666283538 380415540 389636019 387659075 547927436 525783352 734797388 542146891 396055566 337562845 323457676 99964658 358406734 90894649 549335946 357617594 367911424 16874089 535449665 339565991 383585293 521480989 159802177 79342392 574392969 157222614 324442589 752203373 175402824 731406272 985675486 106134367 563072370 163453487 655386119 326551553 375728263 72217646 556819385 36546358 109410058 730301876 407184406 145741607 336912225 684461257 357006061 518443602 537321059 60965069 527946666 154101827 158559094 174846437 541169824 149301975 45007910 661142088 537403178 318143284 567776321 86314921 145781256 702176460 320447913 514318210 751177324 64293895 698860487 393474442 116609253 357500236 998496044 703014778 393784730 504294360 409427605 24447248 293878240 744155440 30853788 755645675 20636908 165266149 2575106 543363068 362465709 406336740 110710565 708784952 758717055 361169140 368906159 410653970 375178054 398863180 404825067 501061580 81312854 330377757 731707892 519502341 313323492 680526910 8280345 43398700 533711878 989104976 68069903 163169832 367836935 999999999 380062653 143967933 52442322 878445550 131873485 58398035 550058398 569415894 534315362 101696501 394482379 709953542 757556317 318230238 44310663 874641785 989996463 55985791 746832284 745900588 571112045 732102480 127966737 291611076 737254874 705682214 108239954 488520066 512687770 663698899 12853031 152135654 1106143 760216198 514906366 75025151 564813937 667257332 18597465 63024316 345676196 506486257 364878632 686417285 317533295 2864951 545056849 534311233 682705035 405726760 739522663 670682161 361429700 516879755 78459619 136599236 991436785 13578513 23653197 64044962 523047637 178173414 4449089 396767764 981930215 486725189 94844260 88730508 162372559 738038304 552754823 489653354 507840386 5401952 383246818 118745494 540014313 346651761 679876521 513666607 542623953 310616085 292575149 148529395 390047981 308031870 404679335 20194519 687868596 63804028 493403867 352385097 21541647 291600638 500409625 306810124 329821314 44917101 363835077 504501363 152699535 559740017 324084916 72798780 397324183 344431902 338577449 676591029 386706014 984714417 332389050 331700759 107354871 148658839 291995729 330928816 488018179 130963399 762036074 29048436 160164422 148825431 112487967 305821678 14506208 552170579 74666870 385606158 83537303 177821439 164531696 317152834 495268771 161377397 703365916 156420344 176956848 118541996 363100928 569988976 986623921 40398273 703388381 104956175 705918042 57479087 178709533 140181949 11247445 409677123 335362883 671112393 494315127 517483117 49513294 163200631 162373131 328089793 979608188 555986311 146607438 297227083 520573379 312653950 108674216 32965297 731451176 704762568 759357386 10518778 30409933 508539728 707738080 25714355 538398386 379176681 22097313 513325692 988604791 677611351 391864377 350579060 671522783 545654177 399378933 71006970 323439446 694910043 503018586 557798414 308223532 303409037 367270823 72799732 997294453 658953278 561475665 60662558 146950686 157673281 336516021 111670330 560076572 686710597 124438649 539264206 408031784 667767530 521477565 875011981 547014718 51465742 348671446 295640644 110911999 487782888 518886726 334738742 96415412 394116843 665166061 325568354 877895897 86859613 549130815 510067002 1492796 347280618 25731212 547563603 658166678 733941697 877590358 302049114 24387501 15203944 138330509 372799646 540297156 20244547 391046880 317054641 377186697 506427776 681897623 311544014 501792985 505855397 522544089 732478884 76132620 40809258 758530318 659793442 53127372 689539949 550315159 558857408 520698443 491575100 314070972 567649298 355433511 990675608 66149851 665916571 571789359 29885321 59989459 402872795 379733882 407385509 324470579 9650468 304162599 755427804 157574058 115786778 693093371 514694509 37521184 760606097 400511614 565394286 382878522 876821660 690426097 983977629 510411213 997127181 748777116 48179255 80446288 102662116 177546373 990532043 994685825 570900271 46873898 153813427 534875778 395173768 156943822 515708427 137340572 308587587 321271868 675415329 130159207 404443743 41674850 137433109 354676712 371540604 316095946 38201755 568289472 409971061 740367388 327505583 330906323 698134297 676505788 163131674 401370911 657495736 50035740 342909083 674018037 85556509 491814072 645004 992256317 503635461 120031995 696517863 353775129 45969368 35458139 548850007 27200498 64808439 307502025 491108147 669879965 7090450 23751884 296559366 981352164 995670161 294835017 531904112 363888770 532217735 373411521 669268099 356197676 339007353 32532130 745316359 57326560 387071802 8878376 489056364 519044837 669258308 98344132 693938968 103178276 519573181 675790682 752745077 512202130 563958337 154700416 352804319 654507013 90045630 93496607 397656357 354596699 742733389 410122414 146748460 332580035 93504492