1648
675560903 561698490 344775689 459979109 459979109 459979109 233594545 233594545 490121623 362931482 362931482 362931482 821035900 805684189 656256724 656256724 413475042 46113999 133403868 527450793 527450793 320307513 997327079 285936269 453609378 43463176 654005460 486938841 385691865 560859537 279719791 279719791 944486287 269715432 284667415 284667415 284667415 475686581 302637686 826968682 381436538 355981870 355981870 703137776 3792099 3792099 3792099 3792099 859419054 859419054 491758030 113043475 832946254 832946254 832946254 689782294 333277081 259796674 802408631 535345187 535345187 354495609 354495609 211681797 560357046 176146443 176146443 782419672 775910943 679068765 679068765 120052116 712618294 45571732 45571732 120909329 131563673 144424502 144424502 144424502 478128035 943054866 758892154 400036743 284581284 284581284 284581284 87133709 87133709 431260304 431260304 748980641 748980641 748980641 223836929 861508255 861508255 835318701 608850797 561653322 561653322 561653322 199336719 450601406 908090001 744927229 889691725 813611914 156752434 156752434 718448786 750578578 564272237 471656412 444785339 444785339 946700970 718988235 718988235 718988235 718988235 210327406 210327406 42564618 405501067 681271127 466711537 466711537 466711537 442341105 442341105 114797356 425494435 425494435 425494435 872156797 442624966 777782214 780403528 86793545 250126454 579649854 579649854 579649854 740537486 129612405 484598988 906472619 906472619 577936872 714138068 714138068 993999463 993999463 993999463 666377717 620425134 470282255 571749325 180274921 156713533 217838860 217838860 22971982 22971982 820859521 509215495 846778539 846778539 582153101 582153101 424429699 438824121 406960509 406960509 406960509 406960509 406960509 56715836 589329181 599029328 613651231 613651231 613651231 309494414 309494414 309494414 267539004 535662320 216759029 510201131 510201131 258274085 258274085 523790240 922425279 678733932 678733932 678733932 678733932 678733932 680844902 680844902 680844902 827021985 17288988 895482414 895482414 609061929 11004516 11004516 968062613 912128339 433144074 106489082 106489082 657518198 657518198 598632545 716607390 831697314 88889742 88889742 88889742 629254293 629254293 629254293 511297921 310430804 310430804 858721 665174293 665174293 644265649 744622504 744622504 744622504 623089681 713161567 713161567 713161567 706643453 706643453 436968692 390867333 390867333 454811237 837958517 872008398 932324651 763341505 717793474 909393190 508996477 508996477 709423680 709423680 424453607 586213480 776066832 508823919 508823919 508823919 827041354 666760801 545382133 799066087 401331495 308934786 868023760 801891095 801891095 220929823 220929823 220929823 368232676 368232676 513249054 513249054 102040600 338817726 338817726 338817726 377566836 465840804 372525932 199909475 199909475 180701552 180701552 180701552 444396333 368565372 832436307 445538391 445538391 877500264 345614872 856321955 236624143 139954127 753546619 367845845 141613352 141613352 144352812 148852223 773949792 210245310 398402567 575452092 575452092 557333044 307228033 307228033 455391471 455391471 123873712 455860559 455860559 169890370 703119869 418337137 418337137 180587288 922773903 646258051 646258051 525723573 955718351 803916097 822135750 157475385 157475385 260835432 5754901 924492446 924492446 400093145 653219211 638963684 177636878 948073512 429322932 754126409 754126409 754126409 754126409 314526742 314526742 314526742 786717534 786717534 291940914 19356292 139049461 755904109 607467895 827853704 827853704 148134179 442931025 150616921 612886331 612886331 612886331 612886331 480676854 426832731 682660390 267033053 565813648 784306752 182639400 949908501 812430882 812430882 812430882 154380936 154380936 154380936 154380936 9367150 9367150 9367150 163342173 163342173 131013392 131013392 68893784 440315490 440315490 803890600 347706316 12729421 12729421 774410940 774410940 774410940 627646229 688569731 688569731 688569731 688569731 688569731 299913807 824090210 824090210 656313822 923516796 923516796 322742268 508639222 508639222 958802461 958802461 853775665 853775665 90042029 639806957 750313160 448367900 377747157 377747157 377747157 377747157 318695734 562503478 478985107 351848422 256673252 725820960 950551224 778908579 422624700 422624700 76694949 76694949 764124096 764124096 764124096 547559407 377452987 944385741 944385741 944385741 273740842 579136578 579136578 579136578 937752887 44440349 58836124 58836124 58836124 60269139 919364632 834240119 866573440 837415373 505327348 799947771 154132210 427853900 427853900 609515953 609515953 609515953 558971614 558971614 558971614 558971614 126481768 189727048 417952709 417952709 417952709 951298504 951298504 951298504 985785471 990835345 990835345 990835345 676296967 802159181 321584032 326318929 326318929 479870001 479870001 479870001 7055984 105786373 304484158 680405501 279578270 660692719 370586306 370586306 370586306 259549432 423983795 384289965 989235625 726310042 726310042 156735901 823843370 823843370 627790067 627790067 91863550 223811113 432602320 756042707 682646792 682646792 682646792 979196349 716695221 525356946 525356946 590097887 71039321 250332060 11609922 11609922 758500710 758500710 311257381 311257381 399641816 399641816 399641816 993177032 993177032 993177032 14852096 689805699 689805699 689805699 915784701 930567652 930567652 930567652 930567652 152800002 89665298 89665298 278335780 134871431 890800483 400087961 928371337 928371337 714662616 937430401 843154896 753739926 753739926 908243941 908243941 329266802 324668988 324668988 343181137 876753854 737621951 198020702 486572158 72892898 500067001 637094473 267489884 596445398 596445398 95378798 95378798 26130188 26130188 560046302 632177451 632177451 634477658 31703986 440510514 440510514 337570044 730157469 730157469 141275812 80989324 864896614 864896614 864896614 944259891 960566672 960566672 657237968 61094122 540190653 263729247 749548781 877013179 308453607 844047604 110686322 184560868 778320765 236646531 236646531 256589261 741706583 603407612 101781251 101781251 657921834 831238470 222238381 354379630 426511965 627476387 727888183 727888183 214541596 107384286 556855638 556855638 485884591 578063301 837709310 816786369 814698726 306791049 669499792 669499792 582229764 582229764 582229764 582229764 614846031 789073623 61777420 456058437 625184485 136391053 136391053 136391053 474168305 474168305 899526076 640343981 640343981 672270054 653244390 653244390 675017997 248711359 248711359 248711359 248711359 248711359 687486984 178522736 17654583 176791591 64747351 756420572 756420572 82744242 883603169 700366832 585175496 585175496 585175496 546797075 20336996 438735937 438735937 438735937 174046648 78529692 656897133 656897133 656897133 701271244 701271244 701271244 527229774 73164295 991445413 316719976 95382652 839149053 839149053 839149053 753002841 718817404 287255043 554380361 311905495 594120312 435975243 435975243 435975243 815602703 941433719 76009937 76009937 76009937 454695877 454695877 155078583 790557037 203450267 764906521 182706293 70967185 425697696 38308513 499410138 436824765 436824765 436824765 842123631 514523180 290538590 477592042 151199224 139647193 83244197 806154764 806154764 806154764 188577501 188577501 188577501 188577501 188577501 608682289 262870842 676080215 756533242 905092121 905092121 260786668 260786668 629476708 183872965 985691976 68119808 637465048 637465048 416148731 673192238 673192238 673192238 673192238 673192238 343870967 958446991 958446991 221119487 221119487 221119487 221119487 221119487 485320766 485320766 391030035 100339202 553134477 230885159 230885159 936596925 826979173 83596082 39070282 559986713 402446246 51152506 51152506 51152506 51152506 616757579 944686245 778008091 81332785 590718487 132126514 96192791 410203655 829145688 907149697 907149697 907149697 710881346 927197265 998720881 998720881 983950813 983950813 752944626 939551737 592884817 164283683 463620812 463620812 451370475 925464004 993942685 447474490 353832228 637950011 90420350 154107259 154107259 621387524 621387524 621387524 920599544 920599544 650766828 368842024 368842024 613816120 576740514 51679909 51679909 613701531 98047056 247788585 931373462 260654660 260654660 260654660 752899770 610227166 610227166 116278733 854381806 854381806 854381806 345871371 290429159 290429159 46973052 46973052 339995232 497682120 135230023 135230023 162917252 875174658 311753029 311753029 311753029 311753029 311753029 737715186 659373046 135366252 497398970 497398970 473478493 473478493 473478493 473478493 473478493 259816375 259816375 25383607 47129007 333959197 333959197 333959197 809126032 477969550 477969550 311536607 553501132 276098720 276098720 341377036 435291244 564758451 564758451 847530414 819759437 53312253 35972594 578969909 923745656 456511690 367239276 367239276 139131211 153082733 379657816 532577533 194619054 194619054 806343705 806343705 209438374 218069579 218069579 994482350 600190567 919739682 110817538 402281299 402281299 138506183 340941512 201372017 201372017 201372017 627724055 778623542 220978470 297563015 479562002 759633722 759633722 301508108 723975366 723975366 723975366 943172193 86062037 86062037 903751995 225277335 225277335 393453549 433315417 939841895 739482315 27587074 203403395 327078649 327078649 774754109 338508936 839641426 112783194 112783194 112783194 595397065 881333285 881333285 208127425 748990431 343161776 546803099 546803099 851040514 785490536 227220335 227220335 227220335 965131512 264754919 120480210 514730070 305320036 305320036 532629480 992590602 246494856 969907385 969907385 969907385 558325033 558325033 369456283 369456283 327947768 130508602 130508602 130508602 940278676 725277235 725277235 725277235 725277235 735709049 507876546 285543993 383523759 383523759 383523759 383523759 383523759 367930229 367930229 907775491 822807363 822807363 100930360 715841765 715841765 151112457 711682389 304511898 218458126 218458126 218458126 218458126 282906143 363617969 600913656 793454658 793454658 163552237 137295332 632942717 632942717 534371518 534371518 968735501 394099764 394099764 394099764 368997011 723788292 631634792 253421636 373920305 373920305 152730823 229467096 544665895 544665895 740917231 519474226 342217749 342217749 289237222 8065356 673706604 58451872 542579766 542579766 542579766 542579766 121261097 677454967 459065638 342271940 419656254 863656842 319461860 87462607 87462607 386489614 386489614 459390213 15411913 195873199 839452841 196591882 76273865 76273865 443506738 95935558 533392303 200759962 867754873 11234150 212024599 14158254 14158254 18795359 332885464 332885464 826289419 922227463 20356777 764115651 178891064 178891064 287136760 657238025 657238025 748415712 728970238 728970238 728970238 99106397 675003006 675003006 684314550 687180047 233777146 602074870 305586514 956620575 916188642 916188642 435608237 143989530 690638029 253739199 217825317 217825317 928015532 270816212 270816212 161122236 161122236 161122236 196241266 196241266 870679533 873347130 949634069 949634069 949634069 949634069 949634069 312015703 7501016 784626292 776753167 809893193 349961335 349961335 349961335 951881793 730724847 730724847 668450990 370902937 370902937 491951869 993668871 993668871 335536958 335536958 391083031 391083031 6963048 890881675 278343204 319798647 319798647 916550754 715664596 313194311 572409849 938286921 710752971 710752971 997918344 706470664 706470664 182501493 12341114 12341114 56097587 947308300 313613762 313613762 218078658 756223485 903950345 625518436 625518436 566913247 566913247 566913247 566913247 973440634 973440634 988262191 988262191 988262191 98760109 98760109 92810383 92810383 92810383 420407436 476613633 520187179 520187179 520187179 520187179 875953677 763472403 201716609 705109386 705109386 837126937 280814813 1800919 518255052 518255052 298226188 298226188 298226188 758092073 758092073 532560897 460664246 397445823 397445823 397445823 397445823 640769196 640769196 420349124 460156352 460156352 451349977 329995862 906453795 906453795 906453795 116750526 641778220 641778220 772339117 397791646 449156525 697630344 697630344 691655 691655 330480601 133833435 450823961 315884831 255446175 255446175 297295851 296511844 442387765 424999875 475831774 550691799 426709418 426709418 614095957 614095957 492616723 55892559 752244912 40060068 40060068 130312155 463286742 602105823 720951841 720951841 386608729 386608729 873224244 381728245 381728245 303651043 943397486 681098240 681098240 681098240 926386613 200005075 528478910 528478910 669033526 531952605 531952605 692932396 716437260 788104087 538714586 538714586 462614649 462614649 368657717 368657717 368657717 368657717 357474813 27804284 802850367 873417647 873417647 691278416 616605128 654613917 903391787 364628727 364628727 44359191 363274528 363274528 909239451 909239451 504496069 820020280 820020280 820020280 820020280 820020280 292755647 91325863 91325863 178970050 46760817 829607444 809873055 624327864 357829989 804619323 740864074 237314235 574202937 482350941 37537671 837469146 837469146 823529175 301094251 534930700 712873183 712873183 723938770 85465995 623448 909041061 351095699 102523061 102523061 102523061 102523061 102523061 942667191 452028550 452028550 224161406 353760585 724765668 724765668 181807831 563751508 563751508 46581581 16223759 723629645 723629645 998712814 244153311 244153311 582584227 793554113 156899573 497745849 497745849 497745849 574425660 299422081 299422081 249532847 249532847 242479651 242479651 201095323 201095323 61096952 530338896 962812209 962812209 458639988 278404396 45942203 45942203 356707084 823099134 986588908 986588908 514479705 514479705 600322315 600322315 316360821 316360821 899158462 723932072 495197392 92645971 976683250 212362661 190655110 190655110 331276536 331276536 331276536 331276536 487612912 487612912 510346650 687240369 687240369 214486983 637353585 238145839 787004711 356747875 597141882 268287499 125054742 125054742 864568612 273748702 19870127 256587896 587469447 278619012 278619012 45084834 88663999 654621503 654621503 283596551 283596551 585305249 274802970 274802970 117720620 595674699 406718366 406718366 357075462 214985396 757086011 135159336 368330821 415074414 415074414 415074414 877937366 725705957 797576107 449915906 815429147 815429147 815429147 92392958 499921328 499921328 499921328 499921328 499921328 839530702 839530702 839530702 25804995 643446253 643446253 956034518 80896553 80896553 733963985 733963985 733963985 829245404 829245404 89245400 865750456 865750456 385475817 307845383 307845383 221493183 47382611 901896066 901896066 613770836 613770836 404783842 760436288 449687866 688494551 845297315 48397959 421540109 492997236 492997236 492286426 492286426 172069886 698450758 253379291 253379291 979224802 468894954 468894954 71762931 71762931 575127931 575127931 572477634 572477634 340746069 248895058 248895058 248895058 642523110 642523110 268072149 60881528 75633720 83653770 479165940 479165940 479165940 479165940 386492629 605237528 133092583 133092583 518404430 582809029 19171306 22245209 22245209 531804346 437289409 151216520 826998526 552326485 215702016 440581642 694789756 383673322 236182994 684921508 786023777 864785975 864785975 232410970 351379882 351379882 351379882 187352479 548428186 991451286 910141989 534090069 534090069 534090069 460856517 460856517 460856517 636268089 636268089 894303913 180259414 53674120 199688653 199688653 192548944 192548944 192548944 764510050 725326674 316776131 104353152 378809565 177042238 603798485 15129275 349809432 349809432 981629987 981629987 966010583 303034915 673690180 118138773 736447555 467638787 467638787 875386486 260648882 935540345 935540345 935540345 595867809 900375341 900375341 900375341 900375341 622864299 622864299 622864299 905291004 905291004 175767222 479050552 555024075 87267765 87267765 852625671 852625671 288529053 224126014 224126014 812393613 264535630 643386229 501976644 337728486 337728486 337728486 718558730 97102983 97102983 594605317 694895160 233465842 52989675 52989675 552913389 552913389 552913389 552913389 563482883 759188249 759188249 92166938 390858451 277565436 475812615 589965843 250749929 275442278 524382368 866783412 866783412 921177604 344358842 344358842 981792162