1727
450577124 628187571 958176924 290036775 420004609 570116589 943679421 453426256 745161306 43539101 564463891 245668666 289020983 355841974 296758214 285341667 777767740 555677018 288184700 347793571 108954656 72024963 975899242 575812289 552712638 571218879 809607716 111328905 823872988 929456312 940086924 592919226 559579040 794871621 590644266 593961154 664033407 593758258 646529801 695805393 70237018 827293322 93471997 166504242 494818778 626775890 280488141 269852349 384560502 596627021 721843241 914137098 498299228 663702539 443420581 409033917 760145719 604209717 35660516 831041076 273913999 211257189 501672924 586096750 33368303 675695978 443410056 951108693 213837274 842101076 522130404 514246658 440029312 863946847 283830410 533042854 688388797 737953250 490023297 392409696 262036225 444156514 825243099 512367583 680806547 435334371 793268540 863458363 44393820 88104389 803281772 290020728 860931245 387881396 604968351 826710871 43858722 757163549 592173609 608834097 531596804 448696836 167954543 563109804 589853671 395462281 640362303 26223867 341305701 986440927 312119539 736414390 613049120 457163554 274105497 83272947 944955601 895594599 987683694 610645588 108571698 73863310 712324206 978725000 240247714 743920037 612672408 38916289 394321654 22700221 491345322 818428735 680256689 582398100 403472074 591107393 820920670 124039396 655082239 73291085 11833622 292608343 600765477 675144717 44933993 769143387 176896950 197252441 818669428 962870995 918143242 574368976 903926542 516861113 167053713 29128761 889974463 920630696 50056786 912288119 760063867 886167215 552827930 804884485 668028549 574980952 457814874 10329292 592219016 189537053 410637531 140373427 482364327 870360151 9403524 739755774 352387576 136884670 213049636 185996295 98117675 745044112 877120572 751527709 505019798 711925847 108164751 75719274 888058203 558440412 245859210 586164466 138777177 452929844 890566085 665596207 982871617 873718805 284754805 309031895 318615408 465148558 878514621 499741361 334770428 776733611 264844818 850751518 66210145 110396892 894019644 33180120 52674238 220025920 756327499 109140228 234687962 409517859 420314302 298018406 576447444 188402008 592341408 907506422 194784708 59823716 615070587 516220295 316641203 902853037 289698892 349842118 644199918 598104856 670083819 171121754 11498210 406263911 215883939 460520911 884046783 484817607 51731996 572634993 745286569 434478661 821754958 135461352 694286638 512810154 754643933 750993494 207604975 395848525 161267578 436468608 407874079 108498549 568670844 542404282 338277810 839619227 721473604 403326136 407562751 488976982 786785680 49187191 602489729 787825433 328900990 210598837 615038652 582427584 131012160 305658684 59438742 761747567 81601683 857868108 671326620 712496869 348203565 562660510 477560121 490982573 675229448 433017550 868561393 830662736 399920389 289065743 817614337 661485861 385338706 74104549 799400633 957544449 934002775 9206236 760759097 586809 853501053 614575402 549112242 211143292 543671678 207845525 242240292 638027900 277166320 933279794 183741025 207036223 771266388 222659930 375451409 474206287 189873412 264035 168020993 451851614 460091349 722708994 711688186 763324025 991362279 840286540 249773975 454041798 804421254 110615205 117015725 712524986 972794163 899410406 594513431 56752946 719052587 589548512 143348666 834599784 97915778 23525510 802398689 41397947 456745122 315288437 399647760 425315342 33343857 619993869 503684881 16060881 657158909 671874621 535474138 980500889 447343710 9481806 362179972 139396331 271320891 285096289 484937564 367887280 218578200 91913130 688236863 376148567 338609392 538946516 155485899 533891424 590940663 731742051 361472434 951013268 690275538 101807730 388213941 455972847 467391276 682210636 668992011 515067619 709765087 704744169 451405971 901985491 950213708 585933384 542776365 496765428 298564646 447987986 713402155 285888901 605619932 740101915 228645209 546151606 768821938 764573378 738989183 153529599 977828781 48753123 351746362 660700910 730145044 375795477 101648650 397641345 788440436 470475073 684395996 890536104 345296062 916811716 906980173 87506729 991840179 490028761 421274643 628444933 309798836 421435957 439565886 27422344 4548719 332345726 494499610 859019913 840499708 195922501 939367383 221588022 65702902 725010042 974384480 763320278 375902987 513891860 292829779 129825990 246472811 380391002 4015733 66315659 357033470 639747075 334225133 627628153 211509693 145364911 721109294 883577646 402135670 337109341 990660966 753204000 716216916 666796443 242855344 109890499 248831470 828992115 429395247 870008252 63189471 643733129 290688579 586029244 701850054 429667517 103549300 841681074 629298257 930473967 596503212 101815687 986573821 937804498 671691330 741505076 529181129 700346019 320140318 134388324 789887408 203827936 440393690 731673629 834840461 802923563 525720320 83578406 994368024 652591686 8765735 744337385 491839062 117546451 970271536 283205947 815239980 640295883 724304655 200849435 969565575 505669577 606222319 918055207 806643992 982944736 81072684 812145995 853137469 844274182 859601998 16855015 682135117 992674009 195804623 849851661 392997835 837639389 346587258 946751398 115346381 280866832 620458739 491786610 497400884 3085329 106492028 217737570 450859906 664149002 401447347 547738406 818698517 186575255 717983758 537224155 902717260 918779196 723608681 449427179 902943980 908186915 323073790 96049413 544567220 18704858 650089675 315722933 666360488 135947245 635668330 605693668 21598977 907487827 904994094 349821102 145810030 342060453 445751470 942386068 689280523 37977670 909312066 414343966 35567739 745730995 550005664 441459922 15311589 745316294 12915739 640927685 514025759 147468687 771453275 977714905 916817502 885119116 64173727 486951650 556383651 785440287 181719848 708732242 961212912 876037596 71743660 136143716 919213142 268325967 463365758 131745957 833375837 579610155 543999911 678516963 755101188 916910031 709316277 620717822 455040186 213628765 374078611 379538725 617336609 525875326 771724413 954887679 93001560 564393404 669157024 105881554 915859720 876573728 555253005 637844452 904917764 324023951 927505031 533315427 333142195 369090367 188815047 309385136 915989583 7373957 403299021 434229273 529278467 534785098 501198314 665925295 661919650 364733443 962780165 913594172 415824576 752988240 297475973 707949091 682096718 699613824 692158125 584165464 706165328 853061984 651327331 533733383 955214698 34332019 303896209 56970633 200019088 639711892 305699189 18506253 369585281 23668148 645530449 532864978 205449579 425284155 816660935 333304274 559406673 751151459 427250283 757161986 518840900 362919591 132245730 652131093 804867354 705075004 157253409 234027359 151137355 74753230 134532907 270133188 51886472 378539303 945846957 517344783 188294381 605967993 378318481 189439866 917089711 923222215 723382485 465517341 215149118 472889451 108111240 70402296 947861186 948252252 622880955 507667099 700911918 876874109 972655112 61271940 101511370 419388089 455185911 789916904 893480666 688322535 930806123 274635052 645095770 778361348 567450588 249017388 963325273 435019438 669123230 664873313 276575145 675293406 178940818 477819294 249572507 749275879 172755258 773641820 50314114 953339719 174881514 451972810 707817743 520077266 769319946 141957813 248706921 43854461 565282738 761509061 620325393 291496053 351874413 346107570 176162278 941842225 310999164 490233020 890514521 649756461 855142650 471636772 25688126 938511973 834142791 526727121 253635676 794198676 935980840 570021435 521548182 222490630 902264505 539702334 176545006 704955428 583164341 863169401 690254897 957005884 846808437 732343784 13755176 458535957 932614000 300068727 26308092 678673777 343064373 597434396 541788500 510801378 435804465 152649212 384091029 854281550 238064635 400874995 856988046 400905803 18450662 461843191 495370726 58698838 474487859 746397972 789258972 249354259 415256241 742525425 913374112 553320569 85089788 140906752 832265801 571680022 535449246 789479915 711961830 408243949 759831009 457116027 644219493 220469676 204307988 165791244 261962365 352366100 497136633 495562966 859156700 193798827 257991791 606674257 337919821 856842417 985325017 112618292 693293140 913025172 833524281 383910435 725696068 641058852 339483127 384288673 395725557 577535469 996577960 430826202 822019994 770757299 735335970 67032074 792562564 255765846 559161087 249258223 290757514 703052328 468712231 165337661 390424127 260147526 295889021 253385179 101140301 356292692 743402062 187507615 609169510 715179743 912590602 424228065 637222660 704463617 650886903 771238019 747717714 109200545 495768290 648080082 493189310 339655531 114841813 570319498 170789957 845967777 22268023 886675663 402851224 496173473 544689676 911446475 761565760 614622060 661846387 25623594 536844998 797058085 966832590 40575816 258848097 728229360 83235929 29206564 758142804 127821693 162546876 400312518 459406082 721242616 121230442 89132646 487799641 967641091 509328420 468530861 955058476 439804861 170670791 220292874 778250879 941556716 748788529 832823270 666274726 902390774 259341520 295245344 514013341 333060135 36678355 58785160 36104517 117077242 862385241 220905637 729755248 132557856 261903012 860309801 483091225 877010867 90112167 422596620 690911527 292839917 79277141 262171673 741643086 102020347 866366919 622443253 581415924 12644559 443091170 858828134 234367687 325172945 325225393 327763352 843039555 969786338 919029794 87278311 473827710 344626238 522593235 326481475 545615343 793574695 394599616 217238376 35200761 371635451 185828970 333897291 446426258 306679503 707288673 186200161 482856540 735720833 546470409 705151596 685827271 756086163 684861904 503402384 801592865 128540862 476853690 898504010 134074847 634506467 957323603 663593013 889926123 295430958 391179860 15838825 171238220 14471917 295051174 920115354 525083629 23758058 370925731 159909542 476527972 399002157 793299434 157938678 621693183 787077975 365232591 1079212 418849687 513863352 684295109 817647521 354896604 167176586 698205385 425956381 805941235 62691883 88690997 561578185 159324922 483496796 337959086 359616486 992072208 277769914 451309769 539744743 164509639 845912418 247240071 914612528 375215045 398224296 462427345 15628538 953694961 199366380 888570222 683227346 362815846 68038965 958657344 249770426 883166005 212099779 225935990 242111473 718957151 240380296 3118071 297035169 325731898 992686766 349185153 7402684 894165822 427654572 624315274 767360290 909665803 101617213 767272851 711019541 677076851 904703913 327274369 899301703 50770441 388904649 626080763 16592998 658161157 167739003 567206824 912902086 510223591 352084062 958012589 472089881 588285599 615126091 73007185 137095793 139876291 406422020 951948411 690789449 217418862 594868630 360666481 241835922 504345462 383436639 13042439 2676290 636644916 486505444 826344666 854742693 532445717 945761264 545705323 979188787 788952269 585002126 646131004 332285235 44126813 110596506 616159560 385451680 56224977 297411941 26362509 538954975 758384508 98684256 160034718 393972051 849236222 882416476 907050476 733468029 744532789 378432051 592099810 762696085 502170874 730282378 660544580 720950266 88703468 61638718 434796121 401534940 664893877 384245154 996428273 89750717 637913120 927186236 578803547 393123606 303450389 832267743 335653925 496574159 912646090 5534709 293259595 634909101 800705467 389030494 924866151 615711181 789040815 689756005 100861373 841688278 195643413 197182889 67945639 615400821 591181847 709218163 607635381 43779011 305545766 962127760 877326638 367525163 383768861 74959043 261836137 317755374 904391804 899004138 462448724 499467357 70272644 379195164 257138420 343300227 805938038 45790906 819481799 631778557 970129589 646512147 285100013 663221961 677076184 459502385 498644998 895950337 551050995 919031982 878513629 31039195 50857979 978639564 37616629 922183438 912854233 215627362 780045411 980393808 182755933 213517170 431902631 381793292 355405294 908014616 823398783 938259769 245433553 481063733 449916471 607281530 930192561 794051217 330274290 931765598 774344233 516096877 771164079 905218359 104400804 809496354 594456964 746835873 714369698 777978820 339018145 818854928 142933965 586535201 671935784 684177657 102374963 835557406 596121012 318684697 170061991 493082838 973240624 57992098 323031001 700255634 584055967 962245676 585355382 481408000 706032493 787396217 458486808 94677984 250179817 96591443 169997838 847728669 81922730 290257548 191367261 585732483 61018669 740230047 503286929 306263496 548212805 283747585 158719118 278203574 686580306 456941838 555533456 743966552 483723403 651420926 6598727 639861350 745766056 155512550 406702935 555618740 22862374 442167046 445832861 290188281 145415913 803399210 466298509 229947203 221092599 251526397 56651818 49850254 847994492 573238293 832485221 272369819 912337539 853024789 597980420 82644620 820767284 389355071 928019706 832377345 308714021 708423709 395650762 42875678 905493600 133045815 258783177 398822319 189016489 239211854 806881938 136651714 716636189 195585654 622078908 108156142 8999550 721961761 484753539 129259240 905142321 103946819 736989563 647530613 903489279 851043262 631360795 471939313 529899593 552253641 312139931 428571310 538922113 508116816 385219360 204928361 861931862 199999980 970431818 274873562 899406801 552057099 493204840 65003214 650806442 164673402 404687839 586390413 378350103 941718110 85004169 755803102 873162747 671769324 947217756 621564647 613075188 831086990 335162369 100414962 285917379 822710612 398642533 735996373 71664634 677144857 435501363 609457439 848155714 85507700 723183559 963433455 625610894 736914893 231262504 39457115 366150927 218448960 397261968 523605389 435814630 78991245 352243224 587420375 61445288 76872791 594361561 444489625 236317599 861006304 213533940 102376571 879326334 410665875 831257769 649654147 540165671 532179128 350145035 181706483 70930818 909408500 560182797 99090485 88626869 490728251 712673762 572898539 260908639 432160596 343153159 6073705 844859557 449722464 539956302 711607253 211515196 187539127 154655936 517705412 847794653 913351755 394126015 253680081 459113864 184848449 986760646 820783594 194814694 538884063 229298370 56325892 158538424 139561668 276906929 784742479 604249092 493062135 78484368 744093329 692414353 445831435 757110150 75172491 261809420 399476696 826724826 268067256 447956167 210383590 636088939 310519140 132737911 901899315 509382817 740481801 268196662 980479434 856659628 936910338 343787520 419434251 362101859 771338811 413627096 655378670 943297185 344349726 627674910 337611028 657017720 582016730 926646166 198834318 728583243 412589438 950099631 310021436 874694332 313408916 92537580 946424559 677380062 586948157 449137925 193354050 125969742 484974160 560480547 432020228 598487709 288099096 901529998 382881007 3939274 719851157 544026907 954533935 584257205 387782968 516787063 192888819 10291441 163516726 639172458 345373448 828604783 564549440 349103144 560873915 774367194 272923455 35476108 814830368 476770988 259025835 316509207 504408518 822206342 93562006 555578280 681137385 460321438 727252889 585419849 255022496 397043895 563605141 996164766 527726492 443728758 369362125 629830987 747221349 907310939 786419478 654190086 688367553 488484142 989849242 147910468 748053667 886886513 422380658 191298729 256785949 703342195 734970865 772839016 268986161 577922325 300583062 101731494 189413154 635187892 521104848 863030141 187668249 883495476 639461766 244216400 216796950 424692483 811416449 536231946 939155001 511146021 384928217 34369333 120546121 738698172 485140776 401682479 737457308 422750178 323479874 483204958 766239714 745258526 419023770 736043002 761851117 955872060 761228394 956528432 466419563 859957469 198575632 868061321 697974999 920567323 76554566 6119236 847770034 47096914 321067499 263722260 280218201 356755004 361262472 970148549 974410273 499520262 306897160 87016750 434352638 496379895 575136916 430900583 541406651 575475716 976480303 577117062 159297931 483670315 492743224 221530951 643627655 6621845 286341570 877191485 69781447 664907174 913574065 312511805 600400815 852967520 50791306 305651694 755276272 233371469 408474024 891034159 365493759 648921644 551725234 613378179 523520312 229653821 338081229 273501020 225520774 417204323 972705173 388436565 991019320 244983719 552324364 112834349 841516025 814459323 491471265 357676948 871210494 763535989 998000497 265889248 481275909 237570958 848031807 632757177 694700379 374385114 919012698 886868460 719579786 399963569 60697150 907976010 526046688 818706227 570546951 974029003 936297329 854470374 928872494 400892219 618486096 26133139 799801411 726728722 653097179 724276952 183841189 943402763 655850346 439683756 457892073 513232598 682493623 344716280 39598224 565282931 558934523 728467366 166537247 683197777 888378536 619444482 646250692 589942221 453987055 963230375 360017903 899481400 263066583 278887687