import std.conv, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken().to!int; } long readLong() { return readToken().to!long; } real readReal() { return readToken().to!real; } void chmin(T)(ref T t, in T f) { if (t > f) t = f; } void chmax(T)(ref T t, in T f) { if (t < f) t = f; } int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; } int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); } int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); } int root(int[] uf, int u) { return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u])); } bool connect(int[] uf, int u, int v) { u = uf.root(u); v = uf.root(v); if (u == v) return false; if (uf[u] > uf[v]) swap(u, v); uf[u] += uf[v]; uf[v] = u; return true; } int[] independentSet(int[][] g, bool assumeConnected = false) { const n = cast(int)(g.length); if (n == 0) return []; if (n == 1) return [0]; int[] ret; if (assumeConnected) { const degs = g.map!(us => cast(int)(us.length)).array; const uMin = cast(int)(degs.minIndex), uMax = cast(int)(degs.maxIndex); if (degs[uMax] <= 2) { // path or cycle ret ~= uMin; int t = -1, u = uMin; foreach (j; 1 .. (degs[uMin] == 1) ? n : (n - 1)) { const v = (g[u][0] != t) ? g[u][0] : g[u][1]; t = u; u = v; if (j % 2 == 0) ret ~= u; } } else { const u0 = (degs[uMin] >= 2) ? uMax : uMin; // use u0 { auto ids = new int[n]; ids[] = -1; ids[u0] = -2; foreach (v; g[u0]) ids[v] = -2; int[] us; foreach (u; 0 .. n) if (ids[u] != -2) us ~= u; foreach (int j, u; us) ids[u] = j; auto gg = new int[][us.length]; foreach (int j, u; us) foreach (v; g[u]) if (ids[v] != -2) gg[j] ~= ids[v]; ret = u0 ~ independentSet(gg).map!(j => us[j]).array; } // do not use u0 if (degs[uMin] >= 2) { auto ids = new int[n]; int[] us; foreach (u; 0 .. n) if (u != u0) us ~= u; foreach (int j, u; us) ids[u] = j; auto gg = new int[][us.length]; foreach (int j, u; us) foreach (v; g[u]) if (v != u0) gg[j] ~= ids[v]; const res = independentSet(gg); if (ret.length < res.length) ret = res.map!(j => us[j]).array; } } } else { // solve for each connected component auto uf = new int[n]; uf[] = -1; foreach (u; 0 .. n) foreach (v; g[u]) uf.connect(u, v); auto uss = new int[][n]; foreach (u; 0 .. n) uss[uf.root(u)] ~= u; auto ids = new int[n]; foreach (r; 0 .. n) if (uf[r] < 0) { foreach (int j, u; uss[r]) ids[u] = j; auto gg = new int[][uss[r].length]; foreach (int j, u; uss[r]) foreach (v; g[u]) gg[j] ~= ids[v]; const res = independentSet(gg, true); foreach (j; res) ret ~= uss[r][j]; } } return ret; } int N; long P; long[][] F; void main() { try { for (; ; ) { /* S is given S=(S×12345) mod 1000003 N=(S mod 120)+2 S=(S×12345) mod 1000003 P=S for(i=1; i<=N; i++){ for(j=i+1; j<=N; j++){ S=(S×12345) mod 1000003 Fij=Fji=S } } */ long S = readLong(); S = (S * 12345) % 1000003; N = (S % 120) + 2; S = (S * 12345) % 1000003; P = S; F = new long[][](N, N); foreach (u; 0 .. N) { foreach (v; u + 1 .. N) { S = (S * 12345) % 1000003; F[u][v] = F[v][u] = S; } } stderr.writeln("N = ", N); auto g = new int[][N]; foreach (u; 0 .. N) { foreach (v; 0 .. N) { if (u != v) { if (F[u][v] >= P) { g[u] ~= v; } } } } const res = independentSet(g); if (res.length == N) { writeln(-1); } else { writeln(res.length + 1); writeln(res.map!(u => u + 1).to!string.replaceAll(regex(`[\[\],]`), "")); } } } catch (EOFException e) { } }