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_2 {
	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;
		int m = (n>>>6)+1;
		long[][] g = new long[n][m];
		for(int i = 0;i < n;i++){
			for(int j = i+1;j < n;j++){
				S = S * 12345 % 1000003;
				if(S < p){
					g[i][j>>>6] |= 1L<<j;
					g[j][i>>>6] |= 1L<<i;
				}
			}
		}
		int[] res = MCS(g);
		if(2 <= res.length+1 && res.length+1 <= n){
			out.println(res.length+1);
			for(int i = 0;i < res.length;i++){
				if(i > 0)out.print(" ");
				out.print(res[i]+1);
			}
			out.println();
		}else{
			out.println(-1);
		}
	}
	
	public static int[] MCS(long[][] g)
	{
		int n = g.length;
		int m = (n>>>6)+1;
		long[] Qmax = new long[m];
		
		int[] no = new int[n];
		int[] V = new int[n];
		
		extendedInitialSortNumber(V, no, Qmax, g);
		long[] nQmax = new long[m];
		for(int i = 0;i < n;i++)if(Qmax[V[i]>>>6]<<~V[i]<0)nQmax[i>>>6] |= 1L<<i;
		int[] nno = new int[n];
		for(int i = 0;i < n;i++)nno[i] = no[V[i]];
		long[][] ng = new long[n][m];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				if(g[V[i]][V[j]>>>6]<<~V[j]<0){
					ng[i][j>>>6] |= 1L<<j;
				}
			}
		}
		
		long[] nv = new long[m];
		fill(nv, n);
		
		int[] nr = new int[n];
		for(int i = 0;i < n;i++)nr[i] = i;
		
		nos = new int[n][n];
		nos[0] = nno;
		expandS(nv, nr, 0, new long[m], Qmax, ng);
		int[] rec = reconstruct(Qmax, V);
//		check(rec, g);
		return rec;
//		return size(Qmax);
	}
	
	private static int[] reconstruct(long[] Qmax, int[] V)
	{
		int m = size(Qmax);
		int[] ret = new int[m];
		int p = 0;
		for(int i = 0;i < Qmax.length;i++){
			for(long j = Qmax[i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				ret[p++] = V[id];
			}
		}
		assert p == m;
		Arrays.sort(ret);
		return ret;
	}
	
	private static void fill(long[] a, int n)
	{
		for(int i = 0;i < a.length && i < n>>>6;i++){
			a[i] = -1L;
		}
		if((n&63) != 0)a[n>>>6] = (1L<<n)-1;
	}
	
	private static void check(int[] s, long[][] g)
	{
		for(int i = 0;i < s.length;i++){
			for(int j = i+1;j < s.length;j++){
				if(g[s[i]][s[j]>>>6]<<~s[j]>=0)throw new RuntimeException(s[i] + " " + s[j]);
			}
		}
	}
	
	static int[][] nos;
	
	static void expandS(long[] Va, int[] R, int depno, long[] Q, long[] Qmax, long[][] g)
	{
		int n = g.length;
		int m = (n>>>6)+1;
		
		int[] no = nos[depno];
		for(int j = R.length-1;j >= 0;j--){
			int p = R[j];
			assert no[p] >= 1;
			if(size(Q) + no[p] > size(Qmax)){
				Q[p>>>6] |= 1L<<p;
				long[] Vp = new long[Va.length];
				for(int k = 0;k < m;k++){
					Vp[k] = Va[k]&g[p][k];
				}
				if(!empty(Vp)){
					int[] newR = new int[size(Vp)];
					int[] newNo = nos[depno+1];
					int k = renumberSort(Vp, newR, newNo, g, size(Qmax)-size(Q));
					newR = Arrays.copyOfRange(newR, k, newR.length);
					expandS(Vp, newR, depno+1, Q, Qmax, g);
				}else if(size(Q) > size(Qmax)){
					for(int k = 0;k < Qmax.length;k++){
						Qmax[k] = Q[k];
					}
				}
				Q[p>>>6] ^= 1L<<p;
				Va[p>>>6] ^= 1L<<p;
			}
		}
	}
	
	private static void ReNUMBER(int p, int[] no, int nop, int noth, long[][] c, long[][] g)
	{
		int n = g.length;
		int m = (n>>>6)+1;
		for(int k1 = 1;k1 <= noth-1;k1++){
			int inter = 0;
			int q = -1;
			for(int i = 0;i < m;i++){
				long inte = g[p][i]&c[k1][i];
				int icb = Long.bitCount(inte);
				inter += icb;
				if(inter >= 2)break;
				if(icb == 1){
					q = Long.numberOfTrailingZeros(inte)|i<<6;
				}
			}
			if(inter == 1){
				assert q != -1;
				inner:
				for(int k2 = k1 + 1;k2 <= noth;k2++){
					for(int i = 0;i < m;i++){
						if((g[q][i]&c[k2][i]) != 0)continue inner;
					}
					no[q] = k2;
					no[p] = k1;
					assert p != q;
					assert c[nop][p>>>6]<<~p<0;
					assert c[k1][p>>>6]<<~p>=0;
					assert c[k1][q>>>6]<<~q<0;
					assert c[k2][q>>>6]<<~q>=0;
					c[nop][p>>>6] ^= 1L<<p;
					c[k1][p>>>6] ^= 1L<<p;
					c[k1][q>>>6] ^= 1L<<q;
					c[k2][q>>>6] ^= 1L<<q;
					return;
				}
			}
		}
	}
	
	// in: Va, noth
	// out: R,no
	private static int renumberSort(long[] Va, int[] R, int[] no, long[][] g, int noth)
	{
//		Arrays.fill(R, -1);
//		Arrays.fill(no, -1);
		int n = g.length;
		int m = (n>>>6)+1;
		int maxno = 0;
		long[][] c = new long[size(Va)+1][m];
		for(int z = 0;z < m;z++){
			for(long y = Va[z];y != 0;y&=y-1){
				int p = Long.numberOfTrailingZeros(y)|z<<6;
				// Conventional greedy approximate coloring
				int k = 1;
				
				inner:
				while(true){
					for(int i = 0;i < m;i++){
						if((g[p][i]&c[k][i]) != 0){
							k++;
							continue inner;
						}
					}
					break;
				}
				if(k > maxno){
					maxno = k;
				}
				no[p] = k;
				c[k][p>>>6] |= 1L<<p;
				
				// Re-NUMBER
				if(k > noth && k == maxno){
					ReNUMBER(p, no, k, noth, c, g);
					if(empty(c[maxno])){
						maxno--;
					}
				}
			}
		}
		
		int i = size(Va);
		if(noth < 0)noth = 0;
		int k;
		for(k = maxno;k >= noth+1;k--){
			for(int j = m-1;j >= 0;j--){
				for(long y = c[k][j];y != 0;y^=Long.highestOneBit(y)){
					int x = j<<6|63-Long.numberOfLeadingZeros(y);
					i--;
					R[i] = x;
					no[R[i]] = k;
				}
			}
		}
		if(i != 0){
			k--;
			inner:
			for(int j = m-1;j >= 0;j--){
				for(long y = c[k][j];y != 0;y^=Long.highestOneBit(y)){
					int x = j<<6|63-Long.numberOfLeadingZeros(y);
					i--;
					R[i] = x;
					no[R[i]] = noth;
					break inner;
				}
			}
		}
		return i;
	}
	
	public static int size(long[] a)
	{
		int ret = 0;
		for(long v : a)ret += Long.bitCount(v);
		return ret;
	}
	
	public static boolean empty(long[] a)
	{
		for(long v : a)if(v != 0)return false;
		return true;
	}
	
	public static int min(long[] a)
	{
		for(int i = 0;i < a.length;i++){
			if(a[i] != 0L)return Long.numberOfTrailingZeros(a[i])|i<<6;
		}
		return -1;
	}
	
	private static void extendedInitialSortNumber(int[] V, int[] no, long[] Qmax, long[][] g)
	{
		int n = g.length;
		int[] degs = new int[n];
		int maxdeg = 0;
		for(int i = 0;i < n;i++){
			degs[i] = size(g[i]);
			maxdeg = Math.max(maxdeg, degs[i]);
		}
		
		// SORT
		long[] R = new long[(n>>>6)+1];
		fill(R, n);
		int vp = n;
		long[] Rmin = rmin(R, degs);
		while(size(Rmin) != size(R)){
			int p = min(Rmin);
			if(size(Rmin) >= 2){
				int minv = Integer.MAX_VALUE;
				for(int i = 0;i < Rmin.length;i++){
					for(long j = Rmin[i];j != 0;j&=j-1){
						int id = Long.numberOfTrailingZeros(j)|i<<6;
						int lv = exdeg(id, degs, g);
						if(lv < minv){
							minv = lv;
							p = id;
						}
					}
				}
			}
			V[--vp] = p;
			R[p>>>6] ^= 1L<<p;
			
			for(int i = 0;i < R.length;i++){
				for(long j = R[i]&g[p][i];j != 0;j&=j-1){
					int id = Long.numberOfTrailingZeros(j)|i<<6;
					degs[id]--;
				}
			}
			Rmin = rmin(R, degs);
		}
		
		// Regular subgraph
		numberSort(Rmin, no, g);
		int ii = 0;
		for(int i = 0;i < Rmin.length;i++){
			for(long j = Rmin[i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				V[ii++] = id;
			}
		}
		
		// NUMBER
		NUMBER: {
			int m = 0;
			for(int i = 0;i < Rmin.length;i++){
				for(long j = Rmin[i];j != 0;j&=j-1){
					int id = Long.numberOfTrailingZeros(j)|i<<6;
					m = Math.max(m, no[id]);
				}
			}
			int mmax = size(Rmin) + maxdeg - m;
			m++;
			for(int i = size(Rmin);i < mmax;i++){
				if(i >= n)break NUMBER;
				no[V[i]] = m++;
			}
			for(int i = mmax;i < n;i++){
				no[V[i]] = maxdeg + 1;
			}
		}
		
		// START
		boolean fullm1 = true;
		outer:
		for(int i = 0;i < Rmin.length;i++){
			for(long j = Rmin[i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				if(degs[id] != size(Rmin)-1){
					fullm1 = false;
					break outer;
				}
			}
		}
		if(fullm1){
			for(int i = 0;i < Rmin.length;i++){
				Qmax[i] = Rmin[i];
			}
		}
	}
	
	private static int exdeg(int q, int[] degs, long[][] g)
	{
		int ret = 0;
		for(int i = 0;i < g[q].length;i++){
			for(long j = g[q][i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				ret += degs[id];
			}
		}
		return ret;
	}
	
	private static long[] rmin(long[] R, int[] degs)
	{
		int mindeg = 9999;
		long[] Rmin = new long[R.length];
		for(int i = 0;i < R.length;i++){
			for(long j = R[i];j != 0;j&=j-1){
				int v = Long.numberOfTrailingZeros(j)|i<<6;
				if(degs[v] < mindeg){
					mindeg = degs[v];
					Rmin[v>>>6] |= 1L<<v;
				}else if(degs[v] == mindeg){
					Arrays.fill(Rmin, 0L);
					Rmin[v>>>6] |= 1L<<v;
				}
			}
		}
		return Rmin;
	}
	
	private static void numberSort(long[] R, int[] no, long[][] g)
	{
		int n = g.length;
		int maxno = 0;
		int m = (n>>>6)+1;
		long[][] c = new long[size(R)+1][m];
		for(int z = 0;z < R.length;z++){
			for(long j = R[z];j != 0;j &= j-1){
				int p = Long.numberOfTrailingZeros(j)|z<<6;
				int k = 1;
				
				inner:
				while(true){
					for(int i = 0;i < m;i++){
						if((g[p][i]&c[k][i]) != 0){
							k++;
							continue inner;
						}
					}
					break;
				}
				if(k > maxno){
					maxno = k;
				}
				no[p] = k;
				c[k][p>>>6] |= 1L<<p;
			}
		}
		// sort
		int i = 0;
		for(int k = 1;k <= maxno;k++){
			for(int u = 0;u < m;u++){
				for(long j = c[k][u];j != 0;j &= j-1){
					int p = Long.numberOfTrailingZeros(j)|u<<6;
					i++;
					R[p>>>6] |= 1L<<p;
				}
			}
		}
		assert i == size(R);
	}
	
	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_2().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)); }
}