1139
542989043 117701177 492866813 371614690 662789896 677327412 282546437 170843809 611439235 888767074 459125097 784945444 523493437 885390559 382750341 510627507 704255896 221902894 158331140 240242752 780462555 143143164 947215351 864577262 612963856 50571532 317494230 274227142 192319862 210500899 58002859 621986143 26143915 396606901 14149625 548225322 716238024 830464362 630443267 799280549 670774359 284819320 620880928 382440465 692980836 636479913 94722280 654449775 996183713 142036557 529056312 416856060 107933451 25456628 169189802 563737867 30834516 197617677 963954690 86711996 986499597 964975029 250308457 407114387 522994859 56348853 164050814 624910184 861974102 768990421 534472071 184423648 394733170 396566763 255322538 583986305 82449895 91226516 86535340 89590710 308478100 815807673 463704801 741540009 43937389 195050939 788044450 958335729 65252538 632581689 54633925 448224482 18041239 533300571 158564739 627532304 761077549 812232084 843317413 470801419 825390551 549106290 576540051 987971227 457552374 456634310 747312852 132191262 14754760 573082490 491479186 283112762 431065001 174419742 771246517 971359948 886321917 473538777 445389915 515306206 636064109 963637661 349917219 300077458 350207540 438835922 800086179 116504852 960538187 501320239 125512220 924479874 306710170 274369030 776514144 747980017 196882301 661119781 100866923 144899164 596397424 469846319 741148914 887613263 6657107 493513199 198359534 356232345 339878242 80507135 881386100 600477354 898791781 36449031 210741105 910410300 223859381 920785509 331716049 790656491 559428727 99044312 906254726 490122896 12866758 471191526 448396564 455041232 449925375 135194534 993255414 18240622 556204364 636796486 396249324 588919119 837583967 171559233 583235625 313147415 868246965 6976006 469228266 475784808 450452575 259488319 692548844 820275974 723870338 285905261 958710214 188685768 113412433 945797850 715627765 273617693 796546000 318882012 246127435 633208120 792135444 381620697 87424189 112558971 856134618 599416245 958766513 553614268 951839078 679639210 163533854 800746450 285422942 585452729 149142678 299959142 893642625 162440466 940933466 948717781 947324967 829620088 12027815 65922022 214752692 566807298 724572484 195153601 300713971 396504939 875512294 550642882 438980998 75641553 416289724 686005681 45487796 542676179 276194489 41639411 849678126 191798683 530974417 201650041 679297060 102899955 873796314 126134376 937669274 913734289 379861531 430104104 934772318 215684549 186092399 269105091 414194684 523140195 664554923 685140074 690022298 928035445 526836609 824975311 41136195 264998752 162471057 820147769 865938331 671377994 447141074 85077612 895137160 899202754 463043111 983760310 318453937 514882449 992748976 864337293 984624594 414368269 248686785 50632073 341275067 178416292 925159587 806496166 57330112 388693280 247619581 138717376 516636474 187714761 124518784 17898472 613479974 239588976 857403505 709779304 847871226 744868803 107157398 236513842 143623039 602614818 202542418 906313325 946797812 83450543 917040141 835313389 820493853 67632758 846784943 467039084 130982333 556153554 16050794 186263988 291880118 214738971 924738650 695900560 880401999 791493382 610274140 5870988 331517062 928095474 162194970 333385347 951709700 510789350 565668186 136275883 544380449 694313443 701279164 254581012 886240559 591967984 464259566 497648840 285365958 740709603 187606646 881717048 101066555 722924534 802928030 634872212 100949948 895104915 150820671 761983521 560766794 552279100 536248227 579686431 230082478 969436987 938757608 818956494 958542734 38129261 477189896 131902980 673269744 34698781 16705141 517813123 507649733 518501456 827407935 642169097 952280845 5116690 9550823 463899576 887835089 719144176 837187192 270195860 848534100 443592718 47041380 20022132 235311694 167443319 693450379 948392980 774572904 5812597 4369560 802675312 2993550 834509587 465409689 184944592 162521314 185625087 656396692 99183160 789836386 63048693 859444209 936952333 747477895 595751093 525379594 635997854 182250606 770524800 771418471 307379454 518838451 209964623 102998115 799771814 38165082 856165427 258583825 820267871 910769819 805380426 428706909 991400218 465414518 739078137 672913540 415812706 427256651 654350646 255233798 509433094 816445371 511754011 715901227 831929117 150197844 701485229 532124123 666645980 394404034 166216625 635942281 945094092 350435499 841277202 336152746 245754899 302946193 599862190 486441782 441613622 176130335 491853158 189414809 315289170 245270038 545208852 14003358 810263660 110882266 722945834 293427528 160401298 29959433 289353920 969696016 754104643 938922326 67959037 570542255 451710814 916906978 198040121 843793794 118564002 871674 740611853 510551967 245311058 779925964 589167664 844604739 114139493 141096212 572821572 325686517 216327213 968859497 77461208 88777514 29981975 414084753 10224537 8031790 307687042 967743837 391288156 616083368 904589290 264253631 636951324 407393489 995506106 909737200 357301941 21096335 299539051 550460976 927118858 374878199 64065112 405982956 279597794 84893433 425081134 783641240 970233584 22192059 700551586 776191013 56556459 15024487 283528323 780956241 696757158 273094628 170659100 75074240 2693888 410006205 366668652 459771989 170511166 919527594 605364624 732645356 933175863 671742486 347682651 789310085 951116573 845875025 403087906 32842089 489493541 837460923 290959333 976906576 802584766 278328092 578607240 490056669 373883279 378226454 132260832 136650604 848057585 598377699 30823795 644454862 126592744 657416829 745577221 821008205 274293792 692839746 778944700 7851726 242132004 504136022 694635860 878196887 134683767 140076144 638158561 912604433 516232178 996461017 176009053 402620948 123001427 494789024 362872124 755361412 705350594 877286986 318745771 836736478 142880990 613614518 495005589 439975295 82548784 15192858 102119264 743151363 687187337 464064066 764081773 662273350 927171983 715289653 385334627 493619231 366773574 83380393 53737117 11523974 833231165 473446156 433392599 279895746 43764860 624096693 590332609 66565401 161575018 607079275 781012090 280629936 940595679 677085082 63455171 569076057 217587123 52569841 14777086 578226689 867615858 788248593 957334616 337019106 481774510 560570631 622072944 187732712 856507873 244340889 274889883 234216787 197343989 87957368 850302656 275151456 64753460 616625635 700184001 144432226 938298638 554662687 287973444 537924953 190923297 988769039 738938592 580429908 43799790 509058670 615456773 125006217 44108157 465414186 578283231 807850804 928825586 582280031 540672246 727183405 227055288 217464032 244955748 209147835 309978429 575834719 874389717 871702535 710512364 272578773 507677725 776226737 442190995 207849279 361187098 359961986 459432613 561542462 152376994 968163899 435303991 951846139 23779686 466731246 450918298 505851283 517881607 772988296 290541869 208733119 609550394 510327555 794975004 888382893 101769719 130177007 119099896 763945158 344550981 809093177 829023174 788531487 184107550 119307441 784204609 409764381 901610966 751717974 838653430 188512572 563045643 134570819 525240764 56082667 69178113 37041454 251110922 279398791 78927733 78382034 273556249 181169793 20902025 389227487 113113357 279101618 631880156 724376020 826749422 146924954 215462984 400504282 819142390 287415134 466941754 304345216 694529502 525656871 953505207 584039434 139821753 575055658 288821013 684232514 441418515 349922883 564817537 309853148 562956216 307275692 191367705 670466176 955349281 735302789 735100674 657438094 655702066 173544420 54722167 984486195 113423201 954093344 38012797 649545410 845736179 775004046 391385739 277252919 967675648 906315219 85387183 982920156 945861439 107321645 966107283 988925825 657577673 132887645 69095848 634372227 710403272 941118229 953718157 579839833 517980479 129490225 878620244 556874644 289705619 284370417 991083504 484709229 244878682 760595431 973058009 558649932 630199924 8454198 221707911 889413535 66757185 680280281 670291748 69970204 198178198 132223194 174905001 162167574 73223876 583242625 333970146 887382240 996950185 651346327 991028578 909413672 177757906 655807533 989892898 441528783 66551457 679114838 389044740 174906805 115325888 454119084 926334495 558996738 210737248 610840228 588578990 42840334 341713302 826938795 144121021 924934833 94618066 785231368 933738860 782282390 183649599 862950282 291423356 976469515 236097621 978655516 514582424 626961967 993104836 630679305 210254175 340251802 635967509 265489883 475110304 205788147 162557580 63815172 321177332 475103327 260885835 567244171 858371122 957332748 894452106 162951527 545353934 158886070 6027641 454966396 675369943 977723827 699345201 988628132 70407526 444835861 130990774 275575549 763973972 714980517 960959800 860807564 835725652 547120322 908145697 298080878 860631237 154979288 193900517 750894435 548641940 926120140 72086727 270324643 964721523 873445348 511566216 427581577 425766099 758391381 688827390 834900614 408241896 229619339 677151437 53854148 493808228 243722730 245603035 641752301 264905581 99755485 317409789 293617128 278091681 255737531 600273057 897286595 43789021 511189013 91392634 432082432 814996234 312142336 837551220 471914478 764980403 530167112 953686583 179080045 402823233 540565168 859640300 85851209 993538931 347037958 181388317 94312648 977444886 872215320 359044409 18193634 227595816 203217318 965227910 844170186 904820961 379926479 412259292 693930490 293753589 323840217 993993148 754694866 695883872 323385700 783339129 193116783 14022638 849440845 192904959 809120293 516835150 155984791 344539819 39986431 200706598 298247225 438954451 48968588 462662868 301407880 399110652 613521129 204974682 846036343 737898073 251250172 445881592 482701696 833731783 215129800 785716793 35204543 43979592 419150974 848512044 900392146 909352332 367154088 651992018 147736110 62823873 816695691 112006767 260714092 575791904 941808190 548993710 492787626 601160411 556925763 61813551 688091362 388925096 151410039 596928593 465123824 477073392 157993952 436938652 104795873 962772153 343649198 639730028 178895109 273306710 496647606 718505008 424573781 220495652 252432584 125139011 250660828 863198299 232798520 835564703 558344321 335447547 551856548 383969074 186279394 411222127 487869208 594857458 691092052 380515252 519989486 255628376 233424373 824659908 237612326 203457867 240144132 206805451 510191641 249856120 611199881 391462002 438665632 727873008 789042655 461840707 501138082 151196748 935210464 824493592 980054951 843450188 473767923 13850850 935069042 604922419 532513153 355680844 986960459 175287903 192935497 108762622 549312483 76340378 917113622 218376948 203285177 966908720 63881937 529255147 137013065 924246879 203960348 888793243 160483057 347954135 173364874 653705621 259713463 825704282 892699520 361066005 595017703 654912242 898041542 273961231 3756407 42369142 636510252 233792055 598056730 838249395 447024966 290476589 169574847 149990711 362770808 45795885 724261078 431601247 253711942 138291021 811023185 845020410 154921556 520911224 823169229 332133886 205415565 14354065 601429897 259974547 827227395 678222558 251937210 752482667 999873507 308970546 381087466 
373360099 323276874 254477189 253236234 110601343 228537473 348011224 686138289 858935391 276664897 290065933 740129683 667400480 272579167 794955116 676588018 887644656 866535655 65416442 888402620 706509304 109359252 411317506 366051170 895299578 436767177 804720218 877058357 931385402 730798108 256597776 752823411 659743376 159710788 987283785 156545734 18229876 278498898 818106710 297201462 186251058 711072355 714965013 135044037 667242444 868086189 394166330 89411688 384254165 478782379 654863957 4401263 278249328 307820146 470402470 517742351 976260352 210726863 777094606 129953618 856454582 139099305 505549818 585180896 220013140 884954767 196863576 334356990 917002006 768995248 79887431 893528985 635355259 256244880 671798867 527120107 98515450 487164502 323246439 332930509 892300945 852258332 800597513 530085167 564731393 706228327 433104121 110155856 644871418 961339182 992768702 5073849 462107403 131496710 6907206 749196834 62295472 12994816 678893912 153574072 504338907 709199981 111826279 61797648 107344489 848340158 653315361 734638618 336479441 696671288 954079145 826711782 282540274 358413444 230436047 70218906 464182297 585177743 852048586 796012744 653571045 655000297 250583575 29628501 210473832 791975914 715503232 464196532 603970097 959897516 111168570 49264449 368898589 584848790 566319428 714737186 704695888 315846767 722300953 144354111 454652881 680512707 690425828 161509129 45394710 479027032 887728319 78429531 720296689 681044227 636050595 118596501 956831445 757370279 520894130 21092326 783828333 447066482 518706989 693382516 870081152 108459021 232839007 645218227 933942257 234337128 679481592 485718189 142086337 362250067 677836019 527748455 321322948 734542800 79655897 733816544 80415325 770343321 479751095 925541116 164089932 533555623 232447237 980417845 49534687 820525703 660069433 129201741 196245995 137903882 170743772 320010134 876409311 659912281 176629687 729545390 566732344 100974279 879137334 333904781 611557670 871209768 731071144 455074115 547785449 407060988 132424002 880705018 144447047 286352978 937724639 164833073 783485796 126964702 201801521 930045417 498795158 941952622 832809311 104636568 173960588 56661354 200320061 232614976 502515849 609150919 276664864 591769574 943477074 922828281 802089764 669760198 956591227 457457433 236036441 698345371 579488705 721542295 630373262 150111322 123654308 332364871 124032668 599345523 384673080 331649483 355790519 352040327 523185 683102779 340858829 64823134 603424652 956609889 131304017 140422312 135115395 245707163 762467703 58194534 220615084 898100283 713494534 722294322 984724657 116677265 908199536 528451743 386963349 123946322 603914523 792145337 78730781 564282494 449785227 671613635 745233677 621427258 799058016 227858691 61433266 891938353 609821619 87302197 850016669 533391038 462932541 836017937 351253274 915588106 180642887 124082729 745742882 709613439 338350339 33026059 55105956 957049323 210943456 460274101 801933539 897820610 898697675 984447909 691296616 141329808 25783124 961699728 857367425 255901741 552686252 222267339 979944657 346695426 235384061 359486598 987664120 477366730 127322236 426454157 120474117 973910850 422298600 197583223 136594232 758861430 651507201 42602145 160252084 7209427 68986264 374826263 207750671 360368216 201639418 297084271 243143969 204252847 777384526 652544557 464390124 13045179 836518894 680267206 710188968 950277124 155958480 776039591 692120243 549691422 65631538 680426371 808389442 742256980 620623643 940673288 228258006 904232586 697346567 639861757 795180742 182923208 835947224 15512716 439345256 843317007 697297324 578154017 650182224 343169800 187660816 513033977 665172961 977373015 583994602 301864795 460234785 644629924 878220652 168738469 53613988 230937262 281465253 389938870 619728871 753021349 681923172 523632784 559815215 29681832 449737272 250050271 171237681 556936950 144958842 685154498 994802753 28908799 282896006 678030633 972074373 32537120 90359815 419544449 179711471 487147927 898105509 323483634 128876522 581007602 799863356 9331017 258602869 920236992 654923621 5854664 701133144 497289550 584516954 252060588 743116751 59882919 983891018 910981336 79677603 184715203 533358370 434252325 854667197 109443799 84211065 995262294 719314339 824236630 496346527 123116362 641775677 167924104 31351243 65598908 183861853 451228047 789527592 753405758 309891782 744972874 583512240 221059670 644702535 582336069 244686218 171300249 132398933 913802339 151799781 169767331 317726270 828549589 484107274 565721574 452690475 33955386 142282126 760043482 7118049 501972747 904514728 8079499 839405182 924098943 139612289 803126106 280613461 536904536 889762988 60244855 974157184 677336685 454746126 728561694 123749660 655438869 468263603 466483999 487654252 893784379 927878405 57978855 20545404 521157784 293048112 627651883 198247332 563661623 404501745 995496060 681072286 453719463 448797157 257069515 794503582 419721 632524300 886768352 889493810 246610811 297829044 577883832 914725631 293167423 23452069 745917294 237333667 593884725 211150506 116368537 228809305 795217134 192360825 433241091 441218259 37586283 785559352 971751013 154086068 493931894 744164813 277115571 808804894 279166637 961236248 501401600 492678880 328366959 258219476 757393425 67887046 547214688 419967931 511938720 237294494 618780731 231766657 67637449 251962656 679990312 738460318 130013544 43815501 806690175 374680193 125233518 96518780 882906041 237478999 989448036 745165502 87316599 492539250 724955547 64749467 887050006 976795287 430195083 801825392 28176590 726754537 408230828 355049637 679869498 721700358 84051333 82856363 733975342 768561810 420967682 445055423 831561732 503609752 435844245 502749747 920280983 368696935 440429083 648021285 298127230 625597471 321908270 479007072 642901180 969117296 823597651 940426450 89014611 234014088 397030878 966604758 848916430 153578748 480569189 65908482 646796671 451469073 384098900 533488032 116407709 714197967 589202761 537242131 144396823 442977969 156378275 91446233 264083265 755299038 551387402 255802502 155640204 45698475 785926963 6283050 133232190 603538709 909586305 843876572 895689953 197296229 889148103 213192217 859494860 435320510 429190457 262985962 688794912 545020116 739681520 421732666 334152604 920044217 160607674 69633568 75744738 704583759 407138617 458986023 342825740 282639607 316792147 798228407 647268337 118475134 710257254 820862375 494157875 998880337 588458136 124109773 908398991 450937082 926295600 640660219 256551851 200957723 333463654 775436005 595097464 991201181 88432723 758688897 751868966 723308400 897877838 202479031 504770291 176088661 15132998 409492522 562457472 510655144 738603258 634512490 270677026 497567520 704325380 295066500 38700797 892119258 405134739 484437329 810671483 157510267 258148700 950263626 733348880 846642131 944819710 732573474 927334560 951412535 379667142 475885420 423528457 264621828 317884554 648474223 954558678 766306980 972125815 410569964 575308336 683510593 274347461 659710285 655141922 779822990 597436828 170728232 745244191 657831376 578095050 144970334 603991430 480805327 737916907 473745238 730581759 267098635 635591619 597415884 287372664 618168299 523699493 384435034 267045400 759152677 113562414 578799388 574760916 569992224 886667581 394574378 266520926 352286774 99483856 217403126 953234393 60744988 259510101 380058557 30616235 925307381 335913482 420759776 741899938 836440900 332763453 509604076 61294236 375991903 231788399 373663393 112918058 686662387 22103834 854579376 43434737 845545934 18246993 145939579 218762285 501214783 753701841 174410611 263747947 934017176 662325640 313788589 96921354 369525082 783690273 747762317 423655924 951393895 322707516 157548220 549956829 434145615 75777491 432313586 697618935 773490910 224269586 838490081 328863979 359063694 262296401 190755475 979191635 315509217 514319440 893476911 390672476 70388692 413499790 151382528 72502363 518214293 700921841 124044844 220137715 282213149 441384194 560503429 719013429 112442491 41409690 36301106 163317210 611399815 671842553 33304384 798137078 155179258 279019570 505712858 92873755 713074261 742431347 955060554 71718 80955807 814544599 48103846 976244567 287032728 452682287 879925281 74899198 834419083 269939628 976450824 310960660 458208021 394797489 720502803 418173620 167734903 121547491 35399164 637290209 737429439 372051915 757913848 550851637 599931164 659236395 400275160 535338464 348174269 541828818 281591068 336447032 882219560 294624073 513160355 234274693 971298087 262511912 232947869 39261037 750735485 425616773 579084927 563681213 802568948 96494496 916404493 865450438 732093310 898558440 528862894 625954144 778722798 105268838 419817439 894441936 83946625 458357832 703999503 994956110 916558926 902376175 989520414 163657278 423491214 442517586 52700792 376831901 142458835 138522739 653274116 58884806 167737211 658225295 325315014 960781368 289815881 218531262 849028769 705512882 104781871 317576317 160509939 37366292 656348197 17819773 363400593 948070697 144331793 929552583 319146735 930825802 528349589 373460830 834427464 525879885 436989615 850653825 608761432 405623139 77779903 219485495 394419073 523768044 941548155 476982944 525885944 241594130 507461007 283172150 733280423 323582916 493107866 136733785 427415726 203654758 144610825 177604351 505245596 237063357 263447428 328475919 118768377 271052598 450733594 766717749 349680985 283828218 554420601 603161884 309503724 920817867 777822799 300794728 681215537 13175424 488365245 66238377 398451436 584279245 11294177 106268605 159940641 576758843 109698618 406376458 156171182 526967533 276421342 775288501 593164524 932591480 205765279 416473187 78573237 489019647 305180269 38977233 842945169 795743127 174360434 35938676 192233492 135901244 619535352 861124420 232717354 543453889 474900698 63661881 447768396 903348146 7466679 52607440 648085060 133445744 858162250 721504576 326053992 999436253 968176527 880054474 398474309 114442809 489169678 566994930 437948328 866159207 254117779 859435770 398862887 86282124 67980361 879767979 375754786 77770726 856835658 221903867 42994138 511421150 289243083 330645273 467372726 721983804 380706498 376690439 969985432 820889079 814757549 735282951 348353533 129590660 166472271 824006943 49254296 45333519 603493011 26913619 656395001 123575909 561159297 735409860 194788393 857449575 199935705 331816523 368425094 579209089 948517503 823613368 86647452 622566072 198275291 687232873 933982725 64214560 829791363 277512504 129897361 929177064 434692392 717620050 580933332 648965535 703557826 33698540 848643681 335956947 703245718 243216067 322760366 688512866 7113537 587438824 388141 222067290 649933836 382584815 158448387 133477601 277801509 350388868 495042722 83336539 384272154 622851180 177428487 919506608 648464 536299633 782018617 9886964 93793090 105103487 70091434 449651440 413864941 386128684 204855729 895293840 212668121 735559450 798257461 100677480 533608571 270824800 812486235 506602236 209699818 266003093 21349322 908389695 976012215 49186702 201325758 33945390 229672824 404599670 414325585 54656759 869596419 450146170 359155134 988579167 698936262 248248034 766130373 986689685 94666332