## 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] a_set = {} for s_i in range(len(array)): cnt = array[s_i] if cnt[0] == 0 or cnt[1] == 0: continue t_cnt = tuple(cnt) if t_cnt not in a_set: a_set[t_cnt] = [] a_set[t_cnt].append(s_i) for value_indexes in a_set.values(): for indi in range(len(value_indexes)): s_i = value_indexes[indi] for indj in range(indi + 1, len(value_indexes)): t_i = value_indexes[indj] if s_i + l <= t_i: 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()