#include using namespace std; template struct MaximumClique { const int V; int E = 0; bitset ans; vector> G; MaximumClique(const int V) : V(V), G(vector>(V)) {} bool addEdge(const int from, const int to) { if(G[from][to]) return false; G[from][to] = G[to][from] = true; ++E; return true; } void increment(bitset &mask) { for(int i = 0; i < bit; ++i) { if(not mask[i]) { mask[i] = true; return; } mask[i] = false; } } void reverse() { bitset mask((1ll << V) - 1); mask.flip(); for(int i = 0; i < V; ++i) { G[i].flip(); G[i] ^= mask; } } bitset build() { bitset mask((1ll << V) - 1); return build(mask, E); } bitset build(bitset mask, int E) { if(mask.count() < ans.count()) return ans; bitset ret = clique(mask); for(int i = 0; i < V; ++i) { if(mask[i]) { int deg = G[i].count(); if(deg * deg < 2 * E) { bitset ex; for(int j = 0; j < V; ++j) { if(G[i][j]) { G[i].flip(j); G[j].flip(i); ex[j] = true; --E; } } ret = build(mask.flip(i), E); for(int j = 0; j < V; ++j) { if(ex[j]) { G[i].flip(j); G[j].flip(i); } } } } } return (ans = ret); } bitset clique(bitset mask) { // cerr << "clique : " << bitset<5>(mask) << endl; // for(int i = 0; i < V; ++i) { // cerr << i << " : " << bitset<5>(G[i]) << endl; // } const int V = mask.count(); int node[V]; for(int i = 0, cnt = 0; i < V; ++i, ++cnt) { while(not mask[cnt]) ++cnt; node[i] = cnt; } bitset ret = ans; for(bitset mask; not mask[V]; increment(mask)) { // cerr << "group : " << bitset<5>(mask) << endl; if(mask.count() < ret.count()) continue; try { for(int i = 0; i < V; ++i) { if(mask[i]) { for(int j = 0; j < V; ++j) { if(i == j) continue; if(not mask[j]) continue; // if(not (((G[node[i]] >> j) & 1) & ((mask >> j) & 1))) { if(not G[node[i]][j]) { // cerr << i << " diff : " << bitset<5>(G[node[i]]) << endl; // cerr << j << " diff : " << bitset<5>(mask) << endl; throw "INVALID"; } } } } } catch(...) { continue; } ret = mask; // cerr << bitset<5>(ret) << endl; // ret = (__builtin_popcountll(ret) > __builtin_popcountll(mask) ? ret : mask); } // cerr << "result : " << bitset<5>(ret) << endl; return (ans = ret); } }; int main() { const int MOD = 1e6 + 3; int64_t s; cin >> s; s = s * 12345 % MOD; int n = s % 120 + 2; MaximumClique<128> mc(n); s = s * 12345 % MOD; int64_t p = s; for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { s = s * 12345 % MOD; if(s >= p) { mc.addEdge(i, j); } } } mc.reverse(); mc.build(); int ans = mc.ans.count() - 1; if(ans == n - 1) { cout << -1 << '\n'; return 0; } cout << ans << '\n'; for(int i = 1, cnt = 0; i <= n or cnt < ans; ++i) { if(mc.ans[i - 1]) { cout << i << (cnt == n - 1 ? '\n' : ' '); ++cnt; } } return 0; }