1352
191785797 280174215 62327579 887733012 634317019 47793819 261886716 150429791 151859992 327203394 22272747 11757873 873383585 500776711 979484467 808843152 106785200 7234004 152372597 591274463 70477533 79607580 167284959 256703305 175422211 766918495 583477442 936170264 21713716 811931819 980632586 213499513 92106033 895476519 101232524 578939406 795786692 215635594 581885552 947646684 542838988 604158299 959404557 268738927 104935009 791405377 77582078 64236564 798639381 82471030 655511027 721633268 162078610 822795986 978336573 337500822 442230834 414330368 126187439 463944550 78778540 106820024 677444063 23400928 854812897 631192942 602340334 503115943 846828536 36742239 450762626 242183878 640900538 262683537 510922805 745835548 54088913 441021237 662588466 705244649 523492267 170615846 279394270 685570878 993411833 110247197 875588054 288159020 524577565 1775492 604619925 603356106 961111872 134580341 626757034 668441122 765773283 81613721 171557064 465118173 118355961 474836045 707302051 759256499 737519582 70741209 357608400 644124849 511762446 20196865 201885851 35254713 43329066 333796476 573341945 36740898 444043673 448929998 177416272 821137592 303221844 782036197 277010051 264333715 916616539 903767085 932774838 534906175 837897161 956848256 852540702 956253122 431684300 412359106 568025974 21720235 483100315 778150729 518361439 994862762 650863948 720247290 30117474 694193014 54043765 455975773 583450266 350603792 904905771 760866539 24257738 60643968 395419089 301267789 324977684 164551981 57551228 110268875 551974511 895448389 67117130 404515212 704217864 351317785 816874319 124760191 225554374 152490987 902910920 743915813 147353748 553774868 316679457 29987576 100484235 223239576 485963349 683934502 573843369 243385473 297317394 598101107 304029442 692736483 899368896 481523480 709804819 956920124 591792355 261779329 704884866 511425839 518810895 409102729 715259978 188201567 533862921 940814353 340692555 289290194 684730165 488046303 843065062 1409621 370550234 943549298 77165552 856513583 480000153 651008921 952415411 777317547 101626381 108961206 322570383 853511631 590484686 32375201 662948109 34793394 146670884 367832974 546219233 665481780 629452058 113995565 853683347 15831332 54809917 194375901 305121526 592056436 534938559 702942 445982412 905488793 944252240 523147964 614518729 276768746 26673238 566934139 54086292 128299619 675895345 376656675 981811250 118896384 261548231 497275712 153689778 408219115 865108687 699909012 73700894 347077098 813904577 927384242 362908430 721230848 974276497 668029956 313287283 509215055 668732898 759269695 267220201 465501491 134934012 881738931 742270237 161607250 301189423 796356529 289906869 977084769 25529558 124234473 95981152 287077789 621510185 102187285 695296904 339135225 802096297 621514153 686212323 468517227 401414748 49120752 42264428 375691244 569667063 355551711 737422654 238399960 967337761 4642854 703901452 102271772 886381785 298688042 263879023 40087562 95044571 406302246 17172330 973090484 530536719 965669837 112684626 4563258 67857121 807981530 196214837 722469772 282012036 882427161 43503352 683426784 784064267 85767780 59118028 206247683 293835846 649057036 444647644 261173606 653699890 1065449 215961732 392598029 299753491 479840755 432685591 247314416 886143002 302374275 72921253 269196074 120560465 185605879 126275686 40933941 993587410 322490524 615920067 128115799 57434038 659423420 811542584 841498305 597707554 723176966 47745988 891543400 372234001 344909986 5233359 878450245 198491789 221195092 123564627 498245280 701035847 556250218 598076051 439695202 711140847 670997304 561407631 831701313 856603184 687683317 725151608 702706947 10173840 341071674 830822746 67607878 853011448 642365329 761622538 450719002 218058648 661884880 194778755 590292649 6794865 200012115 321259248 57803008 421207207 444823875 556048288 122243053 1074093 6640692 414454610 564731294 677637997 975862241 248948960 534241180 516061911 974100568 89464480 526235752 167688596 920287226 446359984 20700043 415168909 207982521 323935399 633227557 869867401 518714155 76036560 729178620 718726270 397295808 786981628 139933476 842119683 195546270 114692883 695710130 202186962 381663847 260441424 879824959 210042441 509390384 266582492 726104353 336007306 356046972 104856458 503695902 128850552 551216442 524395945 544019461 759198964 848331345 177247017 481582718 219561853 253283577 63277692 938288123 650579385 702775674 78221598 345215422 898321944 45430835 40925551 953025261 427094683 153883329 685366573 637137124 663273714 951949066 215757830 999281020 160512391 320614288 355493275 289362943 871830731 879889220 833382404 483546048 580736918 863145776 965128766 800298771 116429352 880922812 591103247 619525092 583698486 521841199 964740514 334536783 567272035 858182419 140078397 846883072 12065748 825444971 336536549 527855816 629910390 552294380 379653189 790422781 872908668 735146464 932302079 744739398 467552037 618200836 80801799 48288955 481346611 45930565 701104080 450292318 779369731 144723681 922333764 215584570 666564880 739590631 550121354 86353268 597773049 690199751 933236340 462355151 368161075 269772889 990210967 998071465 822067269 369864155 641010600 547492290 105010618 573312678 144748042 425079010 44029867 225549841 325884319 525376479 123996760 26988398 828185151 903366492 24228433 750518914 118951061 690793314 342625898 521588769 777146582 940398947 64304874 710382922 255270452 432465949 832672165 245481418 430537414 507255787 467861928 71548013 54748076 425388900 497377045 199496118 850467910 541406912 425045960 176352228 919299745 549042720 55856981 747484895 304925565 80085414 350520162 423876627 770878728 693146060 945465396 400541664 486061361 9770269 110924585 741331813 294752573 796113104 839329585 725289987 303368890 307191512 649354354 210633320 732580413 999247753 410129439 435564676 393171018 687691753 611916905 312470763 89250826 520290240 912472012 394176392 600375654 115508528 818053019 223770736 808654588 616034768 624312400 147232302 478321392 587753339 741080469 773073965 236382796 580410054 350880305 539751686 740117920 852751013 750385006 325214686 851998765 13030798 760779363 97686136 700722551 225212621 410156899 789973378 745502861 175145265 36666123 198394868 290653793 854719142 422165604 99308380 323270263 898994358 99057037 654108009 339264050 840137506 279698327 575646846 273063913 630578632 115398531 13181833 335845998 718299892 190912873 40361116 583847044 951692236 138047253 137085949 176904856 548204152 927059327 922407717 723349417 963725450 120802585 14003209 670960945 395484543 965827945 846747562 146995255 917401336 500855571 486259305 610055195 780553898 61906151 883119109 263648884 29821036 748817296 599494882 600637282 939730169 639855999 184484326 743938759 777903252 321570275 920843615 178623757 101145955 695767686 754489529 917387759 669086625 621009092 440865057 917087522 439353390 287612618 64082776 356754725 640984543 550342082 966809921 274054795 464764587 702445383 537703679 494585623 303779032 989714915 95222905 96025554 482087267 132223585 839964313 112506872 306310214 613324282 291130630 407456169 161608321 45620158 177360281 683211300 519145604 618225338 600298821 958498995 905837956 516897952 167770073 399338853 67240033 134579993 673393648 384520974 689541730 63613680 879106597 845837116 53328594 826845856 941862671 535415862 811585795 634343337 647922734 117896008 100183972 791569718 377868531 114308647 689706230 555228812 797519947 208851834 173454149 250335122 19867182 931808460 767233074 187637255 331147312 686989461 174733603 4540959 71510434 864275333 68154639 803133385 562628803 973999588 482495595 357007827 361931803 294081389 991351164 9854537 264493752 944051491 653940609 642362283 58360137 343646839 197591095 855880085 405015027 223561598 106215206 424882209 155370057 725964634 612519464 339033723 412954094 787253067 196091036 336980882 504044754 116762029 140114266 66673556 90761617 622609861 423681383 452693420 769207605 267548900 315064311 33701356 64116744 969004921 676063639 122476882 165168113 726171088 830873321 570183140 949732687 789604881 995065349 105102743 515569514 460101166 296652821 781039962 247354233 492743857 118020843 751398987 609505887 110651463 670588897 700267504 733261325 94270279 5477277 354985283 214335533 173057943 388686639 278452278 142062863 917266632 253445514 159747330 643437720 84318834 582446824 445686760 873923715 430028526 403305857 242009582 890129692 699958678 23049543 137483924 192702535 993586741 741399265 802208422 104238203 264504515 354992279 690015882 211291148 212985910 45001164 425626682 386043853 286204157 556595314 380623070 203470789 810040828 540370400 699424863 894359662 122817223 145111622 620799730 405362103 548417479 715325666 295491795 100892511 590891563 285492073 293595046 584478303 879407693 948319822 541232860 143912207 155828454 231248742 355203356 368814364 128766260 633346392 754858218 414970418 189941705 135481287 618441207 999982533 528368042 170382423 746858548 503701619 315494045 220174631 909063723 716427878 935500297 57071871 817320389 378908213 342563944 110915434 963386516 74487990 911751610 357135729 218400198 67580063 588384471 426119908 436394428 717150732 59466299 43768999 132121149 101924358 179250286 603078710 101906890 707618328 773461133 701281792 63836301 941471532 773972777 972900024 657899409 561989427 29971894 327736152 940897640 225052192 291167940 756800509 299540183 202919550 113936237 517940381 123015967 554837063 944060289 559410395 124504148 856042942 603179394 109141651 957967300 634946035 712220361 912390544 195080716 338197847 466188689 258917017 132185732 240161465 231817040 790085141 802150892 114305288 117821292 595564885 339357481 261505587 352365393 638897664 464425137 318817984 9354398 587441104 873655047 953414687 999367854 998159195 661973982 455063601 107300845 619941281 90009635 672037560 384848178 285090352 10235406 851036867 544007369 142421138 91198331 628340764 785022634 745865577 742646052 755360280 193946815 82003532 16865866 546312208 720901196 333807357 865130192 730255594 773764816 591301593 536186634 773132669 589460787 50676969 80712623 549277987 670618250 170722259 221315546 55466427 308328965 84067307 759019648 852336334 79004799 702734333 333193451 716543787 301116263 75839503 324420421 495063078 10359389 193802641 41375285 731260586 527609999 759021832 314032533 153891168 202839778 702735522 927023837 792300565 753412491 7736459 194094905 276547095 30975072 415410452 184529876 339304037 351994113 943549525 44156725 430998912 646283857 377350176 59053 947400121 305706033 324479474 294979552 316065423 518282115 188871192 47326008 45892113 947893024 213874895 52299635 3249155 916610417 979323472 795549720 522539262 839576286 989644626 799086357 723067712 257571431 983616233 62371749 609565544 927165757 959044829 893080810 425965968 188911358 893139863 225882442 494617392 217619336 520861994 810682815 735901452 709733186 710525177 634309919 510142563 924400072 686609555 513391718 693526843 518449380 161457792 68582458 210542019 3618771 867668815 933609732 113706556 851285047 848497835 723272100 630967158 660059017 468869263 909449480 848970375 362009126 135331921 343587766 432144816 508710269 6786934 20562621 70959809 717312111 654872541 433618726 494228537 193998449 947010445 40271733 564964183 960984591 108854191 775506203 964603362 976523006 561632288 78309917 680324406 262646476 654098371 163807917 922705493 122967633 73257396 624192221 337493113 61105671 967779988 769637930 422332295 974566922 790200551 493292104 544395387 297589445 926910830 38623923 344104248 726437628 78895656 909068432 539938572 187749847 537090988 357058287 16789206 98723275 287884558 697113612 213886105 941982929 860921530 989107952 917466917 934178926 613300172 107476383 847800952 433596513 729630667 270133246 260679789 372347572 615941704 805075176 669937017 395368887 696215453 14041265 121806515 775111109 775626051 514261441 815377310 312717038 871319729 832166516 263956667 159204286 529280127 330359126 953703570 242718010 319467077 723686840 29413290 785283603 831163223 877214242 71396470 413310244 147347487 332076259 785657816 615805545 989667789 308111186 11174431 685883241 174668805 985497301 313510703 950294856 499758742 128888012 115528247 223594824 813570882 379484914 382799110 195367362 709844040 189019033 438085373 881827471 912705873 467498663 667111074 596385450 344712904 738507544 9695693 344576745 923100157 795353509 960382290 912767945 103464694 824073075 451167539 130649854 809570376 617194596 80944709 161845471 598598962 196472957 385440295 412169843 428474225 620755759 607537205 138318265 809774793 45622577 872662090 722480665 365637594 392289517 171382468 710350498 130797060 181078161 907443597 906413571 828948024 720342240 671697869 784929073 544415315 122865407 915578927 206502044 592576357 996523636 220863869 191175318 45512946 606304164 455861515 473987172 79576276 63398720 464821791 889351069 961537652 190000234 464348088 179691600 582289752 635730556 890042098 565603166 816808718 650002049 472016737 498273095 370344288 143714605 283202167 767275957 119096367 51297447 973778001 564189078 47821083 47158223 755364397 945850384 653462387 63742265 272353909 733038664 127140985 737175700 474906086 941194992 927175935