package q3xx; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class N382 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { long S = ni(); S = S * 12345 % 1000003; int n = (int)(S%120)+2; S = S * 12345 % 1000003; int p = (int)S; boolean[][] g = new boolean[n][n]; for(int i = 0;i < n;i++){ for(int j = i+1;j < n;j++){ S = S * 12345 % 1000003; g[i][j] = g[j][i] = S < p; } } boolean[] res = MCS(g); out.println(size(res)+1); for(int i = 0;i < n;i++){ for(int j = i+1;j < n;j++){ if(res[i] && res[j]){ assert g[i][j]; } } } boolean f = true; for(int i = 0;i < n;i++){ if(res[i]){ if(!f)out.print(" "); f = false; out.print(i+1); } } out.println(); } static boolean[] MCS(boolean[][] g) { int n = g.length; boolean[] Q = new boolean[n]; boolean[] Qmax = new boolean[n]; int[] no = new int[n]; int[] V = new int[n]; extendedInitialSortNumber(V, no, Qmax, g); int[] f = new int[n]; for(int i = 0;i < n;i++){ f[V[i]] = i; } boolean[] nQmax = new boolean[n]; for(int i = 0;i < n;i++)nQmax[f[i]] = Qmax[i]; int[] nno = new int[n]; for(int i = 0;i < n;i++)nno[f[i]] = no[i]; for(int i = 0;i < n;i++)V[i] = i; boolean[][] ng = new boolean[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ ng[f[i]][f[j]] = g[i][j]; } } // reconstruct expandS(Arrays.copyOf(V, n), Arrays.copyOf(V, n), nno, Q, Qmax, ng); boolean[] ret = new boolean[n]; for(int i = 0;i < n;i++){ ret[i] = Qmax[f[i]]; } return ret; } static void extendedInitialSortNumber(int[] V, int[] no, boolean[] Qmax, boolean[][] g) { int n = g.length; int[] degs = new int[n]; int maxdeg = 0; for(int i = 0;i < n;i++){ int deg = 0; for(int j = 0;j < n;j++){ if(g[i][j]){ deg++; } } degs[i] = deg; maxdeg = Math.max(maxdeg, degs[i]); } // SORT int[] R = new int[n]; for(int i = 0;i < n;i++)R[i] = i; int vp = n; int[] Rmin = rmin(R, degs); while(Rmin.length != R.length){ int p = Rmin[0]; if(Rmin.length >= 2){ int minv = exdeg(Rmin[0], degs, g); for(int i = 1;i < Rmin.length;i++){ int lv = exdeg(Rmin[i], degs, g); if(lv < minv){ minv = lv; p = Rmin[i]; } } } V[--vp] = p; R = remove(R, p); for(int j = 0;j < R.length;j++){ if(g[p][R[j]]){ degs[R[j]]--; } } Rmin = rmin(R, degs); } // Regular subgraph numberSort(Rmin, no, g); for(int i = 0;i < Rmin.length;i++){ V[i] = Rmin[i]; } // NUMBER NUMBER: { int m = 0; for(int i = 0;i < Rmin.length;i++){ m = Math.max(m, no[Rmin[i]]); } int mmax = Rmin.length + maxdeg - m; m++; for(int i = Rmin.length;i < mmax;i++){ if(i >= n){ break NUMBER; } no[V[i]] = m; m++; } for(int i = mmax;i < n;i++){ no[V[i]] = maxdeg + 1; } } // START boolean fullm1 = true; for(int i = 0;i < Rmin.length;i++){ if(degs[Rmin[i]] == Rmin.length-1){ }else{ fullm1 = false; } } if(fullm1){ for(int i = 0;i < Rmin.length;i++){ Qmax[Rmin[i]] = true; } } } static void numberSort(int[] R, int[] no, boolean[][] g) { int n = g.length; int maxno = 0; boolean[][] c = new boolean[n+1][n]; for(int p : R){ int k = 1; inner: while(true){ for(int i = 0;i < n;i++){ if(g[p][i] && c[k][i]){ k++; continue inner; } } break; } if(k > maxno){ maxno = k; } no[p] = k; c[k][p] = true; } // sort int i = 0; for(int k = 1;k <= maxno;k++){ for(int j = 0;j < n;j++){ if(c[k][j]){ R[i++] = j; } } } assert i == R.length; } static void expandS(int[] Va, int[] R, int[] no, boolean[] Q, boolean[] Qmax, boolean[][] g) { int n = g.length; // U.tr("come", Va, R, no, Q); for(int j = R.length-1;j >= 0;j--){ int p = R[j]; // U.tr("no", p, Va, R); assert no[p] >= 1; if(size(Q) + no[p] > size(Qmax)){ Q[p] = true; int[] Vp = new int[Va.length]; int vpp = 0; // U.tr("gp", g[p]); for(int k = 0;k < Va.length;k++){ if(g[p][Va[k]]){ Vp[vpp++] = Va[k]; } } if(vpp > 0){ int[] newR = new int[vpp]; Arrays.fill(newR, -1); int[] newNo = new int[n]; Vp = Arrays.copyOf(Vp, vpp); renumberSort(Vp, newR, newNo, g, size(Qmax)-size(Q)); int k = 0; for(;k < newR.length && newR[k] == -1;k++); newR = Arrays.copyOfRange(newR, k, vpp); // U.tr("prev", Vp, newR, Qmax, Q); expandS(Vp, newR, newNo, Q, Qmax, g); }else if(size(Q) > size(Qmax)){ for(int k = 0;k < n;k++){ Qmax[k] = Q[k]; } } Q[p] = false; Va = removePreservingOrder(Va, p); } } } static void ReNUMBER(int p, int[] no, int nop, int noth, boolean[][] c, boolean[][] g) { int n = g.length; for(int k1 = 1;k1 <= noth-1;k1++){ int inter = 0; int q = -1; for(int i = 0;i < n;i++){ if(g[p][i] && c[k1][i]){ q = i; if(++inter == 2)break; } } if(inter == 1){ assert q != -1; inner: for(int k2 = k1 + 1;k2 <= noth;k2++){ for(int i = 0;i < n;i++){ if(g[q][i] && c[k2][i])continue inner; } no[q] = k2; no[p] = k1; assert p != q; assert c[nop][p]; assert !c[k1][p]; assert c[k1][q]; assert !c[k2][q]; c[nop][p] = false; c[k1][p] = true; c[k1][q] = false; c[k2][q] = true; return; } } } } // in: Va, noth // out: R,no static void renumberSort(int[] Va, int[] R, int[] no, boolean[][] g, int noth) { Arrays.fill(R, -1); Arrays.fill(no, -1); int n = g.length; int maxno = 0; boolean[][] c = new boolean[Va.length+1][n]; for(int p : Va){ // Conventional greedy approximate coloring int k = 1; inner: while(true){ for(int i = 0;i < n;i++){ if(g[p][i] && c[k][i]){ k++; continue inner; } } break; } if(k > maxno){ maxno = k; } no[p] = k; c[k][p] = true; // Re-NUMBER if(k > noth && k == maxno){ ReNUMBER(p, no, k, noth, c, g); if(empty(c[maxno])){ maxno--; } } } int i = Va.length; if(noth < 0)noth = 0; // U.tr("noth", noth); // for(int k = 1;k <= maxno;k++){ // UTr.tf(c[k]); // } int k; for(k = maxno;k >= noth+1;k--){ for(int j = n-1;j >= 0;j--){ if(c[k][j]){ i--; R[i] = j; no[R[i]] = k; } } } if(i != 0){ k--; for(int j = n-1;j >= 0;j--){ if(c[k][j]){ i--; R[i] = j; no[R[i]] = noth; break; } } } } static int[] remove(int[] a, int v) { for(int i = 0;i < a.length;i++){ if(a[i] == v){ a[i] = a[a.length-1]; return Arrays.copyOf(a, a.length-1); } } throw new RuntimeException(); } static int[] removePreservingOrder(int[] a, int v) { for(int i = 0;i < a.length;i++){ if(a[i] == v){ for(int j = i+1;j < a.length;j++){ a[i] = a[j]; } return Arrays.copyOf(a, a.length-1); } } throw new RuntimeException(); } static int exdeg(int q, int[] degs, boolean[][] g) { int ret = 0; for(int i = 0;i < g.length;i++){ if(g[q][i]){ ret += degs[i]; } } return ret; } static int[] rmin(int[] R, int[] degs) { int mindeg = 9999; int[] Rmin = new int[R.length]; int rminp = 0; for(int v : R){ if(degs[v] < mindeg){ mindeg = degs[v]; Rmin[rminp++] = v; }else if(degs[v] == mindeg){ rminp = 0; Rmin[rminp++] = v; } } Rmin = Arrays.copyOf(Rmin, rminp); return Rmin; } static boolean empty(boolean[] v) { for(boolean b : v)if(b)return false; return true; } static int size(boolean[] v) { int ret = 0; for(boolean b : v)if(b)ret++; return ret; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); } public static void main(String[] args) throws Exception { new N382().run(); } private byte[] inbuf = new byte[1024]; private int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }