764019106 162641905 823902025 667852204 295302864 483862792 777528709 988393385 487111875 428192921 856374601 746561301 406899334 453397375 988658970 613738503 782994311 511777521 595763303 997021914 724156404 796964868 821406581 659271860 480206403 128650123 883598091 195645214 347419386 800243837 989992762 495721881 758546512 274671657 549236855 564196163 684204581 924971575 791864288 129319057 243695831 585873609 288811723 603706748 383101055 380628058 700706062 469363210 304182078 751322042 968899159 673113185 439373182 845630021 234208745 217511291 858198833 786966180 435068915 958874149 814673747 890447224 667474400 217966128 170778667 842144360 393414038 404566050 491610074 890178775 552391883 705856732 790578185 582512309 670673029 842852298 561754805 141314462 667854202 441548793 926642449 364058685 264352190 405274466 171098555 531081974 632247856 893058162 150486286 661978427 849547946 236119839 871853738 239099109 258120664 629783134 830824919 409371006 850131692 757062401 266113564 585309039 557491175 468058031 334698885 985597902 987815439 425240308 215225966 594404467 896675582 312486855 167874799 605844411 927729549 461666498 181571054 912252684 220023038 465063160 882184215 642512939 188143376 404865442 959460055 461237982 675939102 269042970 165548552 138192521 201615368 625590754 831071442 430380291 320202594 150247396 689010843 264710582 779112437 610191236 908477249 850406257 661837948 121876463 589055219 931345773 387796468 302583918 482239399 883744368 897945746 323667069 452261637 431237255 218360648 464986338 611007663 643804379 422740741 392062901 852491821 368884840 227831622 694130721 977972579 232684681 946359856 327337496 725227163 923600423 713383294 186039353 967084857 622364780 597492183 558320309 950579909 498842075 389200506 920285526 744775557 487129849 787053807 588167277 356376614 414291774 686312908 626780689 935278709 229352347 749028463 744014110 783563387 114546550 298105147 976973434 692868180 152748793 569000862 552578478 128844332 135576226 339642783 636576517 223778001 509159349 258990030 631233103 974201596 367288585 550211192 463649265 254140574 133782845 141866321 867616948 336530159 320245570 289022711 836270692 253498501 440859275 610804815 496865052 570057156 644915652 722811524 385679400 863898726 453644301 858079706 558864140 350871007 253943790 815757346 743101784 392976947 410150343 176929604 872613449 705070359 246776606 475049886 808195988 410760753 824669306 892508095 755305287 703721165 773041294 825807580 680629938 638054575 585991128 300740717 375319234 230551127 631959484 127673789 493360628 471288261 358335848 494040361 835188438 957865824 257615971 398642131 310279122 822527133 915524889 415792000 910989036 636518340 465572593 108381244 314841257 596467692 772296968 683674887 199236311 251387832 207831744 522667931 480904522 265223411 604744598 410923121 940827318 853383839 907986620 801849642 938317274 907792128 165252510 103346327 270527323 953367451 319800204 167798377 583394537 592962213 826823131 599136282 544257163 745045640 830551991 222721487 729209366 790047793 559853171 862939107 885126027 930095872 555330536 844574990 183552328 421811736 526027911 494773872 631303880 265196504 692260067 973411828 892475933 558807005 489736992 194045241 391314964 752239882 521589270 637676273 310767847 572193886 280619382 330528919 525948106 548351956 188061636 232598938 444289655 408425689 824278662 388685244 511173167 275754115 293485277 184735901 622127015 147842335 322074864 883431972 151542943 580117116 411718312 352584163 330755777 725979191 491345646 513838916 306756524 103948806 491061287 929442936 126184783 973256713 601333433 847950700 108332333 262236979 928527248 807302049 690340883 835895473 725891159 933277207 441523124 256076096 420222539 303131384 263107870 668337692 110747476 655155728 827836297 625730080 327367078 251340084 645613322 842719733 537695439 451153647 376342735 295450258 401022512 408169741 152626871 912198037 220469144 632640642 118173151 700838275 586893516 105535453 345632386 302029547 597348232 818157813 528900357 929563045 327030982 833726636 257879750 789978765 425334166 225408161 948710490 820663141 384724646 243381871 866847401 528572655 519031532 467207426 348072333 908241150 422634747 995049401 611980755 772596227 237365805 108023284 957749508 100255086 296450361 310011261 744312743 598287310 551941965 360693486 132998184 477851078 926641211 533898209 416011372 162134462 819856047 452380112 280628296 468146208 304862661 637264238 811353229 947378829 369157989 999828623 796314289 212131276 376892172 627356920 373847123 488557748 349778179 252634820 260040298 209946779 928206321 705662527 248122421 372974715 935260375 406210590 158451609 259721377 686926412 547784768 413722490 568453880 968017071 436810256 248506557 587159476 879592967 751281957 638373082 735663784 257020332 644866949 730634695 562407338 191321590 324326454 153404054 331452460 677874721 517198109 951331934 451434719 334748397 872853467 393585985 626349482 742922577 768300028 735988298 838848979 955869555 264349008 173970982 470992998 181184975 585412352 117357317 208413581 564556441 536485539 930617807 569311975 338068114 605045449 925461229 194440972 155905507 188766871 120485098 645256724 745682244 129935335 250592334 441228255 233729675 650680377 483420989 261239511 483707705 229821149 574779408 275308918 288462892 419810348 537090346 495221174 963024205 269940869 748631001 157984758 462844546 895014113 994002648 426177138 582785875 618551152 657449555 103475058 379260964 205171009 388005365 539776248 861073362 155422029 424714978 268731883 717091782 381380365 721982535 766708411 696605821 612892914 649857040 673862845 903589047 430867475 346718362 162423527 837285664 526542106 473500121 162328371 173189800 730293408 812329729 365559365 498123623 302704454 102600313 213062772 551370796 404767477 454491147 737101913 389789799 495156600 811469388 298042118 474356956 650809345 799791682 438590209 832565239 996635974 884124685 756273684 696465626 864632367 297935578 986827757 473500096 895511352 580024686 457515515 461491140 668334824 997115057 522663791 669061202 938603843 382278312 839276917 360631161 345008290 399887270 316893070 811581500 386758147 503810040 582324832 480490165 440016855 126812439 771300312 776782860 358957668 927070541 457700639 202924658 839970914 941644615 888839184 852088598 883219325 860262176 770100771 178626329 518165383 438300165 504344507 774741580 820226308 571440047 431551191 501911792 439993097 874724402 621809118 863336666 926484749 690263458 498831685 550982220 982975996 423092699 814604041 379249964 157492367 428894317 972226937 529646883 972001382 367099678 206818225 587402595 578081954 780344846 343913774 286797679 933744982 222086514 150973316 429896117 607574792 744571360 677937316 817560993 985949194 941334059 894475370 610098221 506627152 873682793 149377667 676912077 131456068 513013415 929125782 546491863 323416894 782974688 836801122 120762667 869924840 374177114 243422320 308994720 130426754 939052161 702980287 253609827 624444126 155258925 368832433 855341474 912410513 297550471 768282131 147348039 803801301 898560688 935419858 771617509 250492960 999711199 801288525 803504370 967563166 354387616 180505601 689422501 632792831 443315654 627833080 663035743 334188844 327467676 859558679 709172123 365008067 866111746 285157125 624611753 841790683 503226409 491656570 408439729 960497839 180105399 295243640 195324755 609478868 438820480 248850371 924772232 655729536 404103456 185158323 493137241 438242785 430162451 956395769 467310029 845914495 139082326 451948117 944636995 300773699 172137238 399826120 282994008 393494224 203978604 874052307 903902281 482638649 745284496 703225557 317170035 663778221 758808534 424132049 138627680 601654649 825822444 608041852 867057696 797754260 694466442 901018195 690569273 139437294 981368581 176449033 346503576 174809639 412192354 497176951 973571755 458922177 222852724 853865363 334240715 236218780 969985414 258833675 631284937 707851968 788812977 715938934 806169007 446629187 322935276 938125614 251265527 165312040 730155735 798912307 673796186 904131505 366351120 232909181 293603760 263749458 735393722 135003748 578043630 390522635 804936028 144161229 979598411 243404069 655204518 606501587 886664108 621270820 867492479 592379672 159730206 585994642 186281386 961728536 964536312 621363442 605796559 294408462 297520663 468826877 214658564 629473637 577924715 913788062 271024957 943716698 121363818 977112648 632245481 611676926 850724901 824643259 701089745 635566825 133038587 637213588 599133309 641250078 684619637 728035375 857469389 540099473 584411289 255320282 759758660 790261275 939675894 675625719 803502624 689780401 568648672 106777945 801293331 203000839 699099183 418541521 701168415 600663954 449271951 480703763 484128089 613411968 985527389 814273189 675804526 353888106 925175670 606048242 971401216 582288430 236680617 383392552 280252605 963600491 858071983 219081144 739413979 496423587 707198457 810546996 254620310 376981584 580399813 196407808 602126011 628788920 148937119 553861547 689424795 206647611 906331379 539542160 209996739 237880086 620069602 126735476 335883460 800777738 907624957 716508363 454334663 635413878 150902263 925779908 793072007 722389243 879661628 559374940 317842288 619323340 583854864 584205738 853194693 282156939 160120228 383472999 764108580 635712814 198728113 884623380 566358089 618023755 800592637 662573545 465615526 402973032 141670988 327436476 338586189 765258671 893293740 565612777 626983574 738741390 657365584 166790700 335729136 741232893 376861182 673027929 163554643 376241366 627057243 222024267 601502166 356446985 532975092 460660925 463533998 167044047 371440835 458852575 625268340 174358520 690484271 372701476 880387563 509744995 421032659 967936463 993713904 304802056 126841151 714172751 437065852 241616535 723529545 212448054 127975853 185932733 417296031 922149484 678761032 392818505 475157041 680493626 704006069