814 197
4537820 915179056 274071925 626463718 371105315 189012437 211527982 955558227 721549645 793374857 191193079 577025391 122893928 737219040 800479322 867187620 393599735 25928807 642669025 557155826 887007542 570206051 351159534 546339304 51916967 488094124 364090890 629611828 909910780 603301798 381479767 928272911 568966213 349946012 373167993 306983689 889017487 428726002 581672315 937962967 828354207 220952670 464464204 906008734 550222933 494169887 361705750 887540285 119100342 796732644 851220991 828527597 40246939 294726162 951783238 16336760 741708031 515519441 609111841 441869018 355417928 170608205 985917845 698843553 38899253 699880446 723467737 744723930 895934905 37805400 360210561 526251516 488958222 426398406 125407311 849516338 724701728 358241848 742595138 568147815 499402176 463872309 922054926 703305276 464114880 231109638 739621932 584370815 996881275 546676866 882274867 264569845 983919474 590435455 843982241 657347781 893823474 793062064 658458005 227565993 846273349 143786726 837102164 748296163 438223297 65666099 661369825 419456302 101428590 73417968 885028664 711705554 697180740 422546678 526585646 40842383 24171086 398128134 946320840 473622551 625858543 41433300 221780128 356098125 867263468 102707309 707812164 128329473 270426754 659369126 339756895 532924576 972909832 295067984 192909425 375245177 635983808 223429107 809063256 200464020 163595757 213481789 85638504 544733285 648313983 705715633 905137637 26223719 379077714 861051023 35038011 490069297 56129439 681385558 472372359 53272088 146715653 775581465 482321659 109369052 583978260 941051932 637347717 38478022 726567915 213691975 544453265 993335870 174459077 502144963 681520588 260936210 114351033 653029211 894912291 534453194 80534031 729130048 80362156 956829665 34588779 759547471 290675782 277808537 714964943 887047419 916215590 606378995 697176556 827301724 814145470 337642266 265107204 690178938 735438535 591797738 416075950 414690866 499929726 987395230 994469476 927295341 15674191 946805183 669841891 207492450 59447736 429517580 36516150 568511800 123645160 707566866 885240095 70755045 164764468 480129737 806830040 451604604 77329771 387976801 502041721 869496693 198148021 224112462 964852684 822291106 204947600 509719369 775394696 927190905 144956921 496288473 508694431 981869626 518646390 803924840 239307660 966234692 70667745 258307868 4659725 885423519 970139593 712525724 197582440 623282822 35402313 396501464 501455872 854477898 625936883 247863033 162613893 958270686 759752727 280284892 282647337 813972197 325100041 633708800 545459767 105808777 916466776 312512065 905772854 367792233 911867482 2990313 789121757 950081364 142407240 885095241 265593152 452612344 749730236 76156304 499944878 90609701 607015487 812211123 694843890 513820476 828304105 554519411 461691642 279143192 598100566 273283495 243964676 305728296 735956494 263004923 278211457 441627913 950284602 693970569 309332353 972487336 999997496 609008717 803074027 52018609 691164034 602433826 287151628 377652377 240068811 914440487 303419473 52935314 551593188 197483520 747052696 371060215 554671411 428066107 835553769 939382774 837615793 866404656 315222562 620876076 213043963 160523075 760389652 792335427 873259831 419394374 85822607 676868274 192080539 545269243 534953368 989199870 292064407 974448235 85993954 958262591 489770350 227330367 286781675 364196785 565527842 981849630 888631710 793498999 781102068 379318281 552679793 824392334 937715790 572796956 574416621 77308159 807370120 409609295 204077700 487008525 361351813 857126488 518561112 837104555 491167992 962602563 460476091 951804168 115617158 201828698 541112756 73328884 402600229 430276391 592027188 565270691 262578197 360953448 82490030 72100010 778109948 975372309 803274894 904085649 375769330 375008153 547216255 314493120 492328993 767385746 633958608 955290692 313987374 500751231 940433823 101728507 912639592 786923437 62672109 593849881 559645260 456262703 191886179 86565447 169622348 412889078 316138587 454276173 784159355 513357767 463694813 350174478 594458559 218545869 943167895 798996281 14653625 964760478 954517584 640564795 395187564 158736033 659361466 358187404 991428963 45035624 644263759 171802615 236784036 502231861 410527510 900147310 823578450 673413779 17454367 847601130 79381815 152278699 315177543 741631496 248122797 941827612 323900772 468825601 425265849 456541565 986512110 447527756 984356064 9643838 133070987 9240263 243354757 883933197 956043964 249633295 823413398 659510152 717117584 817369213 19058782 313243386 122188866 832315125 727484144 91146043 789862153 73302429 179775150 414678571 74977733 543261485 527732440 774772838 97669947 48695930 165806785 159100781 916427013 905962086 297847911 858955242 173588642 460278677 707885562 173602830 866450544 737231409 645330348 837412416 701542749 643029328 151981507 242742730 447170616 28382187 452144621 810372089 838824135 703323617 863638015 657129621 838983556 54623723 814147592 804687469 598407731 974226560 403744543 397885596 769959451 784161215 955661745 933918570 236568954 453443004 483202014 281485840 100229049 388031554 912549465 792205552 508199293 84319379 836694651 865964439 614405408 929187089 107061153 662881637 51232772 565258040 655450516 771796702 337952773 387538267 393241503 382290389 212837991 97842799 312784677 909356192 604625544 808628557 53084097 287771077 8516387 295406403 896529844 543755362 533774782 997196011 883104673 111206072 158094901 437490550 400442211 409602858 529213572 537880628 979038656 180983604 43392123 755703947 676542631 492130745 915208953 603321212 24126643 160998657 90145288 284395276 158137551 600448058 314471033 6443638 399565320 743220934 544738840 261235160 451755867 774461208 399602457 881939287 488651370 969685044 93122891 119771777 647110563 822619771 260800330 560866724 332749478 44621786 999053578 908374967 778546183 77890567 352327824 684001888 936730504 762901491 56296882 102434773 190624708 300088983 522916443 903777139 734385543 87574555 763806651 546497836 818647903 229353787 271757177 169096245 461972213 310296837 307742705 729399083 22720569 707285084 492128207 785482771 678051791 306391055 920053832 873143056 22275173 356738501 483120619 617752702 300294808 646204578 410221977 820651050 23116819 580995765 520314889 27750188 563795511 283338306 979198366 208886955 179516759 983696975 178140153 94521053 70629944 19423859 150426675 584065039 922005547 608271625 893829129 916566539 530589530 428330584 968241955 690246477 595374526 501759141 223381192 538522401 923811744 243794877 506221805 892000503 63029245 223010920 462811061 73387480 497302284 341299882 992706714 803284966 881769962 918147424 278203049 324861618 168633277 723443383 69769636 465128991 702415769 856583624 916916586 511878830 905662007 555897270 914627246 72296743 992062613 371679355 849005954 203891914 941479985 481623424 147431534 617269604 988666902 110893378 259661888 260068921 842483210 184487737 589840414 362123627 294886468 99543231 738475902 4802782 181180969 517840189 873381483 489559550 355295230 104341600 316084867 789384970 420142773 26511623 146762008 760950412 374481962 44115820 923506996 271139629 761955097 570248361 402810737 277695841 753933182 956454048 663593769 670629877 835637151 169196084 184738666 688019010 138753886 708349253 928034805 770640912 319607036 86794622 151665858 999524780 185231477 183430650 811385441 550910108 125376420 945151319 500721376 305403298 512090429 593726386 618445327 433299745 253837555 971840399 719235644 817066717 515264249 469739714 784510450 158498079 117836719 107906053 972891401 328663975 996939562 342079971 749556197 941220531 94501568 942805462 165084582 61443628 152231143 606832667 799815798 477981163 276678481 214701037 580440378 889077475 501930170 105784708 35668023 913391836 936874991 314335406 275716906 57966315 638269224 969248897 421743253 635738073 378384534 992923078 494274913 430990845 123980811 680510869 438550579 877731034 661499158 902749941 579582124 139082517 84642327 255732535 819460401 910370809
707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557 707082557