New Year and Entity Enumeration (Codeforces 908E)
Tags: Math, bitmasks

You are given an integer m.Let M = 2m - 1.You are also given a set of n integers denoted as the set T. The integers will be provided in base 2 as n binary strings of length m.A set of integers S is called "good" if the following hold.   If , then .  If , then     All elements of S are less than or equal to M. Here,  and  refer to the bitwise XOR and bitwise AND operators, respectively.Count the number of good sets S, modulo 109 + 7.

Input: The first line will contain two integers m and n (1 ≤ m ≤ 1 000, 1 ≤ n ≤ min(2m, 50)).The next n lines will contain the elements of T. Each line will contain exactly m zeros and ones. Elements of T will be distinct.

Output: Print a single integer, the number of good sets modulo 109 + 7. 

Note: An example of a valid set S is {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}.

Sample Inputs:
5 3
11010
00101
11000

30 2
010101010101010010101010101010
110110110110110011011011011011

Sample Outputs:
4

860616440

Solution (Python):
import sys
f = sys.stdin
(n, m) = list(map(int, f.readline().split()))
s = [f.readline().strip() for _ in range(m)]
s = [list(x) for x in s]
d = {}
for k in zip(*s):
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
dv = d.values()
got = [1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 382958538, 480142077, 864869230, 76801385, 742164233, 157873304, 812832668, 706900318, 546020311, 173093227, 759867260, 200033042, 40680577, 159122123, 665114805, 272358185, 365885605, 744733441, 692873095, 463056339, 828412002, 817756178, 366396447, 683685664, 681586780, 840750853, 683889724, 216039853, 954226396, 858087702, 540284076, 514254014, 647209774, 900185117, 348985796, 609459762, 781824096, 756600466, 654591160, 171792186, 748630189, 848074470, 75742990, 352494923, 278101098, 462072300, 334907097, 10474572, 495625635, 586051441, 159996073, 479379757, 707597945, 561063550, 974840072, 209152841, 906106015, 467465396, 82034048, 392794164, 700950185, 344807921, 475335490, 496881113, 358229039, 519104519, 784488542, 665151655, 307919717, 591199688, 692769253, 335414677, 884560880, 847374378, 791103220, 200350027, 485480275, 557337842, 434181960, 73976309, 792463021, 462067202, 677783523, 295755371, 435431099, 193120002, 513369106, 134597056, 143018012, 353529690, 591382993, 163160926, 287984994, 842145354, 703798750, 386436223, 618375990, 636477101, 536261496, 574800957, 34046224, 167415054, 961776342, 807141069, 218578541, 513967253, 460200768, 230725907, 239843627, 792763805, 368353031, 740982762, 126993201, 967654419, 588554507, 728057622, 239984996, 818342358, 882367644, 216705655, 267152940, 867213913, 330735015, 934583772, 59261085, 443816525, 568733052, 754405433, 244324432, 153903806, 292097031, 557968620, 311976469, 242994387, 773037141, 549999484, 243701468, 941251494, 7149216, 932327662, 456857477, 739044033, 645452229, 69273749, 304951367, 503353209, 243194926, 688663125, 239795364, 522687881, 121506491, 835250259, 159173149, 545801717, 19848500, 322507013, 106069527, 807985703, 290163328, 971751677, 238407093, 981758956, 301257197, 728003485, 817681690, 318332431, 864806329, 87958605, 929106232, 617996713, 519300437, 307911059, 137306007, 887695462, 633135243, 442387331, 730250437, 27723819, 80605394, 760335262, 822289356, 415861662, 558003999, 645049413, 347692428, 380668983, 897875109, 278111491, 106909073, 951914124, 374756177, 635211535, 286442394, 774619548, 756991257, 929298287, 923425488, 182439740, 266683608, 415378498, 728411148, 808161291, 436338820, 692451577, 228029692, 235546564, 895805974, 758052804, 700926159, 226442121, 579900323, 96916377, 243044550, 858703179, 30279679, 343764928, 100627558, 840734795, 291199760, 989808717, 370270411, 158336199, 393391701, 881731480, 507200370, 588418523, 340981140, 295449954, 683858381, 903859151, 866470542, 4959332, 237784075, 861373023, 950693473, 955867890, 400039807, 939877954, 124824910, 954530940, 204884446, 42218442, 234856311, 189836713, 179563650, 683193288, 929322036, 73574908, 943547254, 103031032, 141180580, 540183111, 680050153, 382916846, 948921599, 252835397, 199109508, 551172546, 700090782, 44999714, 970123610, 145637563, 33948107, 267648423, 504777414, 584919509, 212459491, 242880452, 351366578, 345323768, 285497541, 692868556, 706562675, 675626979, 620872182, 136458675, 971105139, 182064384, 948539342, 186406165, 706529481, 790490927, 888369436, 784409511, 835815713, 447895018, 17015606, 342727699, 321837918, 394134115, 563672582, 70390332, 61116103, 949269501, 833942074, 581389345, 570974405, 768179852, 765734098, 928340756, 541194960, 126833304, 427218334, 75800034, 100445725, 242810216, 330081440, 986329793, 298082322, 643160582, 505669854, 255287400, 403977567, 659185446, 596703087, 289443930, 478095124, 920175726, 205886838, 729278433, 535998256, 658801091, 606948240, 432632296, 552723022, 17794080, 234033713, 189986528, 444922724, 263196004, 846019724, 684703320, 895782046, 505050988, 44287113, 505335732, 436498414, 12098144, 714227851, 643983136, 647148160, 579243434, 951209063, 511291462, 426622734, 830870687, 949900312, 599926584, 633837711, 176405710, 913717356, 753535741, 874916804, 956692925, 220742732, 649500982, 584759931, 109573948, 937203173, 96881033, 305784835, 559854872, 894253854, 746366726, 951492991, 532579856, 822308583, 572042503, 397665465, 600979983, 914199453, 628402767, 594763006, 9791558, 451332658, 516069180, 651367831, 962708649, 687016963, 539878802, 107278296, 926059014, 371504543, 556987417, 447666745, 565595310, 778161513, 995461128, 121460302, 599892490, 242414970, 900391574, 362620950, 292857964, 495260535, 355054738, 176340034, 370047225, 509682533, 459314034, 40869728, 534741938, 788604648, 945028000, 701904601, 154924404, 695162652, 220536827, 615701976, 167761915, 833779942, 52430883, 368585637, 936409860, 654822736, 613850019, 941559844, 357840989, 218223326, 721900618, 171013438, 597980462, 193395922, 949112044, 859322955, 354602094, 807705992, 347609311, 451694117, 623122523, 252980054, 491785682, 13877214, 918727309, 750110421, 114981703, 174636266, 363160184, 781715298, 30575457, 862940854, 642129450, 34525888, 798422280, 792396821, 168367459, 344551406, 799847612, 626838494, 671596530, 167280197, 959000039, 614621296, 273560655, 8705247, 284372524, 940371542, 906010703, 582585495, 929449942, 308961449, 768816240, 674729787, 279648144, 286568146, 938661138, 536038536, 456529723, 18843013, 501518651, 457224675, 520694423, 938573228, 179014658, 169719825, 459657583, 302109678, 560375405, 556039265, 348713003, 957546568, 687116649, 3656313, 562760316, 716689588, 324677598, 570275686, 60738163, 996201577, 305457565, 38935942, 538451492, 228282207, 77975017, 389525459, 25000235, 152169430, 62331625, 618611219, 462328092, 106666757, 661839198, 177836427, 313546124, 392585017, 950280707, 551167559, 389204003, 77447456, 158414991, 766574847, 941433736, 363591676, 805565034, 312418363, 999641612, 122925536, 768845786, 608121932, 373163730, 783033644, 74564718, 894150080, 796617981, 274365270, 802488053, 947861187, 401960309, 143529635, 769621671, 249500752, 619408647, 849453216, 354838551, 69741157, 944781258, 135254314, 7413076, 416298064, 871313316, 343673168, 375656287, 868866230, 179060630, 399560227, 852555486, 987661859, 165863065, 12882359, 3688778, 380092596, 438366086, 720041886, 240796679, 588918084, 14802664, 17188673, 504951961, 842108931, 839289310, 256364811, 121095676, 164017670, 35340476, 875551801, 239615760, 262141182, 262741417, 456560451, 350350882, 777143297, 264469934, 807530935, 89546104, 246698645, 241166716, 125659016, 839103323, 418357064, 186866754, 179291319, 326054960, 172454707, 430532716, 558625738, 306201933, 61986384, 837357643, 575407529, 983555480, 13784333, 311989892, 153386582, 633092291, 722816631, 633510090, 551352594, 323601313, 248995449, 672011813, 612805937, 202743586, 215183002, 32688571, 38454892, 245790100, 451190956, 823199664, 12164578, 67389319, 584760532, 968838901, 307205626, 971537038, 836812364, 663878188, 468850566, 647599527, 839342879, 242347168, 169911213, 993779953, 251402771, 969281106, 416168275, 738337745, 8172262, 852101376, 879373674, 929752458, 452163141, 48347012, 500253327, 672444134, 406391337, 665852222, 499704706, 116418822, 67956495, 994761753, 808150613, 251453632, 543431315, 143101466, 381253760, 826943616, 763270983, 959511676, 323777679, 514214633, 669340157, 471626592, 557874503, 304789863, 116939617, 503636634, 660499296, 659726735, 273788323, 704107733, 718417780, 624033370, 355000823, 194537583, 760997582, 289828020, 778033293, 933152490, 910945024, 644565086, 434509630, 289427510, 502291783, 421699389, 159196930, 834667293, 313599675, 560298831, 812176354, 865521998, 126796474, 886921339, 937011401, 791993161, 583948688, 275408655, 665183437, 130342900, 699431744, 117550047, 460234251, 56770880, 306091228, 912949106, 626369877, 852501236, 241076503, 262988042, 737247015, 831044258, 475123008, 928949542, 332750699, 696284377, 689111142, 196862045, 570365577, 187156806, 451528865, 635110126, 385331290, 263486377, 200189955, 206842029, 457862597, 450522487, 818984909, 710634976, 461356455, 71985964, 781500456, 467334209, 46762760, 97663653, 870671823, 255977331, 79650379, 32876340, 636190780, 364339752, 597149326, 452604321, 748186407, 302032725, 779013981, 111971627, 175687535, 399961122, 451853028, 798326812, 902775588, 362836436, 498862780, 160000437, 629259604, 919729986, 5994845, 631476109, 371320167, 76164236, 448643023, 945220853, 111192011, 150577654, 827274836, 17668451, 938388515, 88566735, 27940328, 882026632, 712756966, 83642744, 873585716, 638987456, 405271094, 822216133, 345587303, 668558160, 314983205, 826678060, 563583341, 516998387, 77703032, 726563479, 155257773, 49705622, 891556456, 164127879, 842558039, 189099480, 956148983, 992226557, 671472701, 137476493, 871069222, 78241093, 728497057, 278888712, 332713952, 222597908, 235198692, 876216003, 167364357, 722341150, 519365334, 604855967, 834816722, 850786742, 416385106, 608404143, 311628039, 507077268, 571796589, 506398832, 305540948, 556971113, 444565912, 866477296, 411983920, 905854221, 901986568, 512703782, 684027511, 596294441, 916862272, 495347444, 802477106, 235968146, 257527513, 528476230, 969655767, 772044489, 682345813, 66418556, 603372280, 439233253, 278244332, 590581374, 353687769, 321352820, 245676729, 325255315, 91010070, 923699200, 837616604, 736177081, 528261400, 876353388, 339195128, 377206087, 769944080, 772953529, 123785293, 35984916, 461119619, 236140329, 884137913, 625494604, 791773064, 661436140, 308509072, 54134926, 279367618, 51918421, 149844467, 308119110, 948074070, 941738748, 890320056, 933243910, 430364344, 903312966, 574904506, 56353560, 861112413, 440392450, 937276559, 944662107, 599470900, 458887833, 962614595, 589151703, 997944986, 642961512, 63773929, 737273926, 110546606, 654813100, 374632916, 327432718, 307869727, 387738989, 133844439, 688886605, 989252194, 303514517, 79062408, 79381603, 941446109, 189307316, 728764788, 619946432, 359845738, 216171670, 690964059, 337106876, 762119224, 226624101, 401879891, 47069454, 41411521, 429556898, 188042667, 832342137, 770962364, 294422843, 991268380, 137519647, 903275202, 115040918, 521250780, 783585266, 98267582, 337193737, 717487549, 510794369, 206729333, 248526905, 412652544, 146948138, 103954760, 132289464, 938042429, 185735408, 640754677, 315573450, 956487685, 454822141, 783819416, 882547786, 976850791, 307258357, 929434429, 832158433, 334518103, 700273615, 734048238, 48618988, 693477108, 12561960, 598093056, 154072663, 174314067, 345548333, 479759833, 658594149, 282072153, 57970886, 905112877, 584117466, 472359245, 776860470, 324216896, 334199385, 321245477, 508188925, 521442872, 286692969, 245141864, 59342176, 896413224, 573301289, 869453643, 87399903, 60102262, 835514392, 493582549, 649986925, 576899388, 20454903, 271374500, 589229956, 505139242, 789538901, 243337905, 248443618, 39334644, 831631854, 541659849, 159802612, 524090232, 855135628, 542520502, 967119953, 597294058, 465231251]
MM = 10 ** 9 + 7
ans = 1
for v in dv:
    ans = ans * got[v - 1]
    ans = ans % MM
print(ans)
''

Solution (Python):
from collections import defaultdict

def E1():
    mod = 10 ** 9 + 7
    comb = [[1]]
    for i in range(1, 1010):
        x = [1]
        for j in range(1, i):
            x.append((comb[i - 1][j - 1] + comb[i - 1][j]) % mod)
        x.append(1)
        comb.append(x)
    dp = [1]
    for i in range(1, 1010):
        r = 0
        for k in range(i):
            r += dp[k] * comb[i - 1][k]
            r %= mod
        dp.append(r)
    (m, n) = map(int, input().split())
    ns = [0 for __ in range(m)]
    for j in range(n):
        temp = input()
        s = [int(i) for i in temp]
        for i in range(m):
            ns[i] |= s[i] << j
    dd = defaultdict(int)
    for e in ns:
        dd[e] += 1
    ans = 1
    for b in dd.values():
        ans = ans * dp[b] % mod
    print(ans)
if __name__ == '__main__':
    E1()

Solution (Python):
from collections import defaultdict
mod_v = 1000000007
temp_arr = [[1]]
for i in range(1, 1010):
    a = [1]
    for k in range(1, i):
        a.append((temp_arr[i - 1][k - 1] + temp_arr[i - 1][k]) % mod_v)
    a.append(1)
    temp_arr.append(a)
ans_arr = [1]
for i in range(1, 1010):
    res = 0
    for j in range(i):
        res += ans_arr[j] * temp_arr[i - 1][j]
        res %= mod_v
    ans_arr.append(res)
n_list = list(map(int, input().split()))
n = n_list[0]
lines = n_list[1]
new_list = [0 for __ in range(n)]
for i in range(lines):
    input1 = list(map(int, input()))
    for k in range(n):
        new_list[k] |= input1[k] << i
default_d = defaultdict(int)
for k in new_list:
    default_d[k] += 1
answer = 1
for n in default_d.values():
    answer = answer * ans_arr[n] % mod_v
print(answer)