def fast_zeta_transform(counts, size):
    """
    高速ゼータ変換
    ret[s]: sum of counts[t] (t ⊆ s)
    https://qiita.com/Euglenese/items/260f9ddf513f772d7e42#本題
    O(2^N * N); len(counts) == 2^N
    :param list of int counts:
    :param int size:
    """
    assert (1 << size) == len(counts)
    dp = list(counts)
    for j in range(size):
        for i in range(1 << size):
            if i & (1 << j):
                dp[i] += dp[i & ~(1 << j)]
    return dp