477-Total-Hamming-Distance.js

/**
 * https://leetcode.com/problems/total-hamming-distance/description/
 * Difficulty:Medium
 *
 * The Hamming distance between two integers is the number of positions at which
 * the corresponding bits are different.
 * Now your job is to find the total Hamming distance between all pairs of the given numbers.
 *
 * Example:
 * Input: 4, 14, 2
 * Output: 6
 * Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
 * showing the four bits relevant in this case). So the answer will be:
 * HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
 *
 * Note:
 * Elements of the given array are in the range of 0 to 10^9
 * Length of the array will not exceed 10^4.
 *
 */

/**
 * @param {number[]} nums
 * @return {number}
 */
var totalHammingDistance = function (nums) {

    var ret = 0;
    var maxLen = 0;
    var bArrs = nums.map(n => {

        var arr = [];
        while (n) {
            arr.push(n % 2);
            n = Math.floor(n / 2);
        }
        if (arr.length > maxLen) maxLen = arr.length;

        return arr;

    });

    while (maxLen) {
        var index = maxLen - 1;

        var ones = 0;
        var zeros = 0;
        for (var i = 0; i < bArrs.length; i++) {

            if (bArrs[i][index]) {
                ones++;
            } else {
                zeros++;
            }
        }
        ret += ones * zeros;
        maxLen--;
    }

    return ret;

};

console.log(6 == totalHammingDistance([4, 14, 2]));
console.log(748425216 == totalHammingDistance([346450570, 966562973, 457581303, 222998192, 364627507, 169160189, 954431542, 221061882, 240341464, 2245441, 231904888, 735611889, 365662644, 741343641, 855432971, 6410579, 954376059, 436042748, 1757003, 612662010, 619293283, 756454019, 412485671, 362438559, 34216799, 142080553, 739017385, 767259094, 477271201, 645653662, 266228943, 301408300, 648353405, 543652957, 779813961, 33523464, 581122512, 963411206, 25440862, 235321881, 537459840, 564290176, 530181458, 643091781, 951346494, 264772743, 242353595, 253371384, 100262534, 923703199, 520381430, 497283426, 629165236, 170643624, 116719823, 850474028, 58812742, 416255752, 301680516, 135541845, 719123095, 56870927, 992425752, 194127615, 675165512, 203169436, 169712122, 493351238, 319895999, 340486752, 309900187, 844598934, 307377068, 388210841, 397263679, 76973008, 693168540, 777845383, 514392792, 423470900, 514610142, 136010125, 792549045, 323715552, 111204613, 498136379, 79844425, 353928756, 743878480, 863304173, 946695057, 190460954, 119598426, 632009346, 519938738, 292388501, 523930549, 810762921, 501651610, 30789726, 732344533, 285785174, 63479657, 750706287, 447118062, 460965759, 123491715, 56051003, 96864966, 216879136, 807889793, 812134617, 933426165, 725513820, 298625074, 322335679, 541999219, 548221737, 257888129, 496763035, 472888287, 143945709, 667418150, 989758769, 467300921, 578882168, 171676666, 92166119, 138726055, 549049390, 928845149, 41789200, 916910409, 170593191, 269092392, 35271762, 107017362, 196990595, 194125069, 632374890, 428207227, 661163092, 87697666, 553869198, 330979619, 791810803, 8005562, 405494420, 972083587, 546238911, 144786252, 323565313, 733621387, 271033882, 246618065, 59358323, 995901031, 414061877, 83929037, 284525936, 374303061, 931944164, 587326777, 11794358, 659279382, 640438401, 453145421, 831057063, 135396331, 66447875, 97938685, 83005193, 144370426, 363185828, 708665000, 381327316, 669975942, 821874551, 423739731, 530864043, 230395994, 352455617, 961656493, 598750529, 91771061, 502963681, 814951975, 247143259, 503380715, 381591472, 814678540, 739467086, 735449213, 926534406, 652815823, 174563216, 214288088, 2797575, 567181369, 84843397, 619788927, 142303070, 538398379, 158445973, 121745931, 779430373, 29010889, 900202132, 674939409, 698023609, 127116549, 287567434, 100636066, 759204582, 751062847, 997371041, 705221252, 484313149, 681051691, 140910705, 404734872, 298283655, 819536065, 775511175, 938064582, 373977047, 540572738, 550180756, 616360688, 860453735, 284023825, 525258072, 854626934, 137227180, 565734538, 35769828, 35561683, 123225824, 882188260, 710986932, 958354216, 931955812, 783094713, 338547506, 283752439, 259040864, 750448779, 621169822, 83190287, 960277990, 52570725, 733374736, 66032750, 710867398, 889808503, 728370791, 71096437, 709887505, 453132381, 818915205, 285156812, 594522827, 696722476, 733810688, 950627073, 58365878, 141242023, 678229204, 948011930, 55330417, 870877946, 744584117, 631021928, 104273588, 765494720, 888208441, 960437590, 587484278, 511430018, 374757232, 768240151, 140532093, 483853929, 759897161, 299314796, 970053676, 789263086, 138198883, 278804174, 845413242, 108549742, 974876069, 234843651, 89782818, 884775441, 244065059, 100659421, 358753489, 583292494, 927076681, 383918582, 124227017, 529369835, 94067324, 441550276, 579488347, 415287462, 207499662, 726355084, 552847240, 334800689, 588024883, 214465087, 37157543, 382062502, 348366584, 956755566, 980732673, 30022964, 523256059, 212027726, 667599087, 528778212, 888077798, 912204336, 532519219, 486156684, 453089731, 102096655, 99046632, 376917599, 924811390, 611373322, 789655606, 85810160, 42810561, 696034138, 695310735, 274494749, 638372687, 301449997, 556176306, 806343198, 233811147, 916357266, 256831956, 132554022, 894905815, 854052764, 77086578, 454455883, 233671780, 721499744, 199021377, 320244860, 554321216, 485595204, 753713606, 451520967, 653167518, 643050140, 605991276, 173416589, 477302344, 169074063, 299890438, 907450535, 92280751, 479388923, 878468964, 270783401, 331751192, 667714910, 327931726, 105480680, 932758563, 35523819, 841350645, 547958667, 924416511, 417092910, 693914562, 785840324, 386874996, 420553234, 869521561, 422657892, 882770215, 547464960, 423638972, 984891177, 55039341, 273730908, 685398882, 396727266, 5919374, 141144565, 394757667, 908102264, 101450397, 767785239, 84760697, 229850027, 913806483, 335495015, 520143730, 442721751, 941115849, 909992566, 659501406, 77028475, 477918762, 791793154, 858862466, 309369506, 515377955, 155741334, 555013423, 589121440, 109924341, 662462767, 456498921, 211273094, 76422367, 28479841, 564812984, 934102348, 352703266, 621904520, 339336269, 301085229, 867971471, 140099026, 2252870, 2259022, 460160755, 626175016, 99118543, 585525776, 954625256, 329329433, 767400690, 709591526, 128085691, 750572921, 353119347, 25043299, 143415128, 339877871, 20876877, 837837278, 480857967, 798887708, 837947312, 182715758, 2129496, 430700920, 415966981, 97778682, 334296997, 505386605, 527824928, 691597717, 501332055, 102479782, 681768336, 300661338, 186086375, 817514593, 367391045, 725808190, 951134370, 994571969, 551353313, 203194786, 595769572, 530434290, 597471911, 869853383, 704622952, 18619637, 555110244, 861886918, 749210389, 75364140, 215706406, 218148084, 453240937, 288910828, 56738907, 921049259, 12768437, 643734537, 223749773, 318568914, 511005627, 684468636, 941951920, 929452334, 509329260, 427055878, 637793272, 300640327, 625933076, 682305326, 735917680, 210124687, 895477319, 514880835, 36075013, 722355037, 896050368, 763202212, 12732131, 33539595, 59257651, 303906727, 44248123, 441839977, 799020691, 925508946, 804800201, 424969401, 723091263, 384898868, 774529712, 622485117, 360011813, 257107492, 261498858, 52743222, 130543099, 102556237, 380790365, 235375073, 76952715, 352104089, 141471269, 443220854, 739605382, 705285016, 408511050, 339997891, 38053017, 192887069, 93123938, 204404459, 244885791, 216821685, 635289414, 20488214, 748029178, 757125108, 161081681, 115912278, 369988517, 431847154, 353368996, 280431817, 283921732, 163886090, 359479176, 687990599, 799020523, 715663948, 901045767, 969010972, 444406134, 185769872, 940499613, 142848702, 118900815, 644679504, 73424613, 37352244, 713939984, 198175299, 778092374, 370603235, 818972923, 48201816, 112543749, 175653592, 212884697, 245346577, 371317399, 144046811, 780682308, 949951033, 79074764, 864664702, 190785843, 137556908, 19527162, 213970899, 114252993, 985630089, 589031443, 99333478, 341444536, 582011768, 83772691, 365828852, 32812781, 374091566, 672314993, 332115415, 553781352, 209056966, 337181070, 940382704, 325442786, 76055393, 510220186, 368463631, 572891916, 70737642, 329092303, 76924074, 663713380, 793693720, 234915454, 149092192, 472033473, 661988693, 78671791, 972821941, 425357776, 808058947, 360138601, 240549761, 1104404, 381848852, 845496906, 160185521, 86536687, 575669390, 861607995, 563340244, 951564932, 434071493, 230612570, 490459733, 114495345, 970894281, 239430861, 523104927, 26457271, 138238768, 949151369, 671507445, 792041708, 386837181, 139501598, 344193640, 689046109, 211624270, 536186458, 844416794, 541117382, 759572807, 497369481, 75491621, 210795926, 292089310, 144899775, 670019883, 412907291, 213176380, 645674042, 401734181, 50772477, 574991658, 1363084, 80011249, 424298921, 546257207, 245265702, 952513499, 196767886, 100527269, 78137050, 929869611, 873031436, 76563479, 459687000, 460730741, 468511483, 597444879, 415526559, 138057069, 42819923, 60402694, 221291605, 953812278, 550510069, 63178407, 775543409, 125316351, 657937197, 350150154, 661424076, 972067038, 268099868, 533790070, 370512971, 301905875, 775666911, 53530818, 44293680, 853011407, 109373724, 584134592, 47832238, 757540088, 693199600, 299870803, 577445090, 641026837, 960076107, 599985369, 518374118, 765623925, 119294651, 382956706, 137846261, 440232092, 899606329, 398696623, 538142699, 156199507, 20097515, 416980604, 746849845, 56406778, 781408097, 56363452, 846206593, 202993048, 500126300, 164708320, 939291835, 525581748, 852198525, 332167832, 80248802, 121884898, 967565095, 913355159, 340027135, 175051856, 836925980, 197058010, 534190396, 656341112, 294553323, 607893326, 283421303, 136089053, 971608294, 354945470, 6426571, 75669956, 474631468, 376817718, 39090001, 648629403, 887384049, 137266775, 83724056, 548420407, 301967525, 664334814, 707738145, 43082282, 381924535, 177038862, 227302539, 693343538, 778574544, 884499837, 906955925, 369305069, 682554853, 989255744, 395872912, 324672156, 801957443, 891375929, 509317231, 224884475, 62152605, 921779793, 405951493, 271196332, 36452990, 425542113, 758727259, 964124705, 279800320, 407769888, 768190039, 298299709, 296377065, 987732640, 566867748, 901761122, 900059153, 212353581, 701793131, 56963393, 399018167, 854386835, 249366934, 369464441, 6614988, 94910828, 378915053, 136282416, 73976588, 517440059, 99279841, 1493968, 486800059, 528875121, 369343714, 332061368, 438392001, 37967950, 324692491, 350749210, 199361455, 593484865, 786069387, 941769543, 366230811, 346086753, 87320173, 297290219, 509747811, 812170172, 530999050, 351974996, 473793934, 978264240, 552280248, 749805802, 552073618, 571942686, 296898208, 9164806, 561555505, 665722548, 409063366, 32838315, 803241504, 997752686, 677077826, 924154707, 666425445, 130729941, 302347506, 608224540, 407684060, 473162490, 103003167, 95386865, 937217971, 822866430, 121402330, 299495660, 69372699, 449288928, 439488622, 81986499, 848544475, 48091598, 821636314, 921679188, 862566905, 647355085, 737736471, 359268897, 655820162, 128881261, 443837451, 10827857, 595166251, 773331409, 809959419, 89116800, 989955641, 628644978, 809580584, 164487896, 736614383, 34710126, 405019345, 429949003, 17904913, 866119367, 17020381, 32175572, 194916716, 845662715, 799453737, 406757058, 925425405, 548210261, 857989575, 671075998, 190184342, 972569258, 473481889, 28691219, 176980805, 44517118, 667871648, 814743645, 40708243, 76618933, 830175887, 564878250, 31028010, 235195005, 198033486, 896629999, 560620772, 135534193, 28989440, 539708789, 62175442, 744074761, 867231646, 590762133, 122269250, 630413149, 816964592, 506437404, 215755967, 51119811, 763161833, 334082278, 398593088, 945513601, 661082785, 885461564, 683811016, 626750815, 186637748, 140000947, 501322764, 946325945, 429246511, 741518682, 649863411, 945498613, 763684538, 529250625, 237988501, 258185593, 53789542, 97700654, 815858979, 458773958, 147619376, 488218725, 750074466, 772542172, 430155042, 185835092, 682147084, 223828033, 633884734, 827330149, 128683565, 854601582, 711136116, 111184635, 955344711, 536307736, 735252493, 767745013, 408682315, 863943677, 957420550, 65195457, 316364407, 760057055, 46191029, 884006414, 996908730, 170589794, 4977591, 699488282, 974071896, 958514991, 486617590, 757085932, 295629227, 156237609, 660477829, 100879238, 905734161, 102932569, 701824857, 590182275, 759509010, 425133302, 537313145, 453292380, 360534751, 101686801, 800565042, 904591017, 69980537, 489330450, 107483718, 445101299, 131989792, 794805371, 945586057, 85872199, 938016387, 563963682, 692269163, 694401673, 382780313, 320692757, 846696576, 995686388, 101524270, 654863681, 440195692, 287831529, 451334859, 465712587, 446534972, 605411786, 171346394, 836251909, 752848595, 945666619, 292394086, 824819066, 727100877, 202488309, 252407446, 931742097, 338670355, 200991935, 872653392, 519733981, 146004896, 916435707, 782211265, 877327568, 414693652, 964753227, 898929917, 560636952, 259987806, 633317444, 30305354, 974417495, 117525021, 351051285, 981368686, 189096642, 664443112, 380418984, 643046969, 552696279, 92566456, 424739073, 353957283, 430353191, 221158041, 856485777, 166546776, 773450769, 461537870, 149026704, 518860304, 347017439, 903995668, 801368129, 724193766, 380292544, 665453536, 182745976, 510003422, 20278377, 161760944, 1888706, 678710684, 450311702, 656403486, 549894563, 455787300, 135960829, 964031173, 855291643, 424089461, 173346634, 449052306, 757549962, 504646849, 186669140, 667606291, 4360909, 865310721, 311008941, 945053167, 719524557, 568813242, 594445497, 544520813, 126462802, 37459840, 167800887, 376457876, 433676448, 33542196, 895951236, 890069266, 23068660, 167912160, 99139540, 583917286, 45042659, 556199578, 49992055, 550362408, 728923627, 772676501, 333317476, 74962687, 472463267, 88580441, 565304516, 605346084, 421597949, 41155968, 804576998, 614058805, 827411800, 146486853, 426752418, 979991993, 318832439, 645103008, 748805400, 711164958, 448448482, 553519651, 898594131, 566554013, 923784271, 882958534, 565058746, 562635566, 638438599, 54727912, 689016068, 61230252, 245157029, 126046388, 42767174, 173850251, 323408637, 40830080, 976849745, 194161478, 37279531, 77809749, 723888998, 907529131, 413243723, 218116641, 924778436, 412020513, 134462641, 199284152, 441736991, 215618636, 890481341, 299340822, 259989011, 653569879, 963080526, 910153043, 416176120, 317810561, 650268638, 520719283, 733127856, 566192953, 297899792, 810401565, 870792259, 97421286, 769993366, 335024118, 841207370, 287419389, 759927398, 807508055, 484209923, 300637378, 576369233, 886451061, 134417919, 9167989, 615052186, 136275669, 606074690, 782377109, 369700382, 884129503, 125203328, 551338214, 96909540, 404507863, 777910686, 257435244, 327575781, 565564006, 464605798, 172085072, 366311173, 903752309, 6200710, 929096492, 764122285, 444013513, 822418244, 178674816, 598472584, 508295318, 229461860, 832334655, 133048605, 410406286, 773953216, 523251433, 341299966, 299707425, 333539760, 663406228, 926357350, 31540700, 823567738, 963846229, 687400060, 463766138, 299326403, 17648878, 271949260, 806012004, 316905952, 478890704, 94836819, 75508015, 486329884, 216578484, 842777501, 906807342, 812532813, 390476818, 33854894, 63520650, 878149147, 190586376, 287103755, 750034054, 93337688, 63459906, 64246161, 748437133, 964152430, 391269326, 468634968, 525373627, 294771103, 120638139, 926596561, 549971261, 597366939, 460094048, 859535536, 884238761, 814018887, 744602419, 938623642, 825658810, 955776403, 349304239, 329032553, 279727246, 534120239, 477212413, 805087393, 602332982, 172516516, 382160962, 3183804, 409059809, 766034394, 368574771, 86316827, 613923173, 695328423, 571776965, 13614077, 616999066, 852254546, 919207710, 126625452, 37677587, 887012491, 980437341, 568366756, 532806236, 15084109, 701506773, 332090359, 925643738, 922765698, 943671299, 909767776, 176423170, 262280261, 507902983, 870917034, 254052486, 662641966, 173329220, 156375208, 471115506, 266102853, 329697317, 507976137, 100416312, 360766398, 847494283, 370362408, 273382250, 60933395, 343827302, 619949215, 43284908, 78449579, 740093573, 527397987, 312956340, 462733455, 915870976, 673690514, 182681814, 224611266, 912779883, 261297991, 31276622, 680176086, 457002999, 93377452, 731773454, 70573587, 512282143, 457015156, 297700151, 957023994, 842729706, 103516777, 137695547, 54665541, 788230318, 753314861, 546769762, 269842999, 558800307, 810771418, 851482111, 28815969, 126170408, 772666245, 160944884, 111732393, 424095182, 269499481, 434765644, 366811614, 370224539, 103701614, 96767359, 162355443, 403698811, 858054182, 756925847, 752564279, 816639970, 492966391, 87201989, 812960447, 928249093, 406789174, 465199017, 404898570, 902072294, 687476016, 947380052, 172775106, 226294376, 929017173, 785512921, 179180069, 707346589, 52135178, 648565826, 611823988, 774064480, 245781834, 244230857, 739742760, 866713415, 263766882, 516716944, 830787918, 113865032, 321663347, 979533530, 410400808, 36389539, 152099734, 627667986, 569145216, 524460152, 121865954, 87646796, 698897108, 775628713, 559020679, 12574906, 686026314, 997537233, 203442902, 470887890, 735528035, 103812113, 806440405, 867569196, 614492620, 528605917, 139799380, 261069842, 491743673, 218838455, 171404452, 19054137, 60795734, 384663944, 121129338, 799264988, 736441331, 421192456, 668486058, 403714280, 325063087, 929883819, 318846714, 678001511, 416142973, 553687510, 779338119, 833002980, 835190067, 86339277, 198261745, 438011718, 881981088, 524014422, 72932785, 361133636, 784233830, 510839171, 827304869, 703802605, 263433137, 202432023, 660913713, 191352107, 64821368, 116996456, 411898987, 91975159, 785755120, 102335015, 396153014, 737379176, 796662773, 98170413, 121163904, 587237172, 7791839, 546892762, 189620352, 876502494, 787081885, 778954253, 823818059, 83045404, 672713056, 934414384, 947619955, 909857533, 891990491, 893821108, 803251391, 163923495, 633639942, 215099721, 966032946, 139352102, 126581662, 887656213, 269076182, 910313939, 765850123, 419015721, 798344334, 295395082, 870434957, 534697513, 235016874, 706174485, 679936073, 718071802, 567658652, 516604190, 83215087, 377091590, 347089411, 759124003, 189750172, 910903587, 145667246, 98045942, 738189945, 745376896, 277378121, 500060588, 414791805, 466927051, 530678597, 408572366, 16030834, 994771163, 958744646, 51461881, 276902804, 308363779, 791993442, 930135588, 255361003, 973029293, 408334124, 306864834, 369028591, 123734979, 642600335, 281548160, 866429357, 784571370, 741423010, 396409176, 747726616, 759911446, 746424213, 699765764, 135723154, 57373320, 639188893, 927500935, 717399550, 361042592, 47035900, 258389204, 535417394, 803660028, 589434613, 78455658, 842263326, 855002705, 10359436, 750822601, 254523813, 787278845, 148798748, 982571106, 716311690, 257248748, 695126225, 675423895, 250845223, 445263900, 717341152, 172525984, 334268216, 21664338, 980771001, 526718013, 622051557, 870124903, 973092298, 319775512, 462945390, 182895227, 663959910, 642156136, 258346508, 965309369, 508590276, 891853672, 96292891, 777906355, 391665549, 685503988, 15760161, 740537346, 543439857, 138704486, 979517785, 938753171, 62190488, 558479374, 504796359, 552000063, 128682379, 41689902, 395492570, 374715103, 60178048, 95138646, 705863463, 747556613, 404659741, 828535516, 912450264, 370863821, 110695953, 539022347, 55541561, 917586438, 795194359, 40856432, 272264162, 803602624, 417624163, 825727723, 759492125, 934325685, 811360931, 22008867, 535840385, 470418824, 87365292, 617131743, 580168169, 310659003, 506096142, 568111405, 536089273, 358512146, 467502918, 826362100, 684048129, 109920290, 32851119, 225459754, 140932170, 765497127, 135684312, 966082317, 614625430, 613259940, 285789627, 138321228, 187572942, 825420976, 105984012, 9346321, 110289394, 148436175, 183773989, 607948737, 67230333, 363808409, 641987054, 918574050, 214120067, 680857344, 22004323, 459469377, 98108274, 224277378, 389070139, 807099636, 416867800, 998436664, 80772768, 131225450, 833411259, 254684279, 336747260, 884767553, 904470021, 183884412, 316344451, 779161632, 807248196, 766232073, 395998430, 493790957, 267802291, 620359303, 345699336, 225475017, 42952342, 345506602, 133678326, 463730320, 697333277, 262124860, 836540601, 955422676, 53686913, 165793629, 211022, 837636616, 403299027, 581335435, 247040773, 928382160, 850267665, 885437095, 272560533, 342259080, 387150894, 762603626, 896736886, 416608356, 139950072, 439245217, 138562311, 944487629, 951945626, 389944610, 471948204, 376356257, 873249562, 595123514, 55050650, 818306340, 582359570, 279808542, 900462111, 542417746, 139954085, 506691708, 987854579, 468812874, 13451053, 379043414, 939140674, 925481046, 335884901, 630506791, 36300617, 805071327, 332311720, 705595840, 337562724, 557885472, 467525102, 51724941, 757689999, 710765061, 524335613, 28738981, 979716739, 135089402, 143321691, 916965859, 102541341, 923411871, 711977606, 428742958, 75259421, 810199242, 972338314, 532468306, 630461893, 488721353, 962313743, 700711622, 852889384, 58533163, 219360215, 705195253, 47347956, 1125680, 177908093, 597061005, 406207182, 273594061, 532895000, 359457010, 315446637, 367482194, 110265786, 106161588, 284856015, 626973520, 634673389, 404374274, 680164010, 254041667, 273785611, 250287134, 802880312, 15144614, 132457152, 59790303, 20759372, 448887899, 348866582, 770287364, 188302632, 204418924, 842504115, 252471065, 986630, 988378390, 889591185, 577895881, 775020233, 69715554, 769201972, 125988464, 69238506, 902917315, 4842081, 362433937, 956534845, 211537051, 10758950, 23003458, 658019302, 582605242, 468355621, 918334470, 275444879, 220316999, 605994765, 586561281, 31004968, 409454602, 958869404, 793764518, 424817440, 316566383, 214205462, 761586040, 767016738, 698961203, 705389731, 375477477, 135979631, 73014965, 387827827, 609419744, 168124865, 379105181, 36796418, 109590637, 934824089, 598102371, 83081437, 71298265, 600021985, 779274161, 905544521, 63136736, 75178912, 604568126, 24338303, 470439100, 782649093, 438946754, 564745611, 594742915, 455279267, 187384786, 958050378, 913296418, 707272217, 595143552, 391829316, 290452310, 194623117, 206111616, 19786079, 477643046, 452801636, 702534931, 432472689, 129317506, 185872578, 519195708, 689185173, 401389271, 903342470, 914992647, 944000540, 207891744, 80647739, 384368116, 444115436, 742459527, 282776150, 237442239, 667094747, 996775489, 78691954, 518722904, 539724355, 969288135, 14738803, 754442616, 173595224, 125115720, 19372783, 766806693, 670723604, 709949325, 699162543, 941827464, 985203989, 224524753, 251734470, 151431278, 130346229, 88729441, 715042447, 192896695, 107424473, 596854231, 225923858, 144172088, 531707778, 526148257, 429075631, 224043591, 961800746, 875727053, 639146880, 221388444, 79396635, 831899658, 619010036, 83867562, 251315611, 908624075, 281593286, 477378392, 299729152, 698705449, 494878125, 5460622, 227855711, 607592176, 516960547, 984561314, 953482841, 456113351, 173449045, 22790336, 578066564, 141700698, 797245341, 151972554, 637637373, 620908059, 771685418, 856054671, 363399175, 206442157, 487242794, 527471325, 191043037, 165249172, 439456811, 547339022, 99977584, 991042334, 565341406, 225356314, 195394668, 495688813, 952813378, 148888367, 548335414, 20973821, 112670017, 357377643, 81768889, 486140499, 181068436, 232876053, 232617937, 982408197, 125783774, 923980970, 893911333, 172179319, 157341924, 686325789, 735846264, 802814553, 264438170, 268657547, 109745013, 381937874, 194206013, 638295629, 153819838, 472684856, 872364539, 959948904, 964073264, 208210011, 927772492, 986490755, 376364445, 10865278, 662574507, 980008032, 588399912, 75126549, 79008254, 185304641, 563813137, 309542995, 76702509, 87354072, 428557203, 893737361, 543199209, 389100844, 323158571, 132938112, 700834082, 763590957, 310939827, 137959238, 191552884, 351334535, 446984142, 357655966, 110071187, 775998420, 330235287, 959703339, 777324534, 350418237, 872127763, 68400544, 142665372, 185157152, 25427739, 807742198, 478989099, 246572868, 654237413, 444906229, 793910527, 938328478, 514309825, 176528178, 27149717, 477233964, 19811403, 110284936, 280531991, 174567572, 287499380, 956852488, 462217080, 827090939, 48743320, 830688311, 380232408, 447726362, 154267046, 753480193, 30537392, 140839358, 146068068, 978167511, 867018170, 90816873, 84268650, 904455755, 91599397, 351247636, 779451227, 586525489, 783953893, 100905306, 196375390, 946297938, 958532862, 786975487, 138206714, 55914722, 308378915, 839362772, 143010439, 335225858, 84367903, 70612210, 368440326, 974183359, 477368563, 927511727, 105802116, 99703896, 686135412, 38168741, 990376690, 115280933, 496391337, 22716011, 121864867, 276399009, 431015802, 620242883, 536512043, 21556595, 962912978, 241657454, 645252901, 120573404, 838595416, 337981451, 360000642, 69356495, 383969722, 190758419, 31146809, 84366151, 395671415, 85595724, 940773425, 449839692, 313266004, 224805362, 879984061, 172236338, 115660257, 15196020, 434911303, 312913711, 100772921, 911842920, 900651448, 784142480, 768498299, 184258235, 949715249, 765725439, 470935380, 533692465, 523044314, 155218227, 353088662, 863825573, 326951691, 459396542, 873970429, 32854723, 286032182, 274480888, 198389438, 82159253, 18580150, 891452235, 791792173, 487869730, 533987864, 399869435, 129262582, 55743488, 577932724, 246756887, 452077452, 268592678, 226513152, 665523180, 146231262, 426001775, 101353327, 490834818, 976097999, 651489760, 716763914, 60821506, 24835370, 796236072, 369057647, 612079171, 560936445, 998599363, 874792636, 966785890, 909180028, 242582191, 947900709, 126501295, 684411691, 777855883, 336361223, 46116057, 623952010, 598783769, 650435741, 181735757, 504100443, 386136664, 896309192, 818289886, 305817192, 734157251, 332860473, 191069276, 813269467, 34002361, 832988381, 382803252, 706228530, 440786741, 631657484, 48645045, 971958964, 953688866, 623808232, 329790570, 134817083, 275466396, 936458287, 939759324, 940218430, 859456962, 711129190, 994779353, 889372554, 991310536, 571023704, 883953263, 310621295, 79359208, 202864069, 479859894, 997122551, 469312047, 20138498, 312803307, 38191471, 579421222, 641622656, 29566383, 291950133, 953235583, 595415439, 666466831, 33325865, 762064835, 224189715, 63201745, 813280106, 65328387, 610056692, 135891666, 949092279, 678381815, 572482782, 991378514, 920551372, 27694794, 48408515, 498587970, 286821196, 650537304, 534200029, 463737874, 824293355, 481410688, 498534967, 188978353, 30864958, 203790179, 658100066, 147027212, 125652965, 872957754, 192695174, 222449742, 91268014, 76660849, 96184590, 105175095, 91758762, 89232966, 587852534, 258257669, 472192296, 183843207, 416790594, 55340491, 833170242, 144373785, 981167032, 740360089, 711765105, 152205945, 265272616, 53784518, 658757217, 454345834, 531561884, 428612868, 36320438, 345224296, 476907256, 971280988, 296364469, 776031668, 889034423, 603310113, 562771704, 779026318, 680509445, 971821840, 442024376, 957752459, 555644148, 97793211, 785507322, 439582745, 516428113, 271372595, 851421584, 952000905, 171535116, 67640338, 605290081, 273334106, 251777187, 869375897, 914945269, 502223563, 53669209, 661221079, 707780106, 748320809, 363600031, 80240233, 125349362, 651226583, 234010300, 968554443, 568479241, 275857984, 75426862, 122391413, 890628112, 618637372, 115471008, 543498215, 119527392, 438140908, 112815193, 4372097, 53347437, 548166369, 327318153, 530577504, 856985962, 983221483, 116801116, 276303254, 969145164, 906792500, 563083319, 928393751, 690572533, 450933743, 166606916, 636740102, 779881313, 372529950, 989017223, 682017759, 197746405, 366626926, 561140617, 135150873, 590507632, 932816815, 14565183, 569852079, 519804711, 394301781, 42982272, 287013621, 589656985, 875399637, 224212040, 290934373, 61226439, 974050516, 392159909, 197256498, 368189496, 260472265, 978663847, 619002734, 961142848, 348832180, 985071528, 145736373, 52842009, 643372561, 582470082, 344205148, 527955996, 101479015, 41746543, 992952788, 462087079, 996669201, 646814607, 450878735, 596592529, 122465638, 783622618, 621112253, 115628104, 36327040, 101679041, 670142722, 329978717, 149520065, 220844043, 667067263, 180346832, 989779507, 815844487, 215206914, 620142050, 989295459, 270384339, 67167099, 94013149, 678514698, 451342294, 590672632, 411004521, 445575695, 308207354, 103420692, 670278599, 466179809, 63705607, 46259221, 675604289, 928222112, 100803154, 419968951, 432390346, 99883774, 561861311, 510436696, 505358485, 262233510, 722158926, 894980085, 747803585, 53529429, 459422266, 99292275, 796429362, 115693961, 788680570, 878249284, 873588935, 856514584, 857727447, 914963065, 446815866, 31429950, 548149644, 839199656, 903508543, 204192842, 983206166, 6851944, 782463026, 813707401, 597403089, 860645676, 215008918, 587390572, 83996923, 632507360, 300125448, 562296311, 586052177, 64428628, 520192708, 472916419, 469276586, 571629118, 321728126, 68274183, 166399692, 655915050, 930685299, 904419192, 477085056, 457576872, 355547797, 392318225, 710589863, 520245052, 145640605, 236247811, 712674752, 408257545, 167285228, 299711651, 50061073, 710347934, 749111643, 415740118, 579859535, 211393237, 741160699, 75694071, 318405782, 64213397, 636246094, 67023445, 974587665, 830088564, 37702814, 749476189, 100213799, 666140545, 991888004, 893615214, 283253158, 812064754, 906722371, 531908863, 610816558, 22057646, 1163969, 235474160, 949329346, 367799590, 149773064, 178030942, 514300501, 19819710, 42879263, 57730074, 192702430, 137379912, 192239037, 939068349, 857398418, 472918534, 297801969, 166290404, 966595281, 581859, 627843134, 572395427, 316181607, 189726171, 507518780, 63089576, 637065861, 605440463, 860342155, 763203834, 247014507, 486929498, 911377816, 319078039, 477934914, 63259818, 996334439, 462920614, 766484995, 706396259, 905302975, 298440408, 159116442, 652900179, 799355930, 910398456, 245865117, 496484591, 442552342, 34321011, 746087990, 343833097, 71850849, 149883038, 85901735, 641449361, 471502387, 325960879, 193709856, 96340940, 146992389, 333361382, 19912251, 805237272, 973865688, 787744429, 176913026, 52839112, 594682682, 442943236, 368646950, 151945633, 185176126, 344323757, 373933812, 168427162, 164843566, 64887710, 439027872, 135117259, 464030643, 449894644, 882339199, 100335058, 349635489, 601384009, 48491412, 98859271, 168403497, 121610980, 97266072, 308795315, 247862984, 862380555, 455832860, 901687749, 666879142, 520585901, 638860229, 53117450, 977742154, 367515434, 668930466, 637450017, 974004483, 618483278, 27601866, 841072688, 171302662, 101248185, 871196871, 662305651, 963333956, 874583759, 751157445, 439795980, 12322886, 952314890, 360735139, 529145692, 621863217, 999661817, 197082769, 950314909, 106792824, 363642654, 3626416, 819631596, 588122114, 494121435, 379695096, 361563235, 207548213, 749373163, 870644533, 762074051, 586104449, 149985554, 808888147, 57096050, 835605788, 276406114, 550429537, 857160730, 773063612, 397041112, 631256733, 755673929, 186414923, 689948466, 699657909, 323004169, 39892414, 42861390, 402833494, 554078314, 698108584, 53302658, 357092207, 579413331, 154493550, 265365627, 824041817, 341757394, 190743811, 785630153, 2014646, 647900617, 169074560, 515264939, 403765069, 824168741, 534506837, 532314058, 185499404, 689711231, 652911489, 989443100, 249797910, 22943485, 211579582, 578093820, 806813712, 906310426, 257821611, 733300078, 958739391, 963141096, 928153033, 939792401, 348659922, 591920038, 48804340, 501746382, 476139083, 945499259, 774541860, 472151484, 497915923, 876629149, 413783754, 911504492, 655142993, 632603760, 772836601, 83655951, 196758250, 938575017, 8418435, 902199990, 686179041, 623957697, 694365178, 769408848, 455469749, 93848466, 58171164, 370672541, 836315218, 669399311, 74876991, 618127751, 140205449, 643420584, 389592643, 998889776, 460796633, 575958327, 68299791, 158319839, 942274018, 255007548, 327478402, 76398800, 425367850, 977372665, 599964752, 171864199, 949065956, 590476223, 404925752, 4415099, 983103473, 73869271, 68268309, 422180443, 93714391, 745234864, 830708522, 719918685, 543450175, 312119112, 276344341, 659694373, 818236128, 756811555, 979142282, 277146613, 111094348, 999417593, 741882364, 319815844, 786300245, 881337724, 93908840, 72876982, 216231193, 655330027, 835621973, 548427409, 419650139, 723589425, 167573014, 48585081, 318649085, 503934555, 100045764, 575417103, 709366258, 282468640, 511572610, 269312260, 583109591, 509607, 122513908, 240391439, 635153844, 682425449, 961846363, 287906903, 570662030, 454770708, 436989683, 91529441, 737023635, 470557549, 625937789, 407011648, 909352241, 989482435, 910901255, 106473322, 643244903, 584405723, 664268730, 390042935, 331517901, 41760367, 225292756, 274659009, 44585438, 461620819, 395666900, 364217188, 862863344, 980132995, 895674475, 533514433, 32849206, 986286541, 91623394, 168608059, 264717220, 309178534, 600678845, 81701946, 715534567, 874022947, 915524749, 504125688, 17450801, 30814993, 949985580, 659706193, 223916290, 969736486, 107723119, 966725190, 36478775, 504405539, 425939264, 991193175, 746021024, 11314113, 177736255, 856463386, 144726308, 902043661, 560746254, 97026520, 223107076, 254178670, 635932807, 96576130, 804863425, 133070100, 771672751, 643160402, 104659641, 811436550, 85915978, 319304971, 144497391, 349602936, 54265738, 156687169, 626298161, 375837980, 752502611, 573164472, 356619040, 69346503, 570539247, 331619052, 594321577, 609281020, 777052822, 871700525, 330262419, 268227216, 526644259, 529951726, 76953351, 8288272, 862034096, 75347388, 934155542, 99251177, 667221767, 629611913, 235493022, 911837911, 816465185, 57343612, 139886537, 371412472, 741938722, 119541103, 230108176, 603044363, 391278748, 419969100, 434894589, 386506582, 671070077, 90670095, 326380942, 604236334, 742877453, 71428913, 62382118, 484237490, 763955947, 795854394, 396646442, 440488984, 715201457, 717894118, 876290958, 172258558, 134606728, 827975783, 887930899, 590756490, 27427349, 55449116, 72873461, 157053746, 344906859, 791215960, 747897496, 691429381, 819592550, 931875992, 441559973, 742465826, 388643443, 432575974, 865228501, 76621048, 865722692, 999576019, 109580852, 331894085, 921833914, 108541718, 485511632, 703624071, 410295846, 272293205, 144244678, 958749330, 923164447, 848489732, 275509644, 308822354, 702307457, 111305887, 52764850, 701066317, 726302377, 459979269, 723423461, 673183360, 41857702, 713718454, 769887883, 709654984, 840119228, 178885971, 59408797, 51238971, 618400306, 426070040, 248683182, 408041390, 829335437, 117315560, 332628974, 595232877, 100136013, 151769821, 732292558, 205219927, 65554585, 909777762, 551279294, 106641100, 108584680, 207573966, 975182412, 88583158, 403947713, 746382802, 796749665, 56575541, 677345613, 129883522, 901947480, 737210765, 468167812, 909312254, 317420926, 337102712, 416398376, 551278437, 92237501, 545464751, 18381014, 839540777, 987256827, 12329598, 65123474, 106546126, 866861731, 609030247, 857278305, 601662990, 442357785, 118906581, 303115157, 418211593, 961245498, 133608505, 437732420, 482786896, 6142706, 954223264, 222522252, 162459937, 805424400, 971442337, 506168396, 989505805, 510702267, 28348057, 290381521, 4872394, 285947372, 996562865, 800087680, 324018824, 913329823, 914204983, 945138643, 801614620, 572000709, 124607122, 475343629, 461205763, 216776718, 27012692, 321738436, 94070706, 498391550, 280557550, 249632616, 539814521, 337224450, 521986717, 560054624, 417240767, 31463514, 319281214, 390708423, 778956482, 654259440, 815114018, 616094891, 333665781, 840978950, 743331743, 57208580, 17887360, 778127518, 961268443, 312223698, 34121243, 683554508, 256083084, 431164200, 966884422, 417723705, 558267892, 452407101, 514036127, 871453186, 675224562, 195622786, 827679323, 554800042, 943289198, 137268632, 469439724, 811500768, 224765679, 213031880, 571567611, 642485046, 698391006, 859506987, 404415718, 229229671, 77417779, 933005218, 886087110, 814449472, 184488504, 524879038, 926653437, 505886193, 334465856, 48432524, 109128655, 174270047, 936469068, 120955591, 26582806, 100621866, 82071673, 487085315, 28205419, 247569724, 228527029, 945994145, 147651205, 230190150, 980781381, 701174673, 399958022, 263639222, 518618971, 585901002, 25619119, 876782211, 838813141, 849801879, 499422734, 431797862, 672401999, 794425257, 792439578, 631387330, 10155483, 824973246, 963899068, 427981486, 162101399, 74443528, 336892542, 31554833, 61101069, 14440573, 623015456, 683484798, 438972183, 199152236, 17603357, 654361460, 382280511, 510455131, 22216952, 885641333, 557704952, 373987687, 73904287, 302277152, 573268509, 105168899, 780601168, 379209631, 437782499, 531486071, 301907424, 447195885, 975958342, 244736786, 652956875, 397740533, 501523598, 233797111, 680454214, 836533001, 827689476, 725441513, 23823550, 408920017, 771055319, 210420435, 423663014, 595986493, 674236821, 420023906, 563040453, 207944889, 766834332, 928230855, 100263108, 494876908, 985006503, 52861198, 527408575, 136403787, 173396760, 937014919, 912160182, 937906588, 659034114, 458681350, 738640367, 518663440, 540312907, 478168433, 486024935, 386267935, 162118664, 719121452, 29257026, 742059397, 354747250, 615405256, 627872218, 706705146, 8820912, 662653497, 160109315, 953226092, 642921624, 593506511, 795368640, 822513552, 426011303, 54469001, 425444763, 122565809, 526734390, 897299796, 287502138, 3206194, 992389961, 740071925, 956538629, 482156161, 142797796, 56302251, 817601386, 826120996, 926780495, 493866352, 180460987, 553877523, 470897894, 903665263, 897723657, 968883024, 441467745, 192389830, 532984075, 502035466, 39806577, 954704000, 505296194, 362792320, 537426985, 12096191, 82714250, 756480141, 58539547, 119634681, 448368553, 3131526, 884928532, 315076780, 948251605, 581559426, 864173863, 531189358, 402997905, 815345275, 414885418, 99818517, 465086912, 22738551, 500694647, 126981761, 169669165, 564351517, 768161067, 604345883, 791088918, 553164827, 377518104, 73059268, 132428348, 723165122, 271742012, 617762162, 438202067, 140714506, 402185573, 47383233, 801047641, 425697822, 80761128, 142613392, 311529292, 307679258, 24667230, 117790739, 876511486, 583705360, 630686024, 108207423, 309466508, 791185500, 235956276, 462318370, 381988322, 42085549, 248175689, 675562549, 433719354, 961684760, 73833998, 475434998, 996844546, 91849306, 818027396, 189115056, 973927210, 674261036, 34026833, 658332129, 752342759, 241036977, 954314197, 750833183, 432375487, 643127139, 752629822, 770737524, 164207164, 313318953, 321740627, 130894843, 926371773, 273948061, 40122059, 21580455, 925454489, 682519980, 403145233, 144003324, 842774877, 862705774, 479337652, 16757267, 112007290, 103826836, 699384797, 382283148, 554775190, 880106703, 878975363, 398918228, 174712062, 775480585, 423938452, 930305665, 611856426, 319249946, 12670794, 943110861, 80420898, 659797301, 400663377, 588143894, 860177895, 149969661, 541774496, 66269570, 41628775, 722636150, 118727843, 32506394, 312591129, 974104541, 507179506, 596340977, 189598468, 508698106, 556668835, 494343513, 610171326, 915061657, 310873032, 808314251, 356065635, 505686903, 132482473, 839865419, 1063980, 495421262, 544029593, 312979203, 54013318, 209231523, 123476922, 600403630, 751130735, 345386079, 48510490, 64998148, 502180760, 334279188, 206070742, 332816761, 603885339, 286155429, 991388148, 727964941, 692426428, 397092303, 698645292, 483819426, 180005240, 336588635, 573262247, 206944887, 139669894, 818239443, 458021691, 389169789, 334433539, 859785774, 2042955, 123689980, 679280720, 440972166, 246106743, 55504057, 641761779, 72839350, 145276660, 123401628, 127915950, 45219581, 589265407, 736599132, 571365147, 534639892, 414064374, 125896116, 103102826, 977377100, 467482375, 126590830, 603269280, 669470051, 909299102, 889353840, 676784338, 286469185, 29255721, 74631331, 784287425, 57105267, 636010838, 408043147, 858865336, 357605596, 618007666, 269420501, 254832431, 679254277, 996544665, 701221702, 42890778, 458284101, 150022296, 278927294, 121712504, 656096293, 829352753, 408345572, 853776439, 727859597, 69393467, 5358126, 652689086, 398999526, 541087548, 258152769, 856621643, 509584413, 420445055, 198840755, 224993131, 533828928, 23599377, 936211700, 297360331, 540636548, 475151779, 531750107, 90088113, 134944056, 262017960, 394377370, 958901526, 186155325, 976357243, 506614952, 697816487, 793500742, 493522924, 57938954, 762886365, 146742543, 429166954, 758909252, 875397409, 186766044, 148788172, 11841696, 100384079, 380552858, 538562218, 764604399, 163990345, 964209314, 554340136, 10605066, 791180139, 145853949, 88479616, 811200966, 273939337, 40981438, 18734935, 138418661, 116119235, 700831169, 714632166, 94259938, 969803636, 88829522, 456641589, 816115592, 269679933, 113117339, 78562487, 844759751, 655723318, 648707800, 57518781, 350511117, 492699698, 106881454, 60268486, 113141396, 44414977, 98671508, 100616628, 432510116, 112858164, 17575556, 187110053, 635580141, 404748187, 167563791, 893574120, 947091369, 615847219, 820514840, 45913424, 720287895, 513333126, 148038683, 93060533, 138756624, 62822573, 882987243, 254592331, 938860871, 517799319, 49416789, 264779912, 569864400, 81388827, 540889406, 222947469, 512126046, 187997946, 733033685, 130944603, 201161602, 576763014, 707772318, 617427893, 469615347, 822734304, 48244295, 240531146, 835725746, 145056573, 571883066, 649369937, 241615683, 736186282, 429551207, 420093413, 731244602, 772092611, 464317903, 628401101, 212728561, 916136119, 834981621, 877954649, 216625784, 637748601, 342833408, 95441933, 715262200, 945823141, 568554271, 182382125, 837210606, 685799898, 694152237, 485476755, 910424910, 483456073, 161077241, 395794267, 2885641, 254328053, 792107819, 497964758, 342893925, 112551152, 300075813, 875564513, 847799325, 202236008, 306951833, 683737137, 385066462, 443798423, 502367908, 184708330, 279032395, 386156295, 433268831, 979679287, 505633638, 384741265, 66158316, 319266444, 496974102, 872807709, 611351084, 415901540, 790890373, 718207728, 704683287, 239691404, 961588903, 255743977, 174243792, 140696214, 301773351, 695819690, 238566846, 241011773, 530710569, 152947192, 838509063, 34130227, 41570018, 528085829, 781593530, 84990011, 350489622, 131433233, 385157915, 626343925, 790488459, 405690071, 965422650, 619525465, 9264530, 90133126, 684456125, 377174474, 947142221, 116011714, 41209369, 554603958, 149694126, 998803623, 805801740, 77966198, 205843694, 811788319, 762668042, 979376598, 713306909, 295502009, 165568330, 715599445, 964427493, 719285873, 852218548, 668694393, 757716978, 164201114, 4615181, 50914353, 812017943, 119969894, 639842503, 382327392, 298384098, 360197919, 883002318, 507957856, 793167545, 128910464, 373125781, 265730605, 161271053, 358225257, 295231858, 67591414, 576002991, 818967639, 166415050, 707015534, 576039665, 435347557, 202583748, 856450719, 577326970, 803267644, 437087666, 383824653, 47551030, 912201682, 280892019, 576085805, 63338890, 532318965, 60949931, 828769276, 546287290, 957892105, 755190823, 656786969, 345620981, 701541110, 116213740, 934671635, 976270218, 398490846, 227132307, 334243030, 598363236, 24988551, 223265492, 562171313, 278189369, 456825264, 608174023, 706128488, 699843072, 287555063, 892716669, 213792872, 476658273, 81591001, 998365599, 33866960, 704787421, 635366473, 315618827, 113995877, 166270193, 419887582, 212305210, 36305381, 885139875, 719634934, 69414412, 357380741, 779331906, 728581089, 310607629, 997158393, 71708541, 260101198, 37108072, 905108474, 531450817, 502372024, 253885942, 11020605, 539714593, 12239623, 700397296, 12463243, 602284851, 511062446, 284920500, 917794337, 787364136, 434800938, 959997872, 432573371, 821479880, 232955175, 207916322, 286708763, 553854451, 437631859, 940141816, 926310533, 37665959, 691580695, 8221879, 184640454, 138240463, 977639234, 578201219, 257363636, 271543772, 226404707, 635866643, 132041429, 662668430, 411088246, 498236701, 618472632, 641653122, 394124798, 215912638, 389322014, 99900536, 282053754, 774013127, 175670541, 852251609, 869845551, 572990528, 728109526, 767961454, 544417486, 389845913, 167652794, 241963894, 500622687, 917550041, 183469980, 940920415, 772816975, 753801769, 140297930, 843243682, 151976821, 709352842, 56985928, 132268981, 985146178, 45873854, 848213483, 927559995, 917042392, 241347825, 883769239, 158192152, 150743678, 665776333, 106006439, 824750419, 720834395, 901402616, 169616105, 27077166, 612374376, 434501008, 7020234, 463429409, 727867972, 210152092, 208589507, 70532245, 817447149, 381343384, 940030818, 853745725, 566154468, 651082397, 312664914, 859703967, 774596353, 595036757, 98914467, 889061247, 54141081, 209060617, 398543427, 317882596, 860960883, 217725673, 796230201, 270383750, 57267776, 219815954, 567844616, 140112422, 20378020, 481955776, 69894395, 627499012, 876682845, 523273848, 718028871, 200622404, 104396816, 896125491, 878310826, 114946751, 760718913, 432620200, 461051236, 767125076, 726819391, 559498979, 461428418, 663972009, 52525451, 972454618, 694211056, 119542619, 48566166, 793723258, 731360620, 929028559, 622372354, 966792788, 818093292, 149145481, 574683118, 465203667, 483051120, 151988180, 900263555, 352770701, 962305987, 570356530, 408178080, 186222042, 743164793, 398763577, 515954930, 115541924, 587899780, 259342613, 526976928, 471647246, 406101023, 429841973, 12030281, 122448527, 496038041, 172816011, 913784711, 117056658, 862187510, 358809192, 372009168, 33190159, 274232671, 528595035, 104389253, 561992728, 571678568, 152834276, 88213498, 633523034, 190689190, 660593584, 898889876, 94689287, 157464182, 800653770, 455380288, 92266155, 820031107, 505747481, 357638341, 20869234, 709381377, 891078742, 602441194, 991235600, 311574352, 65002678, 223811401, 354350710, 393208417, 639661278, 276941042, 744008423, 545267458, 997444857, 798363117, 611080963, 170945187, 535616801, 7609830, 635351146, 58017938, 942886806, 816717229, 998479826, 806196502, 63258769, 771682474, 806574863, 979921155, 275741820, 916037092, 525139901, 16010584, 92902922, 198798685, 872427710, 667158832, 926368437, 217879909, 448012428, 667211014, 803391311, 13570219, 441404151, 271049119, 502706324, 577498748, 188351774, 237369940, 599449101, 888231008, 132699737, 634927682, 383309431, 978149464, 563702241, 238692501, 205411711, 348406048, 265521945, 156311149, 748980962, 721373267, 220806085, 236128579, 63247597, 145441161, 31676150, 952592241, 520184680, 130968401, 808156010, 991476442, 64438552, 686985376, 291128160, 816215832, 806929966, 712707757, 962972580, 36366846, 770698483, 655528724, 673133736, 207827134, 935209694, 429493243, 593376112, 751236294, 972032545, 42881086, 88369235, 749006077, 143481072, 448198679, 295542855, 59088474, 962537604, 375197577, 933689047, 848804300, 120003079, 404604220, 249899138, 369777412, 31289066, 889322394, 148271416, 709636770, 533996530, 545518897, 928412836, 218355550, 999659774, 162746068, 526482245, 747444653, 315926599, 198774009, 103193109, 347279834, 664596070, 803700443, 121205871, 292576541, 389351535, 448576336, 554878182, 109104531, 916301626, 469174123, 642512055, 152331269, 224109437, 713969399, 692553204, 173311466, 650962308, 87307669, 648661982, 434939302, 783492904, 942997771, 327200915, 353137016, 676511251, 139146917, 618499592, 94769842, 949825576, 472507681, 835046539, 821547828, 581978633, 319851324, 589634027, 489544531, 558059438, 36866595, 580045338, 393722033, 682070802, 89240106, 707854514, 644390996, 519437951, 672617402, 326757606, 699398663, 615329010, 346405696, 212365655, 111742271, 151641219, 363857322, 464067845, 720643589, 49031243, 581864300, 545740240, 353557343, 151012552, 889774357, 154478969, 20302760, 926071094, 308381980, 97897649, 186291719, 766742485, 739063395, 186044095, 899893211, 925355103, 159623125, 371765350, 23286905, 126945737, 564213797, 600984674, 926802655, 866309472, 917147822, 13309835, 946054713, 165617581, 188855933, 913814243, 820422404, 639825219, 91835204, 226510013, 612766007, 219687215, 758633312, 739662545, 873044979, 304180680, 353608900, 810509629, 539540260, 22687117, 197769900, 407002322, 752610159, 440261483, 393580866, 456960680, 529605666, 555690225, 79230772, 191723864, 77511748, 10353485, 64846988, 109118287, 792993649, 560745461, 290719991, 398570390, 564028315, 424050925, 318650660, 884910649, 14517199, 324911482, 529342231, 777610543, 507899137, 13298734, 173523050, 119108724, 405565264, 222296470, 662709157, 95586935, 797805745, 626242925, 447486528, 418344302, 251223436, 359438850, 217252939, 647945873, 136713574, 85019575, 285845279, 280685814, 612387086, 293612909, 982224404, 331742117, 515191385, 960521569, 851435684, 396001027, 330417314, 724063834, 698514136, 426964181, 244125440, 115482888, 181638884, 23439579, 397970361, 423780569, 69744662, 819946619, 233241312, 722053587, 917526090, 928409170, 949719666, 839961958, 476111306, 478651220, 217312878, 655340646, 659590437, 425888845, 350822464, 430541433, 30436266, 27171832, 848920769, 77497562, 564907961, 382897140, 491225568, 893960886, 797995168, 662391639, 54029203, 476210718, 1985057, 150598294, 15286023, 361634568, 406441944, 717250279, 999728542, 525551266, 339887551, 183568637, 451564967, 38170449, 226104468, 239222133, 309980725, 843696031, 164671876, 681282596, 726763746, 978778533, 399046689, 979251020, 104706179, 446117069, 24167006, 93439137, 414008180, 181443558, 888079144, 934826558, 639598854, 582285943, 189843200, 326941536, 643226526, 68522062, 392039820, 326404322, 997183994, 501984548, 184027751, 577959377, 694713858, 187222667, 587821414, 89728898, 333047070, 972699986, 168638669, 779179490, 107387602, 770141912, 684153093, 726566591, 605656673, 992194909, 609316608, 582201760, 922463166, 946961847, 379433190, 47654965, 511553580, 96958697, 230689562, 784464277, 881973184, 36666825, 79004733, 126127194, 253389969, 265136982, 128688949, 359133314, 524560328, 658040339, 936174101, 812917585, 207867459, 465468322, 990645480, 130845747, 894193879, 625962647, 31821476, 100119029, 220824802, 343683776, 355191380, 844468647, 58105684, 270150181, 633662309, 591021890, 193037855, 332416946, 326645575, 756955871, 257177647, 293110296, 124742301, 38286944, 391057355, 993984243, 410860666, 968266935, 824278157, 225977902, 259511018, 855371047, 965653911, 211361798, 212765426, 181221105, 444278867, 987255628, 346683074, 372268985, 897945762, 52329396, 179346949, 10110033, 268116518, 813626620, 594221891, 81342065, 754960472, 287266428, 336595518, 481923406, 171346736, 49021325, 415172474, 422379993, 152583947, 382922711, 920997365, 933564557, 903984517, 968458341, 893755152, 487707477, 101968987, 686771359, 634606666, 430444460, 400611055, 708768040, 172658371, 618834300, 484777679, 105494235, 367598870, 716734249, 916746920, 717800862, 308937366, 842335563, 714584895, 92754819, 443072367, 36962951, 613543474, 756178271, 72956329, 756837644, 624641527, 450077753, 812368515, 569582557, 639420820, 530530730, 70855344, 952804748, 796822535, 488323053, 710536584, 624784899, 712247310, 459669370, 957401909, 751896170, 325150242, 247214257, 696644101, 209540641, 669350785, 259300509, 612313578, 205647600, 811003755, 254381354, 540454079, 703362590, 310551973, 61748001, 357029884, 324929248, 827935393, 563601238, 688618727, 825571006, 480054575, 181180246, 112066723, 748212198, 331153532, 567282947, 290076127, 521587799, 297890739, 865269216, 967939475, 763108878, 591551240, 145383648, 774065297, 52491731, 405722578, 718789221, 94922972, 583019261, 984322013, 79034581, 189309021, 86413318, 88163763, 4648311, 814751685, 175836523, 139922367, 973607282, 739682081, 846881462, 15119518, 710668680, 51943793, 579441778, 987107348, 795003339, 770845517, 979245515, 657678575, 505478916, 138833680, 210419118, 401528195, 90754491, 390319445, 329349108, 305099837, 414990001, 857544998, 789004947, 887602582, 515183612, 829880758, 47096088, 708442429, 142565235, 295133171, 763464074, 118879471, 640455965, 748343569, 391622282, 105799166, 636080402, 222700226, 651680239, 623177173, 461000192, 56712215, 265415393, 305953910, 884493030, 585529254, 13080002, 230735129, 757330268, 107217085, 51746340, 762837923, 539599271, 221506416, 269173461, 43293376, 782297746, 976308666, 690181313, 318150144, 708167756, 821103418, 555230704, 945995913, 531871050, 122777114, 369127387, 636715704, 369824127, 816428071, 433568614, 368659805, 367999618, 9654944, 2348861, 261074690, 573224009, 564278821, 546359395, 22277193, 750628173, 488761133, 276391134, 91639255, 228162464, 113717484, 136791405, 684115054, 294266540, 82898739, 709703117, 649090559, 841076931, 242614763, 347854666, 942884328, 775069483, 104481726, 968702792, 914297237, 348167974, 559179521, 741770175, 788760390, 279321799, 162223451, 332792914, 996067388, 62540329, 434279629, 788292097, 791634514, 133062211, 284577259, 443910144, 439600530, 22362030, 821978563, 231407190, 167757613, 3656827, 769222782, 475742134, 716428357, 70587370, 950954446, 118072948, 970125786, 208237278, 238565314, 215263449, 570325795, 39098582, 585828848, 605905419, 84923059, 372711005, 737041314, 767688502, 458901938, 151095589, 930872147, 542784812, 866781406, 613513041, 37669418, 188189617, 452459466, 246651035, 820506535, 260836358, 655523957, 593014767, 120561820, 998408197, 602327899, 87086535, 227030138, 410067225, 724827352, 646059280, 433978306, 811902308, 323976096, 988178905, 477309015, 281193560, 201634451, 141022991, 498947096, 673179515, 184256209, 915664267, 701521067, 779351039, 50149420, 840690894, 989920423, 829714630, 47961370, 780377965, 129825526, 927208708, 455412724, 282912938, 181933086, 525641652, 859005053, 558345568, 757907633, 73572405, 728313810, 906395348, 685105665, 556575019, 65061648, 7898769, 196581625, 910500867, 612581725, 624448357, 350953210, 480505808, 115580914, 681678219, 140569988, 327776616, 646030557, 158252267, 161096483, 364689492, 417963506, 293636005, 222915229, 324773435, 356669949, 924974066, 405006629, 570736260, 347849249, 851840809, 762485961, 859603456, 25770201, 914028669, 129312892, 901303658, 8417715, 328572459, 929840554, 384670437, 23235767, 267469371, 467423804, 289671680, 959476589, 468326000, 627515745, 364935798, 262661154, 467120693, 490252397, 924766487, 4172248, 841968941, 202241304, 395961705, 24037529, 857781423, 467632628, 504409354, 490057969, 597477316, 960695218, 622470780, 119049854, 563620821, 17750208, 620497501, 520909475, 782201153, 352870115, 485673438, 921108797, 13423603, 710669842, 716968458, 558130289, 287197127, 526358680, 818171345, 460982252, 400689566, 28302417, 523310041, 326324622, 657666094, 295710749, 733399285, 833132862, 663611772, 85968064, 756240864, 124956880, 497232550, 921575951, 67924871, 737963849, 240348718, 917141997, 915409060, 500202890, 304472803, 968352867, 121053634, 881412929, 564900697, 260811092, 437899717, 354085350, 435291613, 616838009, 85831772, 51538376, 562554269, 272079920, 854530977, 878982950, 319411515, 433193683, 716666851, 931472381, 893499415, 839008081, 624169743, 756233584, 209623342, 59306492, 917755992, 142899721, 828893501, 486653218, 562907150, 907983593, 254430547, 367240830, 141606910, 368434072, 869072381, 108719151, 881670907, 398748227, 257967480, 37436714, 572100783, 806550840, 576166594, 421159613, 116493757, 198466413, 582899500, 118982533, 18113930, 84100792, 230749996, 652694868, 496177600, 577921899, 64821112, 674220355, 497784913, 467722657, 224548179, 645455252, 19497945, 722920780, 814558381, 867438420, 918529104, 251691223, 779084018, 650273345, 392808410, 359194570, 199584851, 846112721, 127275060, 804178164, 353306708, 233557401, 946615538, 1468768, 501737168, 675784454, 661287973, 39088986, 631570298, 937815012, 119916282, 93290688, 66509484, 926379726, 200592710, 605329758, 147206867, 997630903, 777754592, 781447033, 917782226, 583814559, 318509970, 667817466, 51590418, 82719094, 630871827, 729009728, 865270939, 642392867, 296622200, 812749291, 526833848, 421406755, 182263479, 990610931, 904685773, 662544629, 477848486, 403643000, 127060127, 900809371, 143387047, 429446995, 23107398, 818981726, 48670190, 956097470, 303026367, 280423132, 137952937, 440157046, 431286785, 879686870, 619798142, 297179575, 797637750, 97718254, 111662179, 598513553, 403882723, 8600941, 113084547, 88953834, 398469726, 226673536, 859108352, 501513283, 853411484, 243533275, 107405390, 714599759, 549595489, 517196454, 299977900, 584445791, 983186537, 676947341, 878576959, 145393141, 933614148, 382955385, 322665636, 645135577, 148708936, 827605891, 113606996, 72798167, 246092557, 24101377, 344917603, 764768946, 575026705, 590398013, 90450282, 926951145, 67013608, 16278628, 657456205, 856052198, 321835464, 724820302, 173064861, 8260789, 45622246, 121426543, 706443551, 907161041, 314700965, 74379841, 852462289, 115777017, 244140537, 576239589, 500502931, 259316018, 79994763, 940197297, 711296053, 858783569, 130831274, 650946168, 170547758, 298478539, 7005581, 778682929, 351621463, 619910675, 395543128, 76959762, 677564440, 867246686, 636517991, 134807608, 702177227, 862992502, 3407854, 86722287, 547564943, 749548184, 310233764, 801555210, 573496839, 854765337, 522904176, 740381086, 857640262, 242623348, 492142761, 483859530, 499528099, 55183770, 553665464, 408810997, 86239826, 674272435, 225609826, 515708627, 63873275, 569288003, 983819036, 569939799, 994114751, 456824975, 396295378, 982607277, 324237687, 89771548, 695360551, 318773683, 805074563, 386699172, 967467982, 635682037, 969830612, 542215154, 236979057, 117824392, 294633810, 960638335, 459416777, 7038652, 772980735, 4127373, 649281307, 106516342, 11776974, 367106494, 238326827, 501979734, 457623922, 939295725, 383939556, 476737035, 257860288, 235860770, 4632675, 137914589, 234115719, 592847929, 818504270, 614001786, 869093467, 817616622, 727687379, 322409188, 629981335, 1917635, 810415318, 308960352, 874156196, 7557045, 102698720, 273513430, 325213430, 309214973, 858604049, 615627350, 65638782, 177393094, 738428822, 465215341, 33761107, 73199697, 345134904, 121979559, 56543806, 143975468, 374599085, 612252238, 174706220, 677294091, 618458337, 401397057, 827180350, 403990350, 670004283, 150718091, 235735624, 694282431, 526163666, 688054694, 83286610, 224673582, 605619826, 372907380, 97053714, 34661703, 29647493, 69208747, 402757802, 74901448, 236197972, 22514326, 27112366, 996959354, 21427362, 938377594, 192318790, 339014795, 547544074, 605824323, 869426234, 967980650, 662158525, 431049499, 979566940, 764901256, 651277228, 85200815, 391483734, 924706577, 997264878, 68423358, 526100270, 977063191, 841086175, 43473602, 516388834, 965715511, 99189351, 628112185, 799368290, 118132976, 979016382, 101607538, 261370379, 40880316, 466661128, 356278030, 573420952, 372311106, 812894831, 825440981, 442208047, 897227309, 862191707, 783853240, 202208913, 206071237, 341136226, 842696539, 339057586, 59710989, 126202483, 518772192, 13602702, 780324510, 24385919, 477742634, 126577152, 811856643, 910989510, 235270038, 666134539, 890945162, 859350850, 75188453, 410418644, 188675544, 384005036, 577259395, 460513197, 314238191, 738988164, 276141747, 195159240, 626796289, 950919266, 319781266, 205147799, 207804358, 552413462, 634228431, 161394687, 288658248, 313615563, 11897603, 40013028, 129558663, 737009561, 234015831, 61513960, 718470091, 819250934, 632786821, 702059181, 26477027, 56235016, 835066388, 948128549, 660840881, 760243261, 28271624, 5772090, 374752515, 43466601, 984680183, 803830477, 952182240, 278770236, 629522345, 523102224, 128511597, 111819053, 87611224, 101038504, 642055598, 716087989, 792473335, 405762651, 392296132, 339272812, 382047077, 882097187, 327806668, 944093099, 409025788, 401264869, 960001703, 703982410, 344953547, 221396107, 562693745, 468769405, 637372639, 466491015, 644672486, 955473087, 900944590, 61507711, 613443148, 862977767, 110261778, 477272641, 462834320, 463625384, 874136150, 463622501, 825681569, 983781847, 944904276, 364597167, 13740878, 955164895, 809107518, 596580800, 925336335, 51210771, 705969397, 173484282, 260513526, 879158896, 129052290, 609311716, 145476847, 192977243, 461194709, 823970718, 146796501, 897565551, 104574060, 934603174, 180151260, 643263128, 890713298, 109896249, 190320523, 113879678, 360797247, 218489779, 108162930, 561672657, 841717634, 66470427, 62927305, 495734320, 717649527, 60417315, 260005330, 573338243, 336726012, 734673839, 779725470, 693738874, 773514333, 382374371, 294981573, 8535066, 714933560, 510316533, 633262591, 315412405, 146650039, 228957295, 942045288, 351204663, 411709085, 195259539, 165037935, 36680199, 156297904, 526372247, 253213336, 236928376, 620533894, 132566626, 899719821, 951651598, 743183308, 916966604, 115062556, 914074970, 552988730, 919844541, 885404412, 77762421, 75930949, 4647034, 793289146, 232196246, 337498501, 625973158, 1458431, 682508278, 999448297, 903419423, 60858071, 432361903, 414820851, 162124595, 464298700, 660161349, 76767172, 735671604, 14787580, 574237655, 213736545, 322948962, 112028365, 310550714, 40587988, 55493148, 665435638, 29417937, 91985505, 398113851, 333428283, 144317358, 825777021, 440559964, 115183739, 448808935, 169202281, 307366717, 7220162, 528652011, 914501238, 481845487, 216267172, 260029080, 972504493, 384976534, 79862174, 652236199, 22757236, 228776286, 47310672, 374493492, 630529265, 621042557, 884709657, 931411949, 232323860, 334823352, 761900502, 609728631, 64621380, 50765434, 456619957, 98041499, 663516444, 985779084, 945706761, 967060680, 232608264, 819834086, 489382828, 987800764, 918849238, 337216067, 174072214, 551952062, 321929572, 159009811, 801215187, 94159797, 434217496, 537001344, 300798845, 349682877, 604855547, 412572109, 22223447, 433276307, 750823350, 474133678, 600395776, 619128557, 135387784, 70282093, 701088357, 742223588, 966821740, 157205909, 754826753, 187334842, 118641570, 937021152, 809896791, 976990229, 407792419, 939847134, 61536031, 734912319, 492891536, 976597651, 252184914, 132108998, 5322035, 839086227, 144590987, 775187261, 936492925, 521920190, 234913913, 123192605, 116855105, 976674955, 403949595, 985034998, 531776663, 890919874, 79830365, 679148827, 371730162, 431882189, 942202241, 48651509, 642125903, 897704124, 286086824, 45365335, 98490660, 770114430, 222263119, 895157478, 434280442, 801956188, 663261722, 645128655, 32370882, 744051083, 469275500, 553376716, 643769233, 806885445, 111926957, 546648683, 382351893, 710172405, 946479387, 67683980, 191297528, 354533537, 525519581, 600336334, 974591932, 108825455, 166333519, 691229086, 393696710, 463488563, 929090672, 873326967, 103090771, 213242224, 604830503, 346162670, 215773545, 199069610, 130896891, 399266018, 725051298, 907930986, 370264698, 778653927, 864184849, 922852482, 254766340, 568462840, 206377, 321094592, 803381411, 201685988, 800183928, 941658960, 300640908, 990203012, 136737012, 331458394, 248647640, 17708418, 272638040, 290414160, 907941136, 540855748, 11762532, 710336956, 564604397, 368842864, 504210006, 80078358, 197694815, 499553796, 487073249, 825412157, 105246726, 941155910, 790319215, 501668388, 312777572, 605663326, 311033302, 561509916, 254013294, 796920600, 136501508, 106783469, 560918238, 692594314, 71268658, 309438558, 675934919, 42669581, 681088347, 964009519, 491352865, 885957918, 436098106, 139180331, 594131534, 917217035, 822067657, 374304979, 964179990, 61491668, 550829869, 143089713, 313078907, 375233377, 180874578, 269671941, 978795795, 689169123, 131636921, 513574837, 915508166, 225415207, 392230741, 594751344, 242440401, 919341248, 223514971, 667218994, 937511171, 455711536, 10078928, 331291939, 391500680, 62034352, 81785269, 968460581, 138424254, 564625855, 729487470, 511767567, 605492334, 732138052, 755921232, 254890572, 863451486, 127617354, 676188972, 17571058, 904490745, 532192680, 292983005, 132846111, 947551853, 912750866, 921092919, 392056988, 821968320, 59253089, 581738262, 574903221, 869507494, 186233823, 148189482, 332572032, 785692330, 47023485, 842708877, 753443774, 565926906, 121415157, 308057627, 734442650, 41615594, 501103083, 401631025, 671534654, 456364793, 104467445, 290208516, 392144653, 940848906, 925470281, 154957546, 621295458, 840249470, 13358196, 965879462, 500208739, 402776946, 603676078, 271094518, 118243670, 898988215, 747472860, 790001648, 813792182, 874833709, 657099801, 160937464, 194045875, 94339910, 727935884, 204065429, 196280944, 358944016, 490512489, 1165437, 846103992, 626061688, 696403563, 461785769, 20497903, 703850779, 73093555, 708689957, 800779615, 215952134, 53131286, 417305228, 114859541, 442464090, 551069647, 878071265, 29107249, 372241005, 634707324, 974719819, 110738617, 108592548, 901337933, 229972571, 471414775, 949642, 721226143, 43060311, 598615094, 755977241, 196233835, 360161631, 627614971, 678122111, 502604948, 228177385, 364494731, 439582673, 515218009, 407991137, 984733266, 903017880, 547554389, 572167106, 773757854, 534769593, 446465434, 229665198, 747847705, 647570622, 272320958, 610689349, 31539630, 451079179, 670487543, 37439392, 824131351, 53576754, 107329894, 7264978, 843401014, 294267029, 91117362, 253662823, 556026866, 442188765, 218649666, 500416445, 953229463, 699578021, 334831622, 107915814, 57866408, 336584321, 293735427, 539395714, 95291211, 329561193, 574645138, 826873807, 901394512, 387917246, 757779808, 427206346, 812203879, 97512599, 950185888, 878799102, 376961826, 520650932, 731836246, 125918731, 483193131, 391283410, 498323334, 927029816, 596258527, 158366387, 724606254, 870527419, 148244122, 457927934, 960879537, 218331497, 240895934, 731288143, 710907620, 772841079, 951896275, 560502353, 499771129, 637800264, 63649802, 315366008, 366855660, 317527083, 180821186, 372312597, 837954068, 89242428, 746880368, 569406839, 626590619, 641707223, 510421727, 608279571, 125568655, 41916740, 912991542, 878188579, 60341422, 545998170, 393619559, 314295353, 345204829, 504230456, 423781508, 85526435, 776233202, 188270489, 18696592, 493987860, 75162296, 325303014, 667369614, 174014217, 931701552, 450209118, 79757845, 253283765, 420628579, 781339907, 117315544, 332360062, 370596187, 907538609, 572540469, 606418854, 124290516, 596597528, 206483831, 833152643, 203092461, 816455522, 540432502, 340717951, 48178133, 714503568, 725891930, 211068903, 939551524, 388186055, 980685377, 442140514, 762200178, 558437291, 152012447, 160635377, 411836960, 403992439, 705114106, 830993974, 75059508, 952250167, 420419325, 559375223, 528944973, 543346278, 713405880, 604402537, 388767627, 17747746, 933623736, 544100901, 718474181, 95012986, 302905981, 50074208, 931107879, 209765242, 149252498, 225834190, 991627081, 803249647, 927590665, 78008013, 115649821, 46819590, 710812906, 973961459, 249883979, 115000099, 71381593, 414558525, 841157385, 240300072, 99548675, 224819712, 121164511, 390417599, 979023386, 219323766, 885575488, 451048037, 147083949, 286253146, 693255542, 447109419, 315702858, 378821247, 707168621, 1489227, 845591581, 958409668, 509432507, 14844560, 384416868, 263490300, 163170564, 864030507, 476310135, 672886576, 348776308, 46030824, 545946048, 665088752, 287250807, 74053371, 14953362, 651525591, 964470462, 648487278, 646172821, 401799668, 358433908, 300040499, 282042115, 578396454, 243710987, 799243680, 378317775, 835249305, 727447274, 581931747, 886343391, 826796945, 402553456, 142446942, 454466367, 764381437, 504613883, 425588156, 385088313, 811048180, 1032329, 756441483, 201793119, 453250998, 458006055, 919354115, 232749218, 41364317, 11331347, 112883024, 996924067, 635380175, 545908341, 824325781, 819373048, 183168103, 162240970, 272729678, 37595448, 299480896, 466729082, 705402330, 232723801, 821202220, 68312271, 368071199, 65233164, 157127378, 227934814, 937076297, 589235159, 228220996, 97464808, 353983973, 878932021, 817952881, 84225098, 965455869, 823332129, 505954482, 334715432, 302594131, 251262199, 803907169, 93661037, 55535608, 379060858, 84838335, 96238384, 9290853, 971017296, 159460319, 782968555, 720198716, 954963898, 578434586, 91616933, 60018032, 553233381, 382221535, 873750568, 632618190, 222383033, 970089851, 604277733, 645691868, 908357185, 297961772, 59120847, 945104124, 575958856, 77190694, 263871270, 330703835, 451676409, 118197565, 710058636, 181847451, 233857854, 346856746, 143690642, 675474375, 99262583, 504417340, 624278671, 439502833, 527852198, 149924607, 577530496, 721940410, 369865320, 508758822, 222617578, 617120372, 743560841, 612691372, 112780417, 65386796, 591736755, 115850606, 126445791, 313082454, 434847806, 393203279, 553306912, 618057052, 99451003, 523708633, 228504356, 771950456, 222602465, 156094759, 52576457, 36733882, 851526663, 570580011, 16739600, 608056599, 525561898, 518579575, 278277499, 583521105, 828879533, 44871620, 183535821, 693005033, 177266881, 764650578, 940120798, 573061007, 765166432, 20144388, 57291468, 825028820, 104952708, 294562678, 765122811, 287006241, 465621325, 267199607, 435488972, 638883428, 295539396, 953061, 985710698, 150848328, 70123814, 188376851, 451817657, 990163985, 835315292, 43512205, 958168033, 743240356, 875772340, 45780420, 425351892, 709166559, 428116263, 279814791, 650983985, 806138077, 81309794, 567086844, 289140300, 618507517, 434986739, 580766563, 423427304, 574870748, 323733783, 417613030, 638615392, 878604216, 603501540, 485117999, 530285181, 238880595, 12202500, 514944544, 313853598, 717584554, 175437526, 83452151, 273480366, 769506782, 953962840, 140543378, 28025993, 172419167, 893499966, 848268738, 501725711, 483226655, 600216209, 103134704, 158645577, 121985290, 945843301, 114404813, 596806604, 425456869, 680536420, 70685596, 247333759, 203125499, 578746610, 833815585, 253235351, 961439550, 40535400, 112108857, 308874689, 788923224, 868589190, 932167671, 841820210, 642981612, 247219758, 434594339, 635172126, 196712445, 168730382, 966094812, 824628895, 825864174, 905340435, 928030628, 30015213, 600006424, 872245503, 899773077, 699241543, 122096817, 27299012, 838951382, 25734719, 317682695, 648708423, 67989542, 238932190, 86381087, 693940993, 875561072, 996987860, 707549126, 954185821, 386196329, 106120269, 944912651, 298334370, 524419423, 644355073, 63163737, 174479650, 164299395, 508940301, 332272906, 53248942, 247265973, 418351266, 368267384, 422052234, 293410797, 732811667, 546971724, 723756108, 614509126, 599000837, 796708901, 725960062, 356163427, 794771978, 177328484, 445507130, 510340468, 35538136, 81976464, 34391299, 927418406, 477818294, 43689703, 439388203, 394244366, 78008367, 914578077, 418773491, 22152018, 587274173, 275162577, 918118226, 935999265, 814911158, 354110518, 858290189, 635549624, 98870390, 709785599, 887881886, 914478646, 895120321, 164287812, 314264820, 186541767, 674331927, 225491870, 326200713, 77116247, 598597697, 818090931, 109464154, 518034446, 499207562, 755864283, 445232376, 980495862, 197424134, 245185523, 959450115, 816356060, 223279737, 8608450, 593793379, 321791822, 784307786, 399312594, 153349061, 150270405, 946906541, 804410317, 107618532, 1910059, 37590555, 10222823, 602251557, 744468766, 839801318, 71202120, 131596617, 422142665, 458779545, 241520085, 276954343, 967558330, 799655804, 655413480, 883711475, 334836251, 978693995, 125700170, 104805698, 325754324, 810085843, 859419899, 295232771, 289957627, 470420524, 115937192, 788718115, 716289521, 677632943, 871092960, 63357121, 484222313, 508876108, 46359733, 778952317, 584258285, 126740489, 409577955, 884579628, 893498193, 818469927, 36798985, 5250559, 199315586, 970048229, 697715357, 241292479, 746547595, 271458322, 144751626, 534584709, 841108762, 423093311, 610922760, 659511013, 238493324, 945789744, 7250892, 252152543, 942554670, 676958418, 64748098, 240052635, 590347379, 386928291, 316282299, 527551546, 391833737, 364756057, 182216392, 199219722, 358861981, 259233891, 492664852, 668708379, 992779680, 493123148, 781354663, 365319636, 271375479, 899892972, 566833161, 527478835, 524285029, 533078762, 152977650, 557438091, 538327223, 110010728, 759864007, 96600587, 654385733, 790236822, 116889237, 757352901, 487609916, 255239838, 84092785, 889154925, 481103580, 631938105, 677096320, 234983365, 935967300, 484696825, 894064704, 602402069, 333661725, 565788336, 939952814, 897237566, 241602528, 869595266, 306912758, 27003612, 730657367, 846873623, 30853092, 442831826, 643662727, 957301328, 208914950, 890780383, 237393844, 646698560, 647960453, 381759634, 700515049, 844054267, 536071965, 67616590, 206157445, 790034082, 4405351, 819268837, 579177473, 839900507, 590787996, 202443622, 855858106, 561719936, 488852140, 12967205, 482439597, 611539354, 78166714, 280948812, 737627178, 669865093, 313340477, 476473073, 909396826, 591338883, 78288265, 530877891, 463139330, 501982582, 150985189, 429884416, 725369782, 818240633, 832527090, 72336356, 281391090, 581058936, 249394443, 477303135, 182368400, 399513109, 228437372, 793634015, 378937166, 153430538, 726675766, 293077251, 214849917, 62544412, 857407679, 628568161, 666000912, 585538398, 19279563, 909068291, 157597010, 885610319, 243474076, 112447797, 917493397, 378937919, 166086209, 829657210, 230387077, 995566176, 435626255, 591693740, 392897501, 63568429, 533687153, 788270599, 430317628, 416429278, 277669773, 313909880, 663516128, 625963003, 37804768, 877059911, 211149747, 943791563, 783561177, 735957013, 516689349, 721503822, 267560323, 55591843, 176718856, 143928991, 947965215, 270191412, 326631726, 524195728, 972659080, 628615174, 308664756, 555546587, 605569131, 875381584, 127816691, 731478637, 765056631, 115181206, 406236804, 771451015, 418432166, 373448615, 603655771, 722773347, 129630528, 151866038, 994906608, 880663692, 650354898, 615986034, 6094898, 943692786, 477921207, 625864847, 328559101, 705332648, 209062074, 216009804, 22390976, 101452563, 597167779, 53274153, 25492319, 538633189, 164435418, 647595215, 685655509, 414889961, 176172718, 702405860, 410660039, 743812593, 755941364, 593249096, 118467098, 945132473, 697915430, 308952096, 89902673, 751694779, 87855352, 263635575, 457323842, 190818459, 685734020, 379919269, 834271552, 681243201, 419157050, 819155768, 826310437, 22769510, 435065404, 109910640, 18147216, 643538594, 18481644, 821819049, 845422686, 60253628, 656401568, 517658737, 834138762, 596925318, 627704489, 35167490, 502001505, 823529119, 314776696, 992685689, 60900058, 138037412, 150918233, 304554924, 201076867, 152621869, 20277765, 151475060, 73211725, 754310922, 107697813, 541407248, 543404797, 903956135, 136936998, 545139449, 786459819, 61309226, 424989400, 266235878, 417964845, 109119156, 807598932, 218601084, 476877349, 468634039, 509759924, 15753363, 64756869, 741971901, 677180556, 857759239, 94786140, 430767484, 741729551, 105992822, 157415991, 783686211, 896941226, 703467089, 66866666, 132581590, 358241191, 208529527, 62448385, 597986959, 936330531, 147069301, 40064210, 196795959, 217845111, 656141020, 433595795, 32512294, 766257498, 823316405, 241681214, 837565799, 6056286, 649245971, 305602768, 277816730, 636332532, 372303264, 681094337, 857662027, 608427703, 320255885, 946639813, 616480115, 365674608, 942422589, 250051629, 139715071, 430045635, 494515290, 349743718, 272905165, 485016741, 975925622, 694811746, 832426283, 525556754, 432124367, 72025662, 940481482, 192626054, 1212127, 483339175, 698361271, 5245773, 118877284, 810720478, 142817178, 27550456, 124508465, 403172586, 810746617, 434651704, 599305681, 625254715, 811488812, 816799765, 238178731, 953392487, 292038742, 87981977, 682811812, 12998363, 6112103, 439878643, 401639927, 614129146, 655127918, 379238235, 918529927, 620028453, 20532905, 937624324, 417011782, 477879913, 931836589, 926797399, 777971880, 138439155, 22088384, 517777535, 683293101, 512087998, 341503788, 577860132, 967165368, 637594411, 898845725, 500127077, 177767359, 379228314, 751787680, 649242459, 246576584, 362187156, 310875294, 846331685, 512435714, 890599306, 134494930, 96470444, 614555979, 238975561, 667833837, 533759237, 645281318, 243672854, 951320927, 835068174, 185167273, 195531386, 439003170, 365445676, 242246112, 948893319, 629428389, 91467379, 486926179, 855595383, 234080347, 791329303, 505369650, 449883665, 52320215, 463515391, 379988868, 649516876, 770757231, 495422713, 775437972, 855225408, 458361463, 450245430, 335548560, 272590898, 852603635, 698400661, 667273503, 706160287, 441310287, 486455449, 386487214, 700057170, 590932855, 844110257, 477095895, 639747945, 940574733, 405390542, 226206041, 798875897, 639439835, 57137257, 173666768, 180072081, 459985322, 825156232, 98882545, 352548193, 163076256, 426479598, 335168478, 327003665, 539944982, 736903899, 398616822, 196927292, 484696617, 890568848, 977092393, 977379120, 708453937, 335980191, 877540752, 702709846, 431806869, 823782648, 280871305, 227945607, 763969179, 225266040, 32664619, 385921548, 575821874, 69901514, 747148045, 773286884, 854606322, 997822718, 706622003, 611436511, 704189482, 530245357, 924063696, 929782146, 757512250, 18304912, 146451619, 982058227, 686288925, 323294438, 475992556, 630303617, 123543915, 371849912, 297036792, 190862447, 632061758, 253343575, 632876671, 64684484, 318375784, 205531942, 221644818, 93307159, 550359003, 671695792, 17127512, 685242642, 711263811, 316892275, 41999943, 163900716, 605298358, 412445645, 689721577, 33818133, 445678523, 888953903, 604515542, 347580437, 628884819, 900126046, 189140585, 610014535, 427358967, 436842801, 563345892, 46490868, 273928124, 498019478, 469594387, 263438162, 286887198, 612349271, 12561273, 456896483, 450646687, 991529087, 949243067, 272213506, 952227232, 34950780, 947702407, 941123228, 241032841, 677779023, 971754451, 456901100, 528244606, 509696344, 154185725, 534201793, 493385422, 894426487, 240438009, 624877256, 909986340, 554861024, 175235094, 769123399, 745874278, 839921385, 941684542, 730597582, 989550775, 59491635, 734487099, 788669937, 906561875, 188957660, 830561354, 393949756, 214443969, 475205895, 86772650, 39510815, 278799360, 764504344, 629849607, 935448786, 359966615, 497464706, 735475971, 228772465, 983091125, 73357857, 269889221, 542674883, 373709772, 697954176, 753134696, 459198832, 491520684, 766029626, 288438995, 716576264, 201955250, 30703068, 68862105, 19196649, 101489849, 76349934, 165603479, 951843619, 30018030, 647351743, 888588899, 912344255, 736654205, 703998480, 615042037, 965701426, 655441334, 558875075, 712892125, 766678262, 659667434, 719977424, 383192901, 19629754, 352277487, 908287808, 279426180, 562049849, 738732637, 69445330, 522514498, 840535303, 729407555, 316119809, 944065763, 304094705, 701605653, 53504294, 598504812, 49951314, 658606999, 77115555, 941472322, 458783336, 98214000, 853730613, 312167084, 82609745, 940526831, 600301628, 391288190, 785682216, 84058909, 881327484, 69288807, 39316084, 507944159, 562962066, 683473158, 243338703, 984717433, 636912649, 177890026, 500430358, 187065254, 882643348, 917200007, 535878061, 749134287, 3339248, 288166314, 635615413, 204586113, 150460922, 1442113, 53746583, 375688741, 391726385, 353469571, 823312195, 170923744, 175224300, 794730063, 827368148, 412827689, 668284144, 512134398, 328370010, 29268927, 735058082, 440741561, 872317224, 164725699, 438402110, 207869913, 861217769, 240241381, 260612685, 43735493, 623023577, 26995867, 600487152, 361906411, 680339951, 63598407, 37527399, 155781353, 434634178, 304746199, 913847076, 224762988, 167804243, 639883590, 72876601, 209827726, 406442508, 81234496, 94531936, 453328150, 961721141, 330784396, 805665136, 722524995, 250545758, 854606586, 795238344, 425607258, 60640696, 719402503, 664935311, 62872989, 144371799, 947788330, 237747442, 501674274, 411703574, 102636162, 369584771, 881517651, 970458282, 354046609, 931655273, 819881612, 140668663, 986207341, 700971219, 920968869, 809137354, 98034452, 131034671, 567450831, 171240290, 407467050, 120842714, 69921292, 286578313, 508864948, 213298682, 553720109, 120208090, 141213959, 206557556, 72248718, 394416380, 821564018, 499578894, 908895335, 545692812, 349413525, 372823777, 484916671, 294049132, 723889777, 920621784, 270647053, 394655425, 544226039, 467163478, 209339892, 590329636, 88721690, 584771390, 13077989, 758429129, 602926158, 197585891, 816351775, 151261742, 782943393, 90279560, 643583647, 982708837, 883672960, 42019715, 289187298, 408402903, 462833487, 449625153, 647971256, 563325655, 706367609, 423782425, 100938454, 107998895, 99703706, 121415591, 522373287, 614685673, 625764041, 781796306, 138541174, 27711579, 892040501, 734339178, 243023915, 782021389, 833565283, 695882000, 285811016, 497806151, 31691145, 57129559, 251307904, 779092526, 793267301, 658025909, 693649091, 619036521, 381517310, 922742875, 205580069, 30515307, 208130272, 587599119, 648584127, 919408895, 360458100, 960897091, 720382997, 111712440, 88745111, 185429559, 308804894, 408857237, 863395506, 334245141, 633842813, 477268971, 401152630, 14063055, 720521371, 935375542, 276438354, 885265795, 688488727, 581123231, 975495439, 261682075, 837104047, 42346432, 692374045, 309669800, 267451919, 174108040, 6595997, 337255582, 838200819, 941419191, 920315688, 214037453, 292363846, 316575386, 365518883, 118131092, 154373416, 186735714, 786515509, 997291056, 153891935, 684419135, 902967191, 695624366, 457745094, 35371304, 425514687, 504799899, 611496843, 363684337, 704192597, 582599162, 366169061, 308254503, 102875357, 94767842, 123232998, 2761678, 111344137, 341127531, 696559674, 938059699, 84887044, 205880409, 635878746, 335456550, 666641053, 606969950, 589604978, 794296566, 777013588, 212294687, 859445320, 515462096, 215394052, 263381700, 692435433, 548439338, 620140842, 968992603, 490183420, 558448626, 135498370, 426912279, 371808526, 955967359, 263734437, 178435251, 74092345, 522505733, 693221948, 882495061, 572424045, 797164333, 937954745, 320925166, 457827345, 63258792, 979090457, 553607485, 227336522, 471517241, 575612057, 45495911, 731555001, 694001310, 889308891, 921326495, 377306595, 665711152, 217530794, 22887564, 64693913, 476848987, 784932483, 368198260, 407768813, 543101092, 887532072, 123100620, 718346857, 895540743, 787869425, 130237151, 402939142, 975199181, 370419741, 882472912, 200165802, 20221590, 320413, 90213997, 896171375, 649483214, 997978575, 178626955, 794072757, 517444441, 172928115, 857454414, 621064728, 109854007, 627842876, 213554152, 759458527, 724149168, 778217605, 120855583, 286210575, 770743323, 261670957, 4748890, 943656447, 660150212, 37071260, 872366346, 783297731, 603187385, 293060786, 292627731, 249701865, 349177395, 344649092, 753893285, 530923695, 439988580, 101867439, 334559192, 617130676, 562235100, 557278900, 10287733, 900215349, 690056106, 6774673, 45295820, 77635702, 93648363, 428480846, 757888909, 906361784, 913974095, 5066252, 42130062, 557832171, 364673773, 153774273, 61378970, 597176808, 205024556, 283942904, 312702472, 490941273, 410782115, 648060278, 59518409, 184477717, 343581929, 145437567, 118755439, 348828719, 133923923, 296511805, 311845595, 121795063, 43665406, 31028524, 450855225, 201459959, 148798172, 179911696, 911878274, 494846126, 467653429, 61033183, 435007062, 922335224, 944124300, 933420995, 638621630, 190467704, 440067098, 67014396, 822501122, 217100293, 22886776, 51449997, 77168416, 36928571, 621675970, 793063713, 383806040, 734722339, 240359901, 105094678, 887673890, 359152099, 485774754, 830948231, 453740554, 96039159, 15421347, 488541389, 878121020, 865339534, 795269032, 941380474, 269599069, 754036091, 783580490, 267572026, 45262742, 314672334, 238673555, 34469936, 101586818, 913129339, 46659111, 161126000, 860781711, 708370585, 728061705, 171255329, 660227523, 395975012, 100204631, 512053969, 124083454, 56968719, 488532249, 931526462, 9460204, 876837328, 972185982, 474213098, 580702647, 349191092, 929359640, 891883427, 241880107, 885393156, 888582829, 810325765, 951326728, 725544159, 601511225, 39127077, 478787157, 354522390, 338171952, 59762233, 548986882, 25756840, 689470342, 106278782, 668578417, 955991993, 677758075, 826702837, 175385369, 354333099, 97220340, 540177591, 351396068, 126664204, 481961029, 803676497, 866229096, 713752037, 979812295, 800636869, 171325181, 834230087, 777319524, 266215167, 862853646, 817138709, 492359598, 833271695, 56515778, 465887450, 237973766, 803513026, 59234224, 703147716, 201153371, 645446019, 71340336, 514130704, 313525178, 640280555, 947711346, 298382423, 539067616, 23399066, 864552017, 444372695, 416739177, 191174972, 235197070, 232739941, 92467200, 111048550, 229690607, 381918190, 863377025, 230656396, 434064737, 324085900, 893192508, 975789426, 907754290, 695502320, 346980197, 71047952, 687978688, 598832346, 112364311, 868849264, 8264095, 894164766, 136660456, 192265349, 233810486, 905247839, 371769656, 302679269, 534692918, 512293778, 652564601, 247242356, 814398925, 689450144, 559789574, 257512711, 836585072, 909868195, 71186725, 872852852, 370069485, 438171261, 415936642, 380849687, 84916280, 258776352, 392741467, 234083569, 52502879, 947592083, 234391407, 724347429, 815422938, 720167459, 429627499, 702333057, 187060018, 1663318, 38098215, 366572699, 4252497, 43230237, 721120573, 623250390, 337053242, 939461155, 16837919, 113020385, 951045325, 290971232, 326210583, 888496268, 502978685, 860102781, 827990888, 141800634, 329386046, 925916803, 10180437, 889870055, 969896677, 652569609, 331411812, 258722544, 842895480, 387691679, 468663955, 12558136, 49667855, 543983949, 693324142, 245564550, 532800894, 925301115, 252246809, 379399685, 691557852, 831321000, 483439618, 239023125, 112736916, 688770558, 229910976, 583671257, 850495481, 626394735, 851473551, 32431696, 204625490, 812270161, 64030526, 64721913, 947444987, 909632582, 258722681, 845198039, 432095146, 580908315, 658369521, 26285034, 538418803, 501712141, 255155665, 669397174, 38960432, 411425445, 723089353, 352797498, 265199519, 179748308, 313299805, 147403838, 806133784, 216178765, 921656278, 270497113, 815076070, 185324277, 893835389, 43272158, 71181751, 203297678, 177591769, 930075900, 45163365, 791926742, 602087266, 337734998, 512832365, 321683144, 105240287, 832935637, 850839913, 765790996, 779773301, 704655913, 572595164, 732699141, 803230889, 819346381, 89480903, 459962399, 439889371, 581945423, 909174501, 942668480, 87774372, 50088362, 607467666, 364783202, 638442407, 473234037, 158009949, 383425151, 421066788, 910889051, 48844341, 26559542, 857107465, 877838757, 623334009, 949459197, 757226769, 515193039, 988320347, 61546131, 904663019, 487139573, 147141047, 38877810, 22797491, 905342071, 162548302, 143091308, 546907494, 644242498, 171115712, 461168251, 586312534, 499786502, 896174275, 343718445, 144894685, 145998744, 813039043, 308749840, 838069728, 92677823, 710527086, 819657082, 661960247, 600579869, 565695961, 534889836, 319905888, 152186106, 138859965, 652191113, 412480481, 275210229, 571521743, 19065217, 39995872, 634196349, 769676160, 298710170, 752544151, 123843605, 527815292, 884150534, 124166276, 655979495, 659307345, 110412542, 863679542, 813070899, 637132210, 720568106, 720850687, 27738613, 198917292, 718371912, 316640128, 99132608, 467411162, 284219008, 865236528, 418552259, 244368019, 104562269, 529410415, 569073962, 326894174, 847213392, 298899734, 436557583, 64654260, 17422438, 761139474, 58537986, 886377532, 46099663, 348418052, 821778242, 952558015, 944948298, 104474921, 61352579, 360644693, 156503417, 478440522, 971078886, 47119802, 668530118, 144230700, 369316015, 866524275, 586879618, 86327633, 2561037, 93675919, 305657382, 402735650, 57097853, 304382318, 240550050, 5961627, 412817227, 492449310, 193577632, 21535819, 175257237, 141280800, 975449174, 484106220, 705184704, 870050913, 729542368, 434438253, 952296949, 59200752, 702110303, 92705903, 620941155, 534951312, 205649373, 47823988, 411860916, 599599509, 121170970, 705995434, 818109563, 777117247, 807007853, 21754566, 142727928, 675009353, 519067348, 886343722, 832360062, 560064054, 368709355, 53302821, 359831748, 378238684, 505966868, 897392003, 482720118, 676783438, 625847954, 44638450, 559614925, 262649193, 266092166, 943059486, 216961273, 40882705, 68339542, 264888405, 38801182, 89415764, 719676295, 764568739, 357631303, 50065215, 218436037, 997899714, 646188706, 668778863, 236942043, 850235163, 546197403, 594644943, 601642441, 451495811, 23349204, 26521383, 8747730, 432683623, 734023019, 578811965, 784753423, 653704134, 72020664, 63501518, 118124114, 475567679, 79330466, 305754431, 679333124, 528747616, 166829404, 81128624, 24151370, 623623463, 164840212, 215538454, 897367536, 71503249, 104725848, 776693952, 489644798, 95763260, 820837795, 178850815, 261520483, 623216019, 906863492, 756245863, 61491426, 546762575, 356072512, 621268642, 389552958, 331903981, 295177408, 152450264, 76574755, 442181310, 93353481, 328892857, 872318799, 191196724, 807804356, 376194958, 516802338, 473026298, 961507870, 248327415, 78137784, 942205949, 903950443, 395776623, 853826580, 570579384, 6201611, 589734530, 31214805, 434196345, 181516487, 113796847, 761635208, 800404736, 357811722, 580378632, 345921928, 464590045, 907324401, 119830260, 795002581, 758105811, 463887826, 197052972, 242495308, 487658128, 272560344, 132061135, 993867172, 590732016, 409071409, 960995594, 21417849, 132997672, 347353933, 909977963, 414068785, 407053215, 253463741, 505022986, 858931336, 466867596, 531418412, 164762611, 58782094, 901154816, 654313868, 582401767, 196034943, 519372503, 720116513, 573378077, 6216050, 39432225, 312442299, 413180956, 163191672, 425814085, 241814791, 935110791, 914714169, 558588088, 538973979, 242620585, 445705020, 541310404, 63231336, 517637465, 476620258, 442672896, 120009864, 311618293, 449013996, 320695214, 887991375, 252671553, 75621152, 447361218, 459742779, 250724747, 567907415, 402596637, 513684940, 618525640, 739580000, 278689742, 69638265, 824710818, 55260388, 841384190, 757244413, 18757169, 364621852, 428621673, 977284651, 61175679, 120927196, 696831688, 67348056, 194895223, 691451286, 187749885, 651818330, 589567541, 165092907, 960594603, 78918122, 817939764, 70789101, 839458647, 961402986, 426004252, 935962844, 409804833, 609772302, 651116230, 881296145, 542574234, 622564254, 690067372, 196122335, 988169847, 325071209, 273411695, 762836932, 315922112, 916339578, 107033387, 904796279, 579356746, 557974524, 964222066, 561641578, 112351459, 91319209, 498621705, 646783919, 728084097, 547597673, 506662716, 500586035, 301539877, 66789466, 982564837, 965453676, 786474378, 513023761, 243508422, 689701019, 481278405, 422738233, 878556333, 591710537, 29709749, 554018848, 53168591, 837268941, 311731174, 553226385, 264639763, 361863804, 171265524, 831574888, 455567940, 951166025, 379113907, 183454300, 677386655, 819676416, 986906785, 926129714, 293608320, 550592012, 292910761, 918641203, 342760538, 18199490, 374624065, 32091098, 922645845, 722280506, 790891498, 382610534, 969205820, 778754245, 757250897, 920712335, 438032641, 440655371, 571205541, 792604075, 248604762, 90036450, 414127662, 42093885, 742783910, 439713937, 573888410, 786426771, 505871490, 294373957, 888256258, 409592840, 341773245, 457151568, 797398057, 216681650, 783709885, 87808722, 65882321, 768564351, 146910552, 666937061, 139525465, 99831378, 119715248, 9479544, 994863286, 152550838, 619438326, 46708073, 629525265, 926683733, 15071065, 482276265, 806880655, 676916358, 712350747, 50651382, 687231640, 928098492, 23121814, 61271438, 582865062, 540183067, 88926131, 80349052, 245260157, 859318684, 534574491, 314869767, 616467761, 512545999, 596675654, 372063866, 952499445, 108045955, 743157479, 482858601, 63804994, 776194305, 682012257, 105274291, 965967356, 829959550, 223869585, 977744129, 400709259, 211799021, 325742868, 617544851, 80823384, 981928562, 654492917, 651216085, 412075483, 910859784, 556953872, 635488009, 210790732, 204793752, 699787370, 351371549, 69078440, 798645209, 57233913, 650680513, 651467, 4766212, 441808723, 273734713, 749349517, 473226211, 26478367, 492799240, 779883848, 60630626, 111682504, 940115828, 489530217, 317484040, 250376063, 150026368, 140343976, 617138804, 698842396, 856084129, 65521203, 703231557, 255763989, 510585476, 858420298, 674807940, 635907773, 823313339, 983129530, 511809270, 99373233, 9606821, 193545600, 276152573, 584133244, 379681471, 925546438, 80423176, 905105069, 474222982, 746823035, 605811108, 647321729, 384143601, 965659125, 298993496, 864931870, 593132547, 159628055, 661645282, 601930408, 996389886, 40313274, 880825891, 81466197, 255289840, 776992752, 69125457, 2902772, 542248770, 447458100, 88038553, 633684644, 759384813, 278216548, 706601295, 56375733, 259634782, 787988948, 198597987, 646780071, 17915830, 49601386, 12796622, 910418410, 374210573, 170476926, 462510184, 665343995, 282152614, 288069500, 948924740, 10037489, 196353157, 218122838, 235952837, 404519097, 612215455, 910999408, 756130793, 274993583, 432341137, 420311758, 898980301, 259957193, 118804753, 384670539, 231971503, 855210194, 202659765, 986584791, 809343850, 480666852, 881785197, 172136610, 232510339, 174008611, 837481510, 736894710, 244177299, 839593454, 79620588, 886867591, 692586688, 943098476, 79287625, 147252235, 760130879, 932445928, 430539737, 1931594, 838002809, 908432415, 207847313, 481379569, 768496512, 947202704, 132549495, 611799104, 148817670, 153109513, 626175885, 468228895, 935934235, 721951948, 563784486, 828005638, 596725306, 413586452, 890417072, 219171739, 684962768, 656893856, 994587143, 13404153, 945300183, 369133753, 743709066, 163446722, 210450719, 932646202, 501577561, 140753252, 53389595, 256715875, 122042880, 120779853, 367921534, 844780803, 9544282, 935431205, 64482748, 429787548, 97309306, 242450575, 883314244, 101025775, 73614226, 283715710, 996241630, 50563398, 1463130, 761484371, 58265855, 21681953, 483847728, 301171885, 176915216, 296667864, 432740492, 689820302, 338584139, 899443270, 598626235, 943224028, 41956442, 787284478, 243472579, 880266296, 413771267, 494614061, 862304268, 528182320, 255834120, 541793546, 593464342, 441139326, 908081216, 747696661, 610962830, 125946081, 942864581, 443181654, 80770982, 101208148, 991273590, 157093704, 16480965, 763166870, 773244206, 137317176, 492340154, 299454965, 30906765, 906440428, 88260156, 270220393, 813715393, 731724633, 250039040, 928131748, 582055406, 817196557, 464610934, 258405824, 607728312, 450493230, 205355866, 409819133, 850112402, 630436923, 69050563, 891642961, 702356761, 939958215, 780990751, 484480171, 193223151, 506224593, 934008784, 573151696, 496397877, 778128722, 981504071, 110007268, 494690365, 144745596, 226217077, 777336527, 197479519, 176041218, 285263938, 247505862, 948176973, 681724471, 710905930, 389932180, 617542263, 37326868, 80424130, 714117525, 680118170, 838113856, 627315697, 90674934, 846183524, 169777434, 236544953, 618794474, 962905744, 913054194, 931180743, 286906843, 942522786, 141084030, 170324500, 841148627, 300125788, 922515760, 683425558, 590809150, 557978900, 37769498, 722750530, 100650278, 205087088, 187434581, 1976365, 442985359, 76608211, 649971233, 964684389, 741969651, 993869875, 636161337, 435491124, 675052092, 444403143, 135500135, 18103125, 109522579, 352499774, 703803192, 273298846, 659162367, 821250943, 680178310, 494381767, 253106304, 585525199, 151949039, 242420768, 382347995, 644658719, 517069696, 317039841, 581679480, 941459216, 445532216, 931960870, 513599450, 329178857, 384153505, 925094231, 70114715, 242471380, 440005301, 28392217, 446621485, 911952130, 588660271, 156012968, 32420189, 572753832, 44927148, 762289848, 65520981, 137973912, 438178802, 749699651, 915477408, 855949148, 737357761, 791245937, 44699513, 231395697, 767573340, 670857851, 818755007, 887676320, 399993109, 853346431, 90649729, 422563089, 289416194, 167512103, 24853904, 107737010, 200191227, 300055918, 748210670, 659977505, 281868358, 805546202, 78106326, 413491343, 84898687, 756069379, 390292132, 17783164, 967367571, 741052938, 619060013, 776347354, 106823153, 666360735, 190632618, 709787980, 134920775, 18217840, 683032515, 427386390, 543236093, 216031654, 242140279, 170158088, 546250859, 138574866, 948478092, 93159141, 3082702, 64343564, 30984285, 500308930, 293708505, 86917660, 536231660, 604126808, 49557618, 484209268, 289628793, 238674780, 55058511, 388899676, 89611642, 716830547, 387743759, 343972515, 913060459, 36476598, 467816700, 657645233, 92583569, 712357264, 367204023, 877496730, 110315739, 236711521, 270819203, 933475406, 198602238, 718226628, 229357009, 70103898, 415175130, 467019385, 935052488, 141837070, 148787320, 997522132, 97124042, 862159330, 32671579, 941371777, 123428590, 788087706, 858423693, 524846283, 21635083, 696103638, 70418657, 848835858, 443376963, 861340629, 364687176, 379038494, 63471656, 261728411, 822894621, 595208467, 689877143, 500932248, 32395896, 957439959, 391402520, 352721457, 927640657, 918223557, 765835157, 521987228, 361621579, 188135821, 695793741, 949925650, 799946330, 95833021, 52848697, 317304268, 523915353, 555363749, 827578159, 647515272, 489537155, 434091006, 558567561, 986955268, 386478426, 197852185, 996987739, 705515479, 134419044, 614033020, 39538236, 946685529, 237345280, 184988481, 338057889, 644694108, 111852619, 297249917, 832392097, 305497721, 659775448, 387885075, 217081811, 66764871, 569196672, 596302566, 544024791, 586777058, 510085360, 42905274, 347413304, 114847782, 244830577, 81818565, 528066453, 455941098, 780381590, 190750901, 550286714, 604218216, 438368227, 785881979, 86970581, 864148416, 310523051, 575655947, 635671494, 147139480, 658036172, 73160754, 252146394, 632187005, 210886257, 17303849, 708476376, 358607395, 275374283, 181293674, 516462403, 54706047, 321531013, 902879639, 578642971, 446459981, 138016627, 156089807, 116831840, 231155031, 224688594, 64947932, 451179026, 994111003, 600853761, 81052933, 544991311, 444188100, 609218306, 723018624, 311538842, 261164686, 731281712, 602821803, 945680122, 312317585, 464596405, 14216921, 366085008, 43059379, 789972392, 322086590, 296022621, 680064695, 732338109, 970795584, 373608960, 3606892, 491491728, 279366134, 700340374, 55775189, 903710009, 295264610, 825075700, 538359799, 657515560, 706148036, 235407730, 625818914, 556563170, 865915505, 738195394, 836958239, 739235023, 130133666, 811150394, 571459380, 763908854, 4362343, 303454803, 38696043, 262806816, 413273211, 920742879, 158407071, 615403664, 601115474, 977674608, 25248390, 295412271, 804825411, 848673871, 868345101, 124731142, 998221278, 755747560, 276447493, 245886390, 646998480, 39243530, 288529081, 290189441, 278572550, 454497390, 138301351, 853500203, 734633508, 894860931, 892665954, 508909514, 607814375, 103975493, 50379349, 410140303, 598544229, 919454255, 122823620, 3270082, 273176999, 758763485, 779996509, 161145475, 188098036, 60741246, 616367775, 625059875, 38801648, 890226404, 516603379, 276606032, 762967716, 366525153, 998125453, 145216785, 117082503, 503585847, 327256280, 283656571, 795271035, 182066317, 971876491, 360543733, 252647275, 667580806, 576034514, 348774700, 19005168, 592278820, 636402473, 193296582, 740379410, 829471730, 260508364, 792401162, 133213265, 675858190, 107590347, 882709833, 887129755, 10831164, 650747000, 763593407, 352116977, 712584954, 692001137, 839161054, 47703307, 176553927, 666934582, 97860912, 923358029, 954538759, 23058001, 427239856, 582427871, 427743449, 101875765, 681515696, 704013221, 508288955, 122518919, 886137807, 312008882, 571192378, 778394956, 13647968, 748131594, 123925751, 553938045, 695112570, 445924310, 79433787, 894786831, 1772323, 308618759, 575453586, 175052392, 52955954, 972489020, 124921823, 469556042, 618973747, 680979761, 286488264, 142895052, 543400196, 472122059, 3369948, 804141214, 86793127, 383667754, 203528115, 903062781, 154721849, 954903273, 706993858, 211731133, 977727830, 126771966, 352654738, 13315846, 461124434, 997363862, 230058730, 126510510, 46309618, 729648090, 856802838, 52940062, 705392176, 416570592, 298229102, 902663794, 245903350, 932045200, 930933760, 430830856, 806822755, 851274705, 630889199, 20980932, 25163172, 449110501, 588149680, 164444619, 9257844, 977761524, 693067024, 426171040, 798706535, 87939995, 124703985, 541793579, 386997551, 332851472, 39789469, 874191266, 596978535, 167617539, 442411687, 24837495, 624929525, 640987776, 303577880, 605262466, 16230223, 50934792, 362557638, 888093905, 975893263, 150954033, 906245524, 314497344, 592583919, 321750425, 295569829, 512440492, 177924574, 874057172, 136239255, 555591083, 560434825, 364828033, 598938446, 102608433, 903543468, 998198739, 583956009, 548376473, 711052434, 704741261, 214060422, 471382407, 249919244, 707698954, 531882792, 172641261, 331266530, 318956686, 378817268, 285788499, 473868001, 75624662, 860858857, 650458338, 207018467, 435866729, 545394386, 983240106, 429797877, 625413878, 191574059, 707222760, 118424822, 234599741, 930849673, 372085716, 172248748, 176751480, 692240559, 568159314, 134274414, 330720257, 520659541, 522022640, 163812485, 915378519, 193921725, 509739576, 673764527, 72113236, 619359122, 508505023, 251985079, 275470869, 11635998, 731163665, 559268099, 875995552, 856842279, 715824949, 666527349, 50451891, 481870050, 629097513, 179906810, 829759272, 5280886, 709021475, 137173122, 218708223, 130078875, 97299479, 77288186, 547914245, 384837379, 888567736, 349636292, 614880030, 390333424, 564294161, 804178775, 718080854, 719795616, 829534561, 523530403, 734981462, 507494290, 798969793, 863044838, 90040428, 126480839, 902134190, 727762088, 223538282, 59006971, 385695261, 274604981, 136536842, 55147076, 729927984, 473035424, 114888552, 137073389, 335474270, 171482515, 976553909, 871518189, 413224914, 109015200, 414915509, 605557954, 687529745, 850403355, 18495278, 50965687, 527304834, 894817516, 162990049, 125082196, 455934915, 469442487, 857938509, 167314805, 796812290, 109113916, 719530252, 664529107, 825736949, 914553507, 5825501, 272431192, 108887118, 202703560, 722647356, 159583438, 59251010, 985270018, 186790509, 914476496, 858985271, 580374563, 277534245, 976553009, 856391889, 736054807, 12829460, 876369520, 699671514, 551663404, 119926929, 65213395, 263343304, 47113861, 568679731, 143504698, 259323705, 209190172, 221469243, 437385428, 93343293, 950641719, 950016131, 380198272, 228507679, 620778695, 744948317, 309680387, 90882559, 602296096, 700057161, 590781592, 449316663, 905630767, 365189611, 233528951, 468456388, 464441792, 563119877, 395340410, 171867052, 204037749, 878546831, 432010423, 156968854, 65610662, 852263901, 76437195, 277694037, 514693506, 182603804, 60980843, 348307260, 752675676, 541405702, 310399753, 443848686, 199654502, 223758500, 258222181, 668724058, 463318055, 3824941, 654252555, 906419245, 86742544, 326497851, 421642250, 638239228, 205888231, 767343100, 96181465, 259674642, 664937390, 97814742, 147378839, 740480660, 383696833, 692258868, 875878677, 685502732, 142134216, 286426357, 456929172, 50710, 645261548, 911398464, 20614044, 153843850, 83275962, 607239137, 818863593, 210692506, 55898086, 467251172, 890234372, 443500133, 783975172, 458541459, 180470908, 927641192, 134236724, 258790918, 637552229, 189892851, 368447315, 298668904, 851965067, 348901451, 356330647, 310271224, 638166852, 136948446, 383040916, 760185153, 844629046, 606448030, 407630126, 359672330, 639362583, 906246540, 124551834, 132075369, 85614363, 106555451, 23587006, 728292303, 899432268, 413715621, 559371739, 824894454, 639641924, 158679786, 903957375, 157777678, 774613748, 680373100, 473250003, 780855580, 360144821, 138067879, 662977102, 510992678, 259813371, 642050624, 632489971, 214889947, 735328622, 692740047, 373119542, 160871732, 882266729, 29815415, 182463663, 60136125, 390538785, 868312841, 228032253, 427249923, 397118871, 145173668, 978372240, 12931179, 231455684, 775774849, 867644784, 884900136, 985308855, 632502546, 219216550, 83596176, 546624894, 189551592, 75358243, 323616949, 601467639, 454060822, 36332494, 754870910, 929481541, 793189887, 356928811, 980700406, 694732917, 507547280, 542089076, 265469758, 72182818, 995845218, 476012786, 970309227, 143846518, 147798660, 206477619, 83252628, 653538108, 783610398, 415730713, 421789700, 968947731, 736019716, 777560092, 14474249, 396029410, 807450395, 662601950, 293758886, 140692549, 240175696, 511149959, 755751491, 342515810, 407044710, 110520206, 87231234, 949976093, 854763253, 133373319, 779928612, 812979174, 450015204, 761107472, 520680372, 872129257, 300531624, 946445402, 496498085, 669346000, 971857592, 42908240, 397262866, 270330339, 514094168, 846948273, 930990573, 385686947, 927850161, 144389991, 106057627, 99109979, 441590628, 903179342, 320783998, 25678994, 528596267, 770590408, 986595846, 788123813, 110768973, 618785840, 817794106, 563177320, 6279842, 318605791, 130797366, 81054412, 776870286, 158323042, 203128261, 625167544, 346405815, 214365688, 514042197, 973471676, 608035686, 174077107, 841210135, 333890744, 119943375, 194137670, 844159897, 518416797, 482929878, 54736111, 265290170, 555836018, 382090076, 811802802, 6083823, 112060330, 640765047, 500633802, 311381268, 114807184, 562499991, 714334643, 388758171, 6304401, 169842413, 535668428, 727821172, 423584492, 276267239, 363841059, 190735604, 293190035, 317432027, 523677219, 848012905, 496907774, 112538082, 80408323, 448449276, 212359340, 5606066, 879354441, 120609811, 657509287, 955222794, 634732364, 395567099, 479840359, 875819228, 40848458, 138245144, 56312801, 994915236, 232695910, 145416761, 976090419, 524092700, 595572553, 159598182, 952548349, 136996905, 990469907, 327473983, 2128667, 855241426, 934597411, 83292519, 531007567, 849625284, 826357863, 612836870, 410681656, 107129512, 727390576, 421987039, 345162079, 578709784, 214881003, 230501745, 129812674, 504183722, 638323170, 616701425, 937748131, 143330962, 279804978, 840561963, 970460753, 188555284, 155773794, 307590065, 673084126, 728536933, 361456315, 912532489, 398314327, 762366190, 201117328, 832649896, 343358220, 326022629, 24520684, 388232920, 768345432, 555484791, 714447406, 929460843, 445318601, 282195790, 13728532, 393160604, 43089609, 505069424, 846436224, 914917618, 830471784, 36030413, 558719993, 253912598, 459027997, 122285555, 904451284, 223476722, 817346629, 839387391, 556781972, 41332003, 468229949, 160670235, 790673944, 21147750, 888411073, 864084898, 390459672, 538660650, 625972445, 989475040, 141118559, 396148334, 865743838, 354976841, 179173899, 396625977, 96533729, 885208396, 723783734, 285840730, 997209349, 135147455, 178556237, 960020400, 18222889, 122396127, 408329819, 234510699, 788825848, 379474405, 592871823, 72607081, 536498871, 800174791, 788093401, 599634489, 63584899, 810498443, 558558580, 43033023, 347007100, 730228095, 867528638, 287339383, 415266556, 63153942, 571381576, 810762095, 487769028, 781951575, 453179963, 618625879, 69791804, 50735722, 750228951, 14466498, 58736931, 935078853, 584953625, 135439409, 144964890, 616924041, 591309371, 729763728, 652847057, 699513054, 35909831, 93624810, 594152066, 907793290, 557996742, 983134923, 809470843, 467554556, 546758319, 284541920, 997451218, 698251022, 299774477, 312999077, 388035636, 600076891, 909100725, 57220317, 215151119, 475374063, 972710001, 691465843, 77904315, 520281182, 605393868, 77219990, 756249142, 471106648, 910205025, 289837594, 600509540, 383676458, 704321312, 391407098, 429663903, 166691438, 264322778, 122242781, 540053735, 62726854, 983248148, 357938349, 561114974, 851652619, 540038856, 960139148, 659515456, 106145403, 12834720, 757752918, 768244694, 9864872, 28620041, 566649315, 378041338, 484139940, 917411675, 5436265, 172992681, 588110107, 646824855, 416095449, 902435289, 345882040, 1213851, 73840934, 592008350, 592601899, 978445354, 94274530, 776577871, 331650009, 321637298, 334706565, 946545040, 816608882, 177491797, 249846496, 839528387, 986039519, 234891934, 753791552, 968580811, 11646217, 109935820, 648368898, 597022386, 904621296, 578879690, 130028920, 50684372, 448715992, 400087858, 505330649, 941877505, 826243076, 831095408, 779860746, 819838959, 571283339, 952671414, 57866713, 341710456, 549340492, 526429169, 855396321, 390434029, 107678749, 575503669, 16797373, 786068832, 932441658, 358773847, 570944331, 904436321, 971993581, 388013138, 576458074, 25096679, 331562650, 878232, 314016851, 106872656, 350874009, 149374601, 130535664, 332101261, 108873652, 976380498, 104483159, 199808645, 666956254, 462102216, 251076760, 834717543, 734562997, 709782554, 43725993, 463357077, 866689117, 62411818, 983405390, 60242418, 822500167, 201049608, 841963503, 903823416, 53812412, 334593097, 393993433, 948523308, 853104453, 171209130, 31244577, 580069280, 796115227, 130994310, 450629995, 710986643, 746475571, 208434601, 407489328, 140763991, 86396321, 364021675, 78865069, 73761640, 52292670, 562093067, 317613916, 640223417, 134876627, 714695913, 18172120, 269121544, 318208004, 680620776, 340973241, 250891291, 12507354, 343658428, 76651191, 372336093, 878346271, 563187219, 527157404, 209940084, 147359767, 626958978, 744771064, 478072863, 234285014, 83683925, 459895846, 468816747, 78544564, 189022821, 778238634, 681311408, 211007030, 692630591, 326471128, 179530211, 149732242, 846440657, 989423049, 60284400, 173586572, 979701556, 879908721, 846459183, 153305884, 779099635, 912748264, 877361105, 978350011, 639328376, 331329491, 22637144, 150852267, 136326587, 461853516, 11638085, 180282718, 59699156, 74808899, 473705507, 846576720, 335771665, 520327917, 597890435, 668556732, 798553620, 665381237, 908078908, 708906105, 345633179, 113574318, 878084090, 244657024, 312396941, 5354119, 378322015, 552005916, 434075172, 499466945, 27368492, 420744586, 938090978, 463109550, 1470122, 878998915, 587735270, 434885268, 229848535, 534225370, 96665483, 159135649, 768690806, 917734668, 139012322, 710866496, 81670011, 178803022, 605747179, 365845604, 521385067, 185541309, 39503497, 155805734, 637384223, 661183303, 72878874, 809556528, 907662351, 150283547, 374805557, 787459848, 43432522]));