1940 1000262265 313094128
405155151 444415873 774541656 725362166 995127884 544388532 927434239 837729334 493651910 694283089 351409529 443745488 483458018 570502606 41496126 854016528 956963411 918168065 802798040 994872056 948599331 543285503 877823284 856896172 137848369 649192530 519672051 861152530 435060001 942974516 599707521 906899308 977756264 908840876 567513875 91421389 267008843 566870219 889118556 310140837 543968446 122438981 663980111 971627393 326122926 73000670 313342153 463099491 489617213 760970724 505170718 527787540 13366655 873387580 690121428 96226104 997676045 952093837 161007769 621262248 42467503 960514947 760750124 946801141 377680192 568049976 111143709 597770075 47845577 29575868 421366652 423836219 165005757 372179752 978923525 448510414 165273996 904647808 784347133 103463724 220705021 944278066 113179625 449745698 537239441 15506935 604318968 310639738 812155900 91830066 897948334 735941252 217396224 235725611 483260609 567478844 684052095 540996286 814468958 424776464 972097805 202415322 890697839 395124169 259233902 281227578 650262106 25289251 299518160 754463545 329467688 484887039 116910092 684732699 742814038 56114753 612700437 672795717 683902341 533469845 575548733 361704840 870545345 5134381 961057456 860930613 114606267 621697226 921899661 933319990 147720316 396483910 213751237 477213376 765928049 417873539 336110692 953060991 776376798 159191974 280426975 523048889 847199819 418732232 813713464 592644846 821243141 402492190 852008902 738467459 758117155 323914174 650592204 680488199 883387393 28318014 494616021 205707597 785993455 343548041 447615599 226295495 979521894 251079319 173728171 228284882 104396777 935446262 211832056 166546403 582388726 338679321 464711591 196350829 211541928 75278531 499496284 895865488 808486283 552305152 996238975 232429884 143350178 59468168 742968706 872332783 387618218 853721428 968214799 386456331 84921032 926409832 876301405 336282154 84032187 983682004 160094959 822944558 670794577 271043083 492660014 702255355 122660876 329572487 455732645 812788648 143617221 862263126 970686397 707837803 421683566 223892722 977199712 616814995 296958889 509536108 239512141 193200786 740274488 351509667 128137871 919033296 942410263 638594242 192454735 81477307 969601754 846879748 317813932 102386533 299349112 356101643 968725060 255844778 466792420 842205217 456604686 554639489 234769224 255685460 30573547 596401372 422560666 695720830 20740371 171780908 240231481 377037999 374363268 188943282 765446880 234334216 522561738 551751851 307470043 131029269 189382157 99693663 747018457 443274885 719034687 563740735 461923674 957348907 682048227 811008418 636685910 112477317 47879634 95156148 213454223 511113508 903457296 74110450 538338591 778658134 697948731 812564463 633885216 826534094 750120088 406314760 466815532 432748390 927261595 212278504 265690088 607671594 691660339 46618087 645932446 811318983 514799117 703911053 899223533 758283422 126165564 428360663 28164460 42736615 644587073 608237074 948182573 10786740 937755845 812165477 917838825 895409841 233921533 364142529 132679406 27019816 930123315 797792674 699737385 255076618 55579206 656714224 118009571 541204729 589358812 193089762 810880108 881762160 132202678 509877462 885655998 595913311 248647358 990428909 51662934 349670061 603778355 159062589 639880743 723505077 754129964 66775516 409357531 687568473 429759659 892343987 764338176 428620713 988534929 308336281 153382517 495321174 153062446 663004098 510645052 719082567 995232867 862133039 800721866 23776274 63751526 284834965 680845714 575485801 138681109 782866041 947088559 450459514 487269564 673087157 874628424 312693792 957794762 267773890 58822092 176135570 478219881 96804969 69444929 21602825 747792152 454403482 301750175 729219182 233631579 47786422 633324370 247722071 79442255 979538910 118124581 11727336 848139040 955823386 512903639 453510583 245798720 625461382 998535846 600128385 469035801 887784948 139877466 101800483 768425333 601307018 670689778 343659593 823645307 801727979 781857685 364077569 892351981 271826010 15694366 622069138 355675192 289483739 522287250 72271905 378193127 129146500 491134288 779557244 888447789 802879739 897875732 50916573 190007971 893791000 108229903 61997459 401330920 464978820 356412009 564905940 267967663 599699168 349128431 836906345 304815197 984755330 83724847 887263030 170295655 400754320 928758850 601626152 517838860 432783421 863640963 155568556 249052012 869586972 10789229 648752598 13125634 560737254 46107836 625701270 140343217 295012940 656861805 607388179 710960737 451894157 308601926 938847339 141621335 455747118 519173198 313243983 810254294 332232379 617952343 856912087 431851423 143263484 744417487 605138096 786511028 163355920 687812034 41122137 694776363 686370972 798894911 676348091 533446733 51591144 173987782 272458726 989473036 459057536 749523890 712503680 316359924 956073685 250142177 163665802 544529620 624557514 129356794 837349355 69264186 36801513 115511664 852961445 928395292 701156514 133936199 291224049 38310554 382309922 705249325 179990802 767832381 223885467 20616657 162912910 930701556 278834663 738143189 503984571 765967002 470645161 324723988 186548801 80358379 437431256 822158531 160036071 924466332 590365071 151772380 934693931 704130044 219043987 820008209 992811005 238194498 984073370 490384803 953644178 675277288 309105882 51600433 241978843 362737088 622545037 882909442 21338740 172672746 657726269 535283445 352967223 82423440 898902154 399625057 480590214 106471265 143210399 529156267 286085044 434846843 920877176 126874685 700913153 111564879 327175108 928008938 545858783 945521293 765313068 959292259 845228903 839811759 632282330 378565039 540770778 164600460 62397763 367979935 720509512 571914215 4409557 550730678 835960781 392590671 515193858 142998997 751614907 982806335 278804369 989475525 39689650 540500794 121314372 266110622 564928427 773966770 837566155 763173654 445217354 388285064 333607382 261736914 336317362 727858853 879190071 767134168 227453404 477700527 49636517 894321055 305504907 469647880 1400223 824380441 695447068 239291541 884750601 21959842 33860535 231521703 43206029 662105369 182957262 826274483 442569293 820195251 605351726 861683375 123960860 272403412 636694302 48168428 113951608 319117044 197464225 237088611 71503415 200085858 372542790 71866973 844693709 293146440 778979849 82467023 88679323 933981147 731040500 223764115 543723584 61107474 853017269 537162774 571641552 600637208 793675746 732294602 359413653 963931931 953103540 323891411 915641998 179798419 676370854 47172992 734572177 386736519 445225255 107875170 327466548 139331652 465045845 231736125 326744624 865224890 36498767 188096788 62506420 251270239 919297260 19876320 323583865 82899096 862819276 345065941 992208627 72253327 129349318 707115825 797846943 363600340 488475274 678120518 560093653 111675188 447533624 694757358 964783743 557692972 379852003 735321223 199540399 866326066 435356325 394910539 27299603 975931064 513292340 448944066 305485902 52079692 208261721 848229197 436810299 22462303 839254496 937864502 368131482 939154791 156748173 640848612 177317707 383447270 374672822 392874086 684038861 416700122 480081174 232315719 851225496 764536654 748852673 620311406 574002261 888587077 676678400 833715862 938492895 210879125 976263813 747564566 125633841 251401233 974743846 138129226 143366093 486969925 961951711 450636789 764362992 438371331 691925984 595480821 117352823 321893695 337258167 148253363 744576805 842867994 661391611 495209372 635546074 187697802 328106817 203017189 995852708 331708702 409897194 355618579 732488375 187129146 505052893 957525650 30660511 229289043 771777052 319433704 228485213 107910284 422203470 646321728 809643139 788952074 127929482 715427300 603427550 822105540 646658657 578058795 638557425 770973222 396282040 507756134 507887582 500765981 840630062 114969536 585194931 543864379 529617104 756529860 776369543 49396906 984567899 293430104 862413896 228835148 997921939 18857589 304541435 274900099 160450506 973645719 80518964 424522243 765696661 251409592 632188828 293046457 878912845 116157967 431639060 109937246 719835290 141784891 415620741 953089273 538305332 627719475 508159181 248150749 95157850 437330517 620410262 152033068 663944903 39204809 719960843 576426046 133817895 512992701 445080856 477975015 700955002 963460752 78362604 298973594 759776891 319774066 709608752 841070291 354329819 860851075 415067334 744635350 573858534 766340732 66861449 875965237 340133165 919105704 660129100 561890934 42913358 568623205 57287749 928090482 68571364 420867199 439525011 330211049 298006910 546751682 489046960 908432199 131144393 409164542 410689032 4023290 72828026 952416688 375704751 191198722 656602672 5029398 138578890 347019765 404723307 894119235 187473617 598931345 119015155 183104852 674635820 392025191 727803539 578895613 158057048 515365475 374763328 938099573 841446816 762527867 741028363 170862497 809063543 11827922 404781444 149036769 11375708 404794171 701430485 954679562 307815627 767946546 33601132 80565007 179019124 995148511 909715096 114265889 981973627 163494168 968629865 985120911 264321013 456976762 66281118 556870996 202469591 762675538 221604131 676116341 999695269 302313534 936510739 635373574 111379657 565604892 857263268 137442989 952475843 363576355 944683059 121218172 884104298 70138950 632130783 773095672 930764001 177571826 927990360 689575472 858477374 389068693 937855886 519147845 668553563 886310657 137999139 519980842 269221765 583562143 846745535 101038732 351039828 64816003 786808042 564856440 957870724 868059587 911582942 701288671 531226464 350863064 485068407 472246825 555037010 84149513 454304385 313229278 35867135 511215305 853603853 39747318 387561828 5390209 730165765 971944251 857595684 451246492 756528773 774714948 548368108 341852573 966401730 948661832 749182946 907980434 882252694 297966813 807061479 350149855 164301484 67189158 929106453 908289695 436763617 227166593 377930757 898268306 482423405 473338523 611193572 686920112 664784214 276781820 754913809 426507469 622331508 81156561 925334016 83908795 930817336 102313931 218404580 172976827 727364461 65568334 463022824 111814476 471105998 692446638 824126695 764404082 879044093 316817877 681145221 313955115 360381522 820271463 400554744 139109735 823971580 84620267 516804247 860384799 262119076 313537567 341518240 768526140 952382631 745185647 400133880 890765753 933073107 162696110 944147512 664151573 75795933 938652042 469143799 422801147 325762362 123124728 677186499 294897819 986895610 557947237 765493041 739632156 155306215 700744105 466806082 940794097 917363169 364879857 234295263 400563097 323690103 335478051 530614385 792000544 901328307 93362957 859919048 245348456 98933958 762067767 655196324 420409431 310686793 342459006 732865014 231836932 639216135 818561052 47158725 189253847 364716191 811234802 257293559 864527505 268396348 206518865 78561755 872124394 973242449 882137684 396834715 555181409 377905051 505646244 820345583 658744025 870905471 757804375 964395130 880337358 766630686 305760683 146245737 456293819 772676327 445622776 668441455 259987777 590237432 498638718 760136021 101866948 890891573 220827779 225547317 815654330 252470113 97078946 515375226 981404676 513585249 152582918 241817479 279752753 878947893 285544723 795014466 551318199 764098460 701083124 299105751 280301422 293136529 549802751 806692885 298831780 480281423 702295452 2586220 54740972 481114420 82094200 976485991 320307485 637284847 650112410 657180194 821879645 566709887 779619556 414555522 142666581 728738779 331820810 425014149 178103734 398636113 91972570 877137537 342934946 699820278 648852736 457849147 190619126 180254056 481089067 101299080 949345692 342535996 244753162 118500105 969688718 885292729 627709968 935519392 61414926 300441987 888697386 706832161 892032362 14305921 81228969 584641524 575647135 528015440 66234298 929015157 489148757 734151643 769170282 205247799 623224266 152123225 827285438 316223404 950865359 138331839 985956344 691156383 267397251 134678476 760289530 506610355 634735613 954154429 211310191 432969732 675538277 733253422 73852433 109496512 338223442 296132221 934027967 856645044 662038823 444295607 806315570 147244996 323075766 7451260 112999235 38156839 72171783 322141747 422139759 858640930 678968871 870912947 941885312 218433551 17455930 771187451 583726796 837023579 433392046 487358626 910620950 206586519 60188183 811908666 709038216 950625748 966661133 40970006 673517641 135037375 24331201 287546402 960572615 581530033 57852002 173348896 724838473 484896790 883352173 317900694 552798769 355052460 423173581 470703654 792480449 788720337 841199676 813133119 479051650 803911436 864765622 804255134 742133066 69498264 167069164 338156896 701532063 649222437 636184696 682448333 194312320 274307395 906837614 657327319 579395066 35478522 233128097 805949945 847679347 395943297 709082897 23998452 229074814 905106117 242457890 836768097 70294736 15141354 653242500 121072194 759557341 800596361 657803259 472474725 919903886 613525746 753605159 979645608 789383140 590904734 228020493 891026306 325626445 695467321 336406326 705364446 459491487 281179698 578578699 682884700 658409692 771977383 629073030 235899273 584392444 97065548 315529566 221282416 800176407 292424462 955297581 252697699 684289948 629687525 180067014 731865917 542413118 318214038 991743600 246132301 191775982 215915132 264941042 565202264 287758585 817157413 567292533 836596463 235858183 472036890 398440868 883924296 595107114 543657579 544135010 898395317 686724698 472562903 844956050 121349420 887082640 370574740 571901602 900568602 529558611 959140128 188106365 544515147 736373570 124297028 92281831 904036161 892387095 22506001 69560709 776498150 643085720 670051216 888882608 404348954 556987380 90547169 676679048 788430209 242145110 101993959 903196717 434657373 433552378 724428966 745837302 240704924 781019378 642060564 371189235 555966658 917795242 577088684 261794806 300524880 680828561 672155448 898461782 459761471 748861032 135734760 807807530 651133834 829966610 938264806 44438879 291043782 323583217 579852834 407563486 62406379 649399201 447463496 848489885 255626915 781218278 833193101 220642709 299179141 591097723 220251884 826913369 160198808 271523486 881247110 545957880 486677016 612644047 610649224 585950591 781828714 225720609 601821397 817305003 240485374 707125736 158815449 980385945 55984199 456127255 585706743 9833356 149606993 760030784 368073437 196007131 903183319 79385089 179916682 800893651 850655272 109564426 840167306 890325019 562831009 417415530 20723355 237734398 674139339 840063457 577461118 905104415 857051866 878535008 948671121 611977201 400714071 676572162 686307150 978620161 31632400 313891293 116874872 201367354 65714105 814931797 707215808 644643686 461956933 105941210 126099815 136621302 234949197 175881824 412596918 163238686 752540194 663855939 285603160 867167902 364888691 794554668 625498937 930998079 811330499 996067320 71155812 46792452 426260004 424713532 258129199 67688519 613805934 116337969 538769330 854355127 53488345 64742873 305979176 413678585 929967529 679954780 410903453 988434343 104852424 290653513 426403731 61610223 263888695 184607935 239126917 555044911 924983734 178382620 555846392 235924089 440168612 435333838 916537418 461492935 58376953 275833299 379000017 42791627 109370692 432212289 921700510 504941091 250738375 466955792 915341233 176616958 898963185 246657106 416535469 683444388 772241772 926151815 755509103 253175779 834988269 963763498 296351212 4194945 214268810 447957113 622357214 526923742 678368570 129716920 358201701 595468094 351069735 772808861 435405825 517001656 157394271 459265979 240184060 442315028 79630712 118313568 316210170 920820010 946262304 998862042 146540837 644160622 25518419 291179368 668029886 714659105 240126244 315972317 562931748 89641315 685957032 752111516 599548194 410024833 189027463 312450231 62162692 492506131 589573233 5113754 787983761 53190574 372552297 578122506 407617419 147300820 496277694 981380644 492103084 135496643 243733492 511241967 16580261 822690439 137925470 946773920 219242887 793743400 941440173 827589519 780010381 222314437 31537205 714717542 490726157 682361571 919697258 840226194 18881621 197382526 520181091 862336795 635382408 758444786 575740022 53999961 645209805 355962018 511786991 361046130 972962662 709218483 414311674 527127332 625589443 771427117 714177221 644300247 843514092 456538681 586583680 257448227 121727257 877601389 61769370 958766139 957470638 828481357 436521530 867582859 916230078 831291131 661582944 549625476 521210615 185330468 692792222 319416551 366937895 199665904 783778097 774962686 622582073 80965005 933486749 234815385 44964684 528225375 881948697 988886557 260630109 198534286 869232996 253243808 314305233 485463148 947071691 44188580 647489363 835661805 178156725 195786838 934548160 896798541 188353599 480274464 723480445 353603608 343400460 36330334 324984977 974973014 155033362 582846735 829399768 666654883 109235959 501623547 363567963 8053638 835256508 957056236 865583789 53173706 552728641 2340326 712715863 66942275 593947505 919743301 403860893 871115765 575248116 343082071 777947828 71247108 338870654 953469813 533306473 449078460 467735800 625898997 492374683 43298854 703303376 145907138 74928249 861930426 366377049 207781816 270096500 375076089 227585938 654602279 162532931 738525351 489020298 324145924 193946695 447830458 563451966 8518665 874096701 234565604 721457896 509127977 522042384 389613041 573754796 643850256 592698779 153516730 298730202 852674256 428348050 568410842 674499903 345659986 95614457 760078205 687032987 817666636 535216420 599507945 866444370 885996376 415869821 463097434 636661925 552646666 978659440 710778526 950748635 26616546 949283466 236163805 903846963 1726419 176290685 352772902 687018282 689622527 532526465 398955247 721427602 647295042 527699362 918784958 231091983 374800883 698512090 339138461 916112752 377717228 563498648 636119736 443391269 874162450 495091547 50978799 531118466 45582703 473134933 533456183 807172503 275423792 188931766 353940537 603980225 728436255 47201274 933400816 779434486 571095422 32047466 21642104 181701213 243732405 379950859 551183805 625186176 577701599 362977418 978302423 694501582 566996 555033953 374560995 519987801 869117872 556516777 748992026 357176545 329432925 637525177 670829340 977799962 139411190 429166843 455873733 595538958 804475427 321293394 42391541 101360111 216484168 23062553 535550674 916353470 552431807 725954870 962105426 106143030 940074082 317377565 549015773 130675293 861581156 852541949 276757188 350000159 747086486 28634872 587665347 289301528 437690682 565415422 299307263 920631553 797245076 304794944 562571583 456397886 133094363 820463846 168971134 18288638 761135348 507602251 932573746 93424651 49513630 628082513 225299579 550516567 182595629 751210253 445228312 768740562 239972735 272897804 361668023 185793307 237586727 424615130 53461124 147588009 254424963 661123804 159632203 16188895 146658412 193569380 449531587 987136631 199368614 537164831 119924907 931690901 107918278 856998781 96415302 365526652
