package グラフ;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//Pair p=mis(g)
	//p.cardinality:最大独立集合の頂点数
	//p.choosed_vertices:最大独立集合の頂点
	//120頂点で5秒ぐらい。
	//verified yukicoder No.382
	//
	public static void main(String[] args){
		new Main().solver();
	}


	void solver() {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			long S = sc.nextLong();
			long Start = System.currentTimeMillis();
			Graph g = set_edge(S);
			Pair p = ms(g);
			int n = g.n;
			if (p.cardinality == n) {
				System.out.println(-1);
			} else {
				System.out.println((p.cardinality + 1));
				boolean f = false;
				for (int i = 0; i < p.choosed_vertices.length; i++) {
					if (p.choosed_vertices[i]) {
						System.out.print((!f ? "" : " ") + (i + 1));
						f = true;
					}
				}
				System.out.println();
			}
			long T = System.currentTimeMillis();
			System.err.println((T - Start) + "ms");
		}
		sc.close();
	}

	final long MOD = 1000003;

	Graph set_edge(long S) {
		S = (S * 12345) % MOD;
		int N = (int) (S % 120) + 2;
		Graph g = new Graph(N);
		S = (S * 12345) % MOD;
		long P = S;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				S = (S * 12345) % MOD;
				if (S >= P) {
					g.set_edge(i, j);
				}
			}
		}
		return g;
	}


	// 無向グラフ
	class Graph {
		ArrayList<Integer>[] e;
		int n;
		int[] deg;
		boolean[] valid_vertices;// 選ぶことのできる頂点
		boolean[] choosed_vertices;// 選ばれた頂点
		long v=0;//選ばれた頂点。0は存在しない。1は存在。

		Graph(int n) {
			this.n = n;
			deg = new int[n];
			valid_vertices = new boolean[n];
			choosed_vertices = new boolean[n];
			Arrays.fill(valid_vertices, true);
			e = new ArrayList[n];
			for (int i = 0; i < n; i++) {
				e[i] = new ArrayList<>();
			}
		}
		Graph[] disjoint_set() throws CloneNotSupportedException{
			int[] ds=new int[n];
			Arrays.fill(ds, -1);
			ArrayDeque<Integer> q=new ArrayDeque<>();
			int now=0;
			for(int i=0;i<n;i++){
				if(ds[i]==-1){
					q.add(i);
					while(!q.isEmpty()){
						int v=q.poll();
						ds[v]=now;
						for(int j=0;j<e[v].size();j++){
							int u=e[v].get(j);
							if(ds[u]==-1){
								ds[u]=now;
								q.add(now);
							}
						}
					}
					now++;
				}
			}
			if(now==0){
				return new Graph[]{(Graph)clone()};
			}
			Graph[] gs=new Graph[now+1];
			boolean[][] each_valid_vertices=new boolean[now+1][n];
			for(int i=0;i<n;i++){
				int d=ds[i];
				each_valid_vertices[d][i]=true;
			}
			for(int i=0;i<=now;i++){
				gs[i]=induced_subgraph(each_valid_vertices[i]);
			}
			return gs;
		}

		// 無向グラフの辺a<->を作成
		void set_edge(int a, int b) {
			if (!e[a].contains((Integer) b)) {
				e[a].add(b);
				e[b].add(a);
				deg[a]++;
				deg[b]++;
			}
		}

		private void delete_undirected_edge(int a, int b) {
			e[a].remove((Integer) b);
			e[b].remove((Integer) a);
			deg[a]--;
			deg[b]--;
		}

		void delete_vertice(int v) {
			while (e[v].size() > 0) {
				int u = e[v].get(0);
				delete_undirected_edge(u, v);
			}
			valid_vertices[v] = false;
		}

		void delete_v_with_neighbours(int v) {
			while (e[v].size() > 0) {
				int u = e[v].get(0);
				delete_vertice(u);
			}
			delete_vertice(v);
		}
		private Graph induced_subgraph(boolean[] valid_vertices){
			Graph g=copy();
			g.valid_vertices=valid_vertices;
			for(int i=0;i<n;i++){
				if(!this.valid_vertices[i])
					continue;
				else if(valid_vertices[i])
					continue;
				else if(this.valid_vertices[i]&&(!valid_vertices[i])){
					g.delete_vertice(i);
				}else{
					throw new AssertionError();
				}
			}
			return g;
		}

		Graph copy() {
			Graph g = new Graph(this.n);
			for (int i = 0; i < n; i++) {
				g.deg[i] = deg[i];
			}
			for (int i = 0; i < n; i++) {
				g.valid_vertices[i] = valid_vertices[i];
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < e[i].size(); j++) {
					(g.e[i]).add(e[i].get(j));
				}
			}
			return g;
		}
	}

	Pair ms(Graph g){
		int n = g.n;
		try {
			Graph[] gs=g.disjoint_set();
			if(gs.length>=2){
				Pair p=new Pair(0,new boolean[n]);
				for(int i=0;i<gs.length;i++){
					p=pair_union(p,ms(gs[i]));
				}
				return p;
			}
		} catch (CloneNotSupportedException e1) {
			// TODO 自動生成された catch ブロック
			e1.printStackTrace();
		}

		int[] deg = g.deg;
		ArrayList<Integer>[] e = g.e;
		boolean[] valid_vertices = g.valid_vertices;
		int A = -1;// 最も次数の小さい頂点
		int B = -1;// Aにつながる頂点のうち最も次数の大きいもの
		int deg_me_min = Integer.MAX_VALUE / 4;
		int deg_to_max = -Integer.MAX_VALUE / 4;
		for (int i = 0; i < n; i++) {
			if (!valid_vertices[i])
				continue;
			if (deg[i] < deg_me_min) {
				A = i;
				deg_me_min = deg[A];
				if (deg_me_min <= 1) {
					g.delete_v_with_neighbours(A);
					Pair p = ms(g);
					p.choosed_vertices[A] = true;
					p.cardinality++;
					return p;
				}
				B = e[A].get(0);
				deg_to_max = deg[B];
				for (int j = 1; j < e[A].size(); j++) {
					int u = e[A].get(j);
					if (deg[u] > deg_to_max) {
						B = u;
						deg_to_max = deg[B];
					}
				}
			} else if (deg[i] == deg_me_min) {
				for (int j = 0; j < e[A].size(); j++) {
					int u = e[A].get(j);
					if (deg[u] > deg_to_max) {
						A = i;
						B = u;
						deg_to_max = deg[B];
					}
				}
			}
		}

		if (A == -1 && B == -1)
			return new Pair(0, new boolean[n]);
		if (A == -1 || B == -1)
			throw new AssertionError("A==-1||B==-1");
		if (deg[A] > deg[B])
			throw new AssertionError("deg[A]>deg[B]");
		if (deg[A] == 2) {
			int B2 = -1;
			if (e[A].get(0) != B) {
				B2 = e[A].get(0);
			} else if (e[A].get(1) != B) {
				B2 = e[A].get(1);
			}
			if (edge(B2,B,e)) {
				g.delete_v_with_neighbours(A);
				Pair p = ms(g);
				p.cardinality++;
				p.choosed_vertices[A] = true;
				return p;
			}else{

				Graph g2 = g.copy();
				g2.delete_v_with_neighbours(B);
				g2.delete_v_with_neighbours(B2);
				Pair p = ms(g2);
				p.cardinality += 2;
				p.choosed_vertices[B] = true;
				p.choosed_vertices[B2] = true;

				ArrayList<Integer> neighbour = new ArrayList<>();
				for (int i = 0; i < 2; i++) {
					int u = (i == 0 ? B : B2);// u is an element of N(A)
					for (int j = 0; j < e[u].size(); j++) {
						int v = e[u].get(j);
						if (v == A)
							continue;
						if (neighbour.contains(v))
							continue;
						neighbour.add(v);
					}
				}
				g.delete_v_with_neighbours(A);
				Pair p2 = ms2(g, neighbour);
				p2.cardinality++;
				p2.choosed_vertices[A] = true;
				p = pair_bigger(p, p2);
				return p;
			}
		}
		if (deg[A] == 3) {
			Graph g2 = g.copy();
			g2.delete_v_with_neighbours(A);
			Pair p2 = ms(g2);
			p2.cardinality++;
			p2.choosed_vertices[A] = true;

			ArrayList<Integer> S=new ArrayList<>();
			for (int i = 0; i < e[A].size(); i++) {
				S.add(e[A].get(i));
			}
			g.delete_vertice(A);
			Pair p1 = ms2(g, S);


			return pair_bigger(p1, p2);
		}
		ArrayList<Integer> a=new ArrayList<>();
		ArrayList<Integer> b=new ArrayList<>();
		a.add(A);
		b.add(B);
		ArrayList<Integer> NA=union(e[A],a);
		ArrayList<Integer> NB=union(e[B],b);
		if (is_subset(NA, NB)) {
			g.delete_vertice(B);
			Pair p = ms(g);
			return p;
		}
		Graph g2 = g.copy();
		g2.delete_v_with_neighbours(B);
		g.delete_vertice(B);

		Pair p1 = ms(g);
		Pair p2 = ms(g2);
		p2.cardinality++;
		p2.choosed_vertices[B] = true;
		return pair_bigger(p1, p2);
	}

	// Sから少なくとも二つ使う場合を考える。
	Pair ms2(Graph g, ArrayList<Integer> S) {
		int[] deg = g.deg;
		ArrayList<Integer>[] e = g.e;
		boolean[] valid_vertices = g.valid_vertices;
		int n = g.n;

		Pair p = new Pair(0, new boolean[n]);
		if (S.size() <= 1)
			return p;
		else if (S.size() == 2) {
			int u = S.get(0);
			int v = S.get(1);
			if (edge(u,v,e))
				return p;
			else {
				g.delete_v_with_neighbours(u);
				g.delete_v_with_neighbours(v);
				p = ms(g);
				p.cardinality += 2;
				p.choosed_vertices[u] = true;
				p.choosed_vertices[v] = true;
				return p;
			}
		} else if (S.size() == 3) {
			int[] s = new int[3];
			for (int i = 0; i < 3; i++) {
				s[i] = S.get(i);
			}
			// arrange s[i] so that s[0] is the smallest one;
			if (deg[s[0]] > deg[s[1]]) {
				int d = s[0];
				s[0] = s[1];
				s[1] = d;
			}
			if (deg[s[0]] > deg[s[2]]) {
				int d = s[0];
				s[0] = s[2];
				s[2] = d;
			}
			if (deg[s[0]] == 0) {
				g.delete_vertice(s[0]);
				S.remove((Integer) s[0]);
				p = ms1(g, S);
				p.cardinality++;
				p.choosed_vertices[s[0]] = true;
				return p;
			} else if (edge(s[0], s[1], e) && edge(s[1], s[2], e) && edge(s[2], s[0], e)) {
				return p;
			}
			for (int i = 0; i < 3; i++) {
				int u = s[(i + 1) % 3];
				int v = s[(i + 2) % 3];

				if (edge(u, s[i], e) && edge(s[i], v, e)) {
					g.delete_v_with_neighbours(u);
					g.delete_v_with_neighbours(v);
					p = ms(g);
					p.cardinality += 2;
					p.choosed_vertices[u] = true;
					p.choosed_vertices[v] = true;
					return p;
				}
			}
			for (int i = 0; i < 3; i++) {
				int u = s[(i + 1) % 3];
				int v = s[(i + 2) % 3];
				if (edge(u, v, e)) {
					g.delete_v_with_neighbours(s[i]);
					S.remove((Integer) s[i]);
					p = ms1(g, S);
					p.cardinality++;
					p.choosed_vertices[s[i]] = true;
					return p;
				}
			}

			for (int i = 0; i < 3; i++) {
				int u = s[i];
				int v = s[(i + 1) % 3];
				ArrayList<Integer> intersection = intersection(e[u], e[v]);
				if (intersection.size() >= 1) {
					int w = intersection.get(0);
					g.delete_vertice(w);
					p = ms2(g, S);
					return p;
				}
			}
			if (deg[s[0]] == 1) {
				g.delete_v_with_neighbours(s[0]);
				S.remove((Integer) s[0]);
				p = ms1(g, S);
				p.cardinality++;
				p.choosed_vertices[s[0]] = true;
				return p;
			} else {

				Graph g2 = g.copy();
				g2.delete_v_with_neighbours(s[0]);
				S.remove((Integer) s[0]);
				p = ms1(g2, S);
				p.cardinality++;
				p.choosed_vertices[s[0]] = true;

				g.delete_v_with_neighbours(s[2]);
				g.delete_v_with_neighbours(s[1]);
				ArrayList<Integer> S2 = new ArrayList<>();
				for (int i = 0; i < e[s[0]].size(); i++) {
					S2.add(e[s[0]].get(i));
				}
				g.delete_vertice(s[0]);
				Pair p2=ms(g);
				//				Pair p2 = ms2(g,S2);
				p2.cardinality+=2;
				p2.choosed_vertices[s[2]]=true;
				p2.choosed_vertices[s[1]]=true;

				return pair_bigger(p, p2);
			}
		}
		if (S.size() == 4) {
			int min_v = S.get(0);
			for (int i = 0; i < 4; i++) {
				int v = S.get(i);
				if (deg[v] < deg[min_v]) {
					min_v = v;
				}
			}
			if (deg[min_v] <= 3) {
				return ms(g);
			} else {
				Graph g2 = g.copy();

				g.delete_v_with_neighbours(min_v);
				p = ms(g);
				p.cardinality++;
				p.choosed_vertices[min_v] = true;


				g2.delete_vertice(min_v);
				S.remove((Integer) min_v);
				Pair p2 = ms2(g2, S);
				return pair_bigger(p, p2);
			}
		}
		if (S.size() <= 4)
			throw new AssertionError();
		return ms(g);
	}

	Pair ms1(Graph g, ArrayList<Integer> S) {
		int[] deg = g.deg;
		ArrayList<Integer>[] e = g.e;
		boolean[] valid_vertices = g.valid_vertices;
		int n = g.n;

		for(int i=0;i<S.size();i++){
			int v=S.get(i);
			if(!valid_vertices[v]){
				throw new AssertionError();
			}
		}

		if (S.size() != 2) {
			throw new AssertionError("S.size()!=2");
		}
		int s1 = S.get(0);
		int s2 = S.get(1);
		if (deg[s1] > deg[s2]) {
			int d = s1;
			s1 = s2;
			s2 = d;
		}

		if (deg[s1] <= 1) {
			return ms(g);
		} else if (edge(s1,s2,e)) {
			if (deg[s1] <= 3)
				return ms(g);
			else {
				Graph g2 = g.copy();

				g.delete_v_with_neighbours(s1);
				Pair p1 = ms(g);
				p1.cardinality++;
				p1.choosed_vertices[s1] = true;

				g2.delete_v_with_neighbours(s2);
				Pair p2 = ms(g2);
				p2.cardinality++;
				p2.choosed_vertices[s2] = true;
				return pair_bigger(p1, p2);
			}
		}
		ArrayList<Integer> intersection = intersection(e[s1], e[s2]);
		if (intersection.size() != 0) {
			for (int i = 0; i < intersection.size(); i++) {
				g.delete_vertice(intersection.get(i));
			}
			return ms1(g, S);
		} else if (deg[s2] == 2) {
			if (deg[s1] != 2) {
				throw new AssertionError("deg[s1]!=2");
			}
			int E = e[s1].get(0);
			int F = e[s1].get(1);
			if (edge(E,F,e)) {
				g.delete_v_with_neighbours(s1);
				Pair p = ms(g);
				p.cardinality++;
				p.choosed_vertices[s1] = true;
				return p;
			}
			ArrayList<Integer> union = union(e[E], e[F]);
			union.remove((Integer) s1);
			if (is_subset(union, e[s2])) {
				g.delete_v_with_neighbours(E);
				g.delete_v_with_neighbours(F);
				g.delete_v_with_neighbours(s2);
				Pair p = ms(g);
				p.cardinality += 3;
				p.choosed_vertices[E] = true;
				p.choosed_vertices[F] = true;
				p.choosed_vertices[s2] = true;
				return p;
			} else {
				Graph g2 = g.copy();

				g.delete_v_with_neighbours(E);
				g.delete_v_with_neighbours(F);
				g.delete_v_with_neighbours(s2);
				Pair p = ms(g);
				p.cardinality += 3;
				p.choosed_vertices[E] = true;
				p.choosed_vertices[F] = true;
				p.choosed_vertices[s2] = true;

				g2.delete_v_with_neighbours(s1);
				Pair p2 = ms(g2);
				p2.cardinality++;
				p2.choosed_vertices[s1] = true;

				return pair_bigger(p, p2);
			}

		} else {
			Graph g2 = g.copy();

			g.delete_v_with_neighbours(s2);
			Pair p = ms(g);
			p.cardinality++;
			p.choosed_vertices[s2]=true;

			g2.delete_v_with_neighbours(s1);
			ArrayList<Integer> S2=new ArrayList<>();
			for(int i=0;i<e[s2].size();i++){
				S2.add(e[s2].get(i));
			}
			g2.delete_vertice(s2);
			Pair p2 = ms2(g2, S2);
			p2.cardinality++;
			p2.choosed_vertices[s1] = true;

			p = pair_bigger(p, p2);
			return p;
		}

	}

	class Pair {
		int cardinality;
		boolean[] choosed_vertices;

		Pair(int cardinality, boolean[] choosed_vertices) {
			this.cardinality = cardinality;
			this.choosed_vertices = choosed_vertices;
		}
	}

	boolean is_subset(ArrayList<Integer> subset, ArrayList<Integer> superset) {
		if (subset.size() > superset.size())
			return false;
		for (int i = 0; i < subset.size(); i++) {
			if (!superset.contains(subset)) {
				return false;
			}
		}
		return true;
	}

	ArrayList<Integer> union(ArrayList<Integer> s1, ArrayList<Integer> s2) {
		ArrayList<Integer> ret = new ArrayList<>();
		for (int i = 0; i < s1.size(); i++) {
			if (!ret.contains(s1.get(i))) {
				ret.add(s1.get(i));
			}
		}
		for (int i = 0; i < s2.size(); i++) {
			if (!ret.contains(s2.get(i))) {
				ret.add(s2.get(i));
			}
		}
		return ret;
	}


	// 頂点u,v間に辺が存在するときtrueを返す。
	boolean edge(int u, int v, ArrayList<Integer>[] e) {
		if (e[u].contains(v))
			return true;
		else
			return false;
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	ArrayList intersection(ArrayList s1, ArrayList s2) {
		ArrayList ret = new ArrayList<>();
		for (int i = 0; i < s1.size(); i++) {
			if (s2.contains(s1.get(i))) {
				ret.add(s1.get(i));
			}
		}
		return ret;
	}

	Pair pair_bigger(Pair p1, Pair p2) {
		return p1.cardinality > p2.cardinality ? p1 : p2;
	}
	Pair pair_union(Pair p1,Pair p2){
		int n=p1.choosed_vertices.length;
		int cardinality=0;
		
		boolean[] d=new boolean[n];
		for(int i=0;i<n;i++){
			if(p1.choosed_vertices[i]||p2.choosed_vertices[i]){
				d[i]=true;
				cardinality++;
			}
		}
		return new Pair(cardinality,d);
	}
}