817 106
371386803 781225491 451583305 185853221 250972605 35026376 391853728 225902056 218413833 131481690 322493302 533621268 495379683 648762359 40829196 981004178 845350545 311979956 407989097 682136355 753511943 421852989 56338565 426491154 83766365 118762484 14502795 556896997 193088838 578318552 607531446 573608550 708030406 794335885 679611893 167527150 297301238 594601778 361006644 639920452 204534846 973165614 913564162 266171130 888870357 248228871 443737705 523224463 715288294 851367630 732774435 499479090 316953474 417837605 917660919 953032282 445335652 869065221 449701960 940103413 556377407 462354493 531604390 299778372 382171182 399221205 26003199 278329092 160671618 207186360 102181547 372127097 321220611 71002623 60621010 937610823 546179086 944398028 178549899 828121315 652551562 879899989 539922497 680781708 312695572 733546814 77723099 234153011 780516454 299846400 536851176 814893488 610582414 162470758 802798035 620917110 286890384 263114182 582513562 683088563 225809249 487119355 136395047 729836744 200983593 836411792 241367991 217247806 785909271 588956927 829691124 610763469 411070348 675209443 536713926 978776085 498283758 827129336 687850080 470980453 610053501 113671764 565901350 667040453 810355088 50949941 314601265 904148667 553550175 995144667 17582419 460309745 177852709 29708307 588572756 225111111 810572043 968365178 982158346 643657505 984736431 600169655 187150248 783961340 393338045 12057797 907987423 58524488 888435572 633965762 546714415 424634742 745833735 575917053 256230474 991838485 149870872 47047573 526244187 823885568 454018423 409649665 609245717 353008197 260463836 731765321 798786655 763724723 592434124 917377423 742359333 516184183 180594429 412380834 542520221 194349827 497590559 730673831 267703885 801536480 342799553 38701974 809621682 535447741 504926187 929654709 19760409 593638678 543793868 938075999 187187866 18142046 162834950 655622995 153703417 450573162 747192525 407641246 277011234 555579416 486073262 506491967 352098545 944511558 895228956 177408981 913254203 616237104 473415100 715061848 566037900 66252846 274395321 437630531 222021928 327804845 281644261 994675397 741463988 682036212 684739700 499790314 171317872 518406880 226203810 3540982 749501442 260975319 181032392 567462838 606435125 113493922 638646940 322164193 453158678 933524208 507157574 830028560 339901522 351800115 874335919 142157373 571350189 854230542 227156961 864733594 923420705 518235110 354653314 663271958 841167180 923081871 532153104 337535080 852048397 37021618 393975627 977867509 148124903 268790947 484488168 634348098 569101602 893181176 792556252 465529406 47402906 161093948 837328850 36597887 772164019 675025359 838520836 289705989 808647357 790405972 559200807 964598143 428048578 57283453 504776140 509208080 94546237 19205978 790694594 58859812 60600766 110598549 4410671 591731024 940912640 60374074 403743848 472108047 868576616 995581614 95028484 897346015 950488808 117486834 297916396 760309470 751229105 566139383 428970249 461529563 558147156 297446258 857756492 45226182 392082079 85607453 227050010 140005752 635175839 944102551 899388383 417563918 106357880 215087893 830648496 741105279 887950672 59847033 729524911 84142616 318450702 439077231 496863788 830582958 807111968 197017789 729922650 39864025 256358243 885999657 31223498 99299884 153368967 343726896 488801949 704977820 689331703 264864386 74282113 6446226 939590536 388387687 991863393 570611318 31709385 174021622 933923759 120078323 158710529 786351953 955860001 96621961 729792807 236531161 43954403 325845514 311137502 56452740 915471155 511308648 115135519 626069415 42797717 688696633 846390570 832081250 208047402 230174662 399608436 302575915 835505159 803110983 626914536 396578713 766431848 111220355 522687004 704361114 177226249 483496245 894204629 709185561 125044677 218532895 443633348 572790676 216490631 801416099 483078373 939269365 628462986 902198714 915679546 656353917 94600957 796187503 18455063 148290676 768734105 915030549 588656898 889373422 423897208 466238155 301788276 365821575 214170528 262267215 156407800 175959927 38529570 94459523 408417889 576865059 85419392 460474260 490313038 110294794 896369774 682479026 212010904 332210737 360461941 822944583 79706583 4227023 267110197 184355993 3910030 416549337 98734905 737719329 125559410 793759767 180826567 209689099 459636413 62607620 151541016 497294494 386902895 753588392 789510107 603920933 821820236 589300539 846300062 770877750 508790564 879924967 855055677 94117432 845390254 984608770 852158729 156972869 383428431 182805867 36440275 282788333 9576464 331540525 61971735 999395275 803354399 114261431 129036461 836671074 35498250 46861029 872015473 733842128 994193504 680634396 597631197 670706145 151922536 423392634 233407786 30818713 583511528 820509655 231869130 562970633 641903830 310873687 931021122 792279085 48902143 640526725 413813649 510401543 834281842 666769696 54474631 27303629 783956332 899136470 370952587 356086115 125966621 565919378 143222834 118149437 136686230 57429645 14001686 789460107 958485036 288515081 51734080 21513042 689610119 240417550 697781542 830375432 289563788 343132225 610057944 951476084 394105964 718770749 116348999 924950403 824326104 460519479 29932901 787322172 326737945 886133928 643563844 603068194 991806142 723555161 940159717 690258334 616680159 923736324 552871597 594926243 500871841 452623162 428353336 286502562 102263243 890251041 931499529 748763719 165767220 561671476 641487755 855603667 709729767 779912832 928918594 906729923 118318358 457590565 229245250 246920884 275032908 857116939 501097039 976681069 834791847 288614946 597527804 811643002 426921556 422567082 110450246 616095266 871670518 175047741 633290645 506798623 278535779 599459417 867833642 754683548 367758037 631287395 391472840 424326145 995887113 716417793 327914784 526797881 642097034 247513472 631986190 446240989 101959874 786497552 589462337 413550051 530835513 956876356 865539953 66920422 450177956 434184918 650485823 931477097 88810044 506751720 957029536 504477114 412888658 734550535 8127298 489565866 606020288 251811953 127298369 835422183 433335452 131567432 458866069 683033144 134889356 714102950 316896608 822194881 101178479 514780197 681578910 623475758 193570964 181048698 221088319 670019958 512600509 910586797 13718324 907544639 508221460 699463649 345609906 464282263 191967095 338938220 168172609 125490820 203149108 264281274 723523583 940337858 402074853 7623730 999763809 948461783 382074332 834236448 175249689 193992409 394740225 738823183 511632051 922265188 786499576 690117457 155919518 745799565 208005615 201262059 180154224 305437627 922173677 590018456 546057475 759244366 513929941 37095769 15657048 932788065 15798882 107685333 224675574 177215352 106568930 85418937 366439365 319326699 470224116 890295908 997881006 823968932 393826848 123295435 545100258 567911129 372170168 112125924 766080781 921969421 11185282 162870832 24775256 933629007 874972031 955104918 859542111 413278490 32504520 806183917 533498101 458206755 298775544 35868875 919994222 885027335 509255047 872536921 829855336 515041028 819794377 130959992 507614526 323095796 718116615 721801092 817421318 619235395 727126200 608513677 950966406 113742844 281594314 379795037 625914070 805876173 985601440 640949013 507285213 68103251 818746178 31459408 684940547 29324468 900926977 108647283 283261793 358070128 767478661 640355084 417327416 130292609 111913546 877957957 367876361 869230195 553438378 547802275 685577511 754771081 431024450 545375234 428844097 676219832 471048747 302607440 752053766 63737240 269485212 781989519 355610267 73087822 584023170 164356599 619959280 661949734 95199726 416147003 342068803 714733606 85081607 378331447 923952906 973974940 133800593 448178911 973426544 386934995 947716750 410912696 453071301 981518325 184733113 917011192 359490436 530752615 689391943 718877931 267746333 146433433 519915549 877717550 610631545 684764718 626583386 447507420 852123486 608546996 990293044 459038255 629330209 259704662 595352147 459563829 294140681
932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871 932076871