def IsUniversalLinear(str_val, k):
    linears = {}
    formatter = "{0:0>%db}" % k
    for i in range(2**k):
        val = formatter.format(i)
        linears[val] = 0

    str_val += str_val[:k-1]
    for i in range(len(str_val) - k + 1):
        val = str_val[i:i+k]
        if val not in linears:
            return False
        if linears[val] != 0:
            return False
        linears[val]+= 1

    for count in linears.values():
        if count != 1:
            return False

    return True

if __name__ == "__main__":
    print(IsUniversalLinear("00000000111111111011111110011111101011111100011111011011111010011111001011111000011110111011110110011110101011110100011110011011110010011110001011110000011101110011101101011101100011101011011101010011101001011101000011100110011100101011100100011100011011100010011100001011100000011011011010011011001011011000011010110011010101011010100011010010011010001011010000011001100011001010011001001011001000011000101011000100011000010011000001011000000010101010010101000010100100010100010010100000010010010000010001000010", 9))