330 72
130810009 126133550 847290050 736223754 655108428 765639511 799940627 647179013 596636032 968143018 923504585 469682610 14704264 345145460 322722329 777114165 159335612 189300513 611237943 634959689 683454156 753803199 6276394 943855334 28384970 896305818 237566016 572551404 761133395 737986608 58567671 189537093 716863331 510748471 184852577 194661296 412537760 858534441 835530854 285047354 710056805 223106050 723184292 824088179 862189095 265983377 407936295 980537898 908036323 208774557 617245120 483635447 748695200 630529323 320311744 357835386 226364870 513293614 656522048 374190749 677710105 791380729 891554397 461253900 322671079 892117118 19737252 118414066 836218775 450602894 875740543 626937680 497333453 327959161 515814643 819110901 534177975 128879540 811799531 469838346 258275015 85047176 760100387 823411929 485443494 187627044 337139516 143170295 667652472 931058960 305630549 233910625 848901891 609647316 532673717 800377199 622018469 795411617 247995158 282957457 646159213 642300608 95038501 792383106 766601501 183173003 829728074 960622183 733058009 824447107 271605078 415623448 448211440 94355721 623722315 733047400 984393972 256506182 992237888 367037500 254130814 270651443 763784668 163621861 828467909 292072947 951533314 874184526 352724584 869632651 346244015 518669145 957821039 347215848 272655474 224346515 892972844 660529985 180209687 308254523 40292376 70266207 301360152 196571313 331043442 273452132 725519995 673897900 552769951 90460313 354349637 787052467 417571116 380304861 491192440 186363523 394507270 160941317 192082682 203581669 552565328 152344251 811230337 66755289 83593190 410642 27544747 346931252 683342663 614903269 743514106 272819791 67822937 376591405 429394096 692613597 816475844 905213964 774553542 382375623 104689035 888665556 328299441 612869562 111033481 528852769 790974253 675184646 947744495 280263596 180504378 79215092 156781655 58564931 486124583 201148383 925291316 446268893 270161762 840632581 300545164 908720504 126193660 329923448 28045721 306197017 998866308 217376011 302695231 66919869 106209625 462355529 161207158 899289902 234356270 780445776 305066635 343824675 821145451 644194328 188696954 330024501 833476154 934343282 269097849 791894625 362271524 921513933 607567983 799848915 271024831 280704685 53252455 266299056 906986481 157538614 551452171 262819920 950886418 175181462 773627132 661951652 777261345 582597595 38658609 860534777 817742846 642795075 103729758 999413811 813725712 220616396 273217885 807619396 180177608 894879177 963365095 620071678 954418102 803003789 860077201 887458494 749616866 427583562 105986726 524352355 901021542 94305299 172820378 40749295 20718706 793709339 439505398 253834941 490951924 740822144 728291637 101839738 944723419 218924261 856748217 172674591 696482774 34116331 210518758 879817350 613738401 312188554 200305945 542253155 974319024 399379429 785566289 270970672 560815535 173448249 758729432 342583426 438692446 249166443 780025984 993153947 699610727 416142471 462200607 140707100 578637528 62822685 52634313 508527914 446904535 256676978 844457068 737530563 368944108 334484946 270286929 902633892 260986520 464611321 66518216 632657694 545412673 514882163 903713110 514764163 83501939 158968463 578092849 759063351
145477766 870294770 361767914 334217799 924970087 507318 333014950 705662509 254936032 63399240 643492066 460904371 745756015 744281763 118255191 182664758 394503285 298419143 546271906 80437422 667209432 241068246 482867720 668381615 498839418 121395156 905212606 394680885 853849437 694216730 382868868 290858561 852897911 119711498 355130286 137389616 513567835 84137939 317030859 217235840 507658949 802975454 46553291 393533135 472417407 993790012 621323972 593760249 918607924 522715591 103691979 811542028 779978957 969002913 892239560 47520146 333244997 295692466 303776278 491638603 193690375 601107432 865735550 100748200 397865803 982337276 696741137 651195290 772490521 209868947 84154951 861515009 49720244 209112206 840605466 244406631 432062527 420411699 326021519 555888220 266552053 579973908 987163085 883106083 208815164 778819510 13782218 812780170 63269978 398917534 831711848 277708167 485419807 823209535 890505392 184596664 513650053 547315060 685969195 688346644 589485042 399484022 745466071 361928881 784000096 679451068 904222243 33981459 836956437 969690167 247312880 263659203 184237845 944637214 490849004 338663686 847191013 693276543 680845575 779157486 816310196 739985546 535427092 762090520 283787493 149177413 637145690 429573093 176988556 722725237 952680348 455805636 143226104 805126205 154104724 9900861 777521422 334600928 56859626 937483290 896896497 919734847 585651670 675410119 301644237 971480056 370149205 764992574 57584423 4441907 561621563 527343222 276627183 46015252 428718187 396338261 242284900 787754319 291729462 475243406 303392309 159288456 70771497 106082228 145812510 776255479 415276929 20331793 155864779 681083580 654861442 112232620 227290733 992127512 687677893 59641483 797527723 352919305 792609030 302669777 650656002 521704088 487502564 511684898 22573519 610511822 333501229 150857677 926447944 280555306 292316540 824798888 604701521 563984078 38680397 413592574 355119737 517777447 34518763 583942237 172140101 31161178 860964293 31782047 168730831 463620066 410250307 218215664 740325161 766518899 487239718 771427311 819318077 913227309 183081842 922120334 793583581 722110183 232680698 951048112 19569336 181882714 5815645 918932362 517388008 942564568 959196716 718158893 644879920 483400459 282775616 719561630 492626856 333891922 247715656 296404419 262814568 774527358 367048738 158915444 411800271 523618168 626846818 900204459 664976426 711839140 685329354 213391159 142782606 271676708 93222999 657404061 610994317 465803738 474763268 720908476 692427191 438188439 397508661 93020810 134456008 908671031 606465469 151269962 354179862 737408438 576436616 721558716 665262434 693851643 692400784 780444870 515182731 31195996 453135967 349965703 552527538 64828620 640793502 171497494 841895591 437983880 736889641 668027764 399325386 418045503 1344190 11324749 166071977 103431056 916971763 855437720 910117578 210577772 997257933 132483453 642955064 579568088 406223495 964856905 262027207 942097271 409271400 6508807 481753267 228534365 151178653 340201841 841789373 914817561 694260329 676157770 821277950 992645682 340061585 161144393 514382226 903102025 548989068 709916842 888952806 263445102 854387640 766635014 278800086 985924578 553272857 509463386 210788703 530333910