class MaxClique: # 最大クリーク # Bron–Kerbosch algorithm (O(1.4422^|V|)) の枝刈りをしたもの # 参考: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/2691674 # 検証1: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/7620028 # 検証2: https://judge.yosupo.jp/submission/12486 def __init__(self, n): self.n = n self.E = [0] * n self.stk = [0] * n # 最大クリークが入るスタック def __repr__(self): return "\n".join("{:0{}b}".format(e, self.n) for e in self.E) def add_edge(self, v, u): # assert v != u self.E[v] |= 1 << u self.E[u] |= 1 << v def invert(self): # 補グラフにする n, E = self.n, self.E mask = (1<> u & 1: E_sorted_ |= 1 << i E_sorted.append(E_sorted_) cand = (1 << n) - 1 # 候補の集合 self.cans = 1 # 最大クリークを構成する集合 # 復元するときはこれを使う self.ans = 1 self._dfs(0, cand) return self.ans def _dfs(self, elem_num, candi): if self.ans < elem_num: self.ans = elem_num cans_ = 0 index = self.index for s in self.stk[:elem_num]: cans_ |= 1 << index[s] self.cans = cans_ potential = elem_num + bin(candi).count("1") if potential <= self.ans: return E_sorted = self.E_sorted pivot = (candi & -candi).bit_length() - 1 # 候補から頂点をひとつ取り出す smaller_candi = candi & ~E_sorted[pivot] # pivot と直接結ばれていない頂点の集合(自己ループの無いグラフなので pivot を含む) while smaller_candi and potential > self.ans: next = smaller_candi & -smaller_candi candi ^= next smaller_candi ^= next potential -= 1 next = next.bit_length() - 1 if next == pivot or smaller_candi & E_sorted[next]: self.stk[elem_num] = next self._dfs(elem_num + 1, candi & E_sorted[next]) mod = 1000003 S = int(input()) S = S * 12345 % mod N = S % 120 + 2 S = S * 12345 % mod P = S mc = MaxClique(N) for i in range(N): for j in range(i+1, N): S = S * 12345 % mod if S < P: mc.add_edge(i, j) ans = mc.solve() + 1 print(ans) print(*[i+1 for i in range(N) if mc.cans>>i&1])