## https://yukicoder.me/problems/no/1694 from collections import deque def main(): S = input() init_state = 0 for i in range(len(S)): if S[i] == "1": init_state |= (1 << i) states = {init_state:0} queue = deque() queue.append(init_state) while len(queue) > 0: state = queue.popleft() for l in range(2, (len(S) // 2) + 1): # 0, 1の状態を計算 array = [[-1, -1] for _ in range(len(S) + 1 - l)] cnt = [0, 0] for k in range(l): if state & (1 << k) > 0: cnt[1] += 1 else: cnt[0] += 1 array[0][0] = cnt[0] array[0][1] = cnt[1] for k in range(l, len(S)): if state & (1 << k) > 0: cnt[1] += 1 else: cnt[0] += 1 if state & (1 << (k - l)) > 0: cnt[1] -= 1 else: cnt[0] -= 1 array[k - (l - 1)][0] = cnt[0] array[k - (l - 1)][1] = cnt[1] # 実際の遷移 for s_i in range(len(array)): cnt = array[s_i] if cnt[0] == -1: continue if s_i + l < len(array) : for t_i in range(s_i + l, len(array)): if cnt[0] == array[t_i][0] and cnt[1] == array[t_i][1]: s_bit = (state & ((2 **l - 1) << s_i)) t_bit = (state & ((2 **l - 1) << t_i)) new_state = state - s_bit - t_bit new_state |= (s_bit >> s_i) << t_i new_state |= (t_bit >> t_i) << s_i if new_state not in states: states[new_state] = 0 queue.append(new_state) print(len(states)) if __name__ == '__main__': main()