from itertools import product
n = 8
d = 4
s = 0
for ps in product(*([range(2)] * n)):
    x = 0
    for i, p in enumerate(ps):
        if p == 1:
            x += (i + 1)
        
    if x % d == 0:
        print([i + 1 if p else 0 for i, p in enumerate(ps)], "=>", x)

        s += 1
print(s)