#include using namespace std; #define GET4(_1,_2,_3,NAME,...) NAME #define GET5(_1,_2,_3,_4,NAME,...) NAME #define GET6(_1,_2,_3,_4,_5,NAME,...) NAME #define GET11(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME #define rep1(i, n) for(long long i=0;i<(long long)(n);i++) #define rep2(i,k,n) for(long long i=k;i<(long long)(n);i++) #define rep3(i,k,n,s) for(long long i=k;i<(long long)(n);i+=(s)) #define rep(...) GET5(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per1(i,n) for(long long i=(n)-1ll;i>-1ll;i--) #define per2(i,k,n) for(long long i=(n)-1ll;i>(long long)(k)-1ll;i--) #define per3(i,k,n,s) for(long long i=(n)-1ll;i>(long long)(k)-1ll;i-=(s)) #define per(...) GET5(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c))) #define pb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define dame(a) {out(a);return 0;} #define decimal cout<> (n0); #define readi2(n0,n1) ll n0,n1; cin >> (n0) >> (n1); #define readi3(n0,n1,n2) ll n0,n1,n2; cin >> (n0) >> (n1) >> (n2); #define readi4(n0,n1,n2,n3) ll n0,n1,n2,n3; cin >> (n0) >> (n1) >> (n2) >> (n3); #define readi5(n0,n1,n2,n3,n4) ll n0,n1,n2,n3,n4; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4); #define readi6(n0,n1,n2,n3,n4,n5) ll n0,n1,n2,n3,n4,n5; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5); #define readi7(n0,n1,n2,n3,n4,n5,n6) ll n0,n1,n2,n3,n4,n5,n6; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6); #define readi8(n0,n1,n2,n3,n4,n5,n6,n7) ll n0,n1,n2,n3,n4,n5,n6,n7; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7); #define readi9(n0,n1,n2,n3,n4,n5,n6,n7,n8) ll n0,n1,n2,n3,n4,n5,n6,n7,n8; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7) >> (n8); #define readi10(n0,n1,n2,n3,n4,n5,n6,n7,n8,n9) ll n0,n1,n2,n3,n4,n5,n6,n7,n8,n9; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7) >> (n8) >> (n9); #define readi(...) GET11(__VA_ARGS__, readi10, readi9, readi8, readi7, readi6, readi5, readi4, readi3, readi2, readi1)(__VA_ARGS__) #define readvi1(v,n) vi v(n); rep(i,(n)) cin >> (v).at(i); #define readvi2(v,w,n) vi v(n),w(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i); #define readvi3(v,w,x,n) vi v(n),w(n),x(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i) >> (x).at(i); #define readvi4(v,w,x,y,n) vi v(n),w(n),x(n),y(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i) >> (x).at(i) >> (y).at(i); #define readvi(...) GET5(__VA_ARGS__, readvi3, readvi2, readvi1)(__VA_ARGS__) #define reads1(n) string n; cin >> (n); #define reads2(n,m) string n,m; cin >> (n) >> (m); #define reads3(n,m,l) string n,m,l; cin >> (n) >> (m) >> (l); #define reads4(n,m,l,k) string n,m,l; cin >> (n) >> (m) >> (l) >> (k); #define reads(...) GET5(__VA_ARGS__, reads4, reads3, reads2, reads1)(__VA_ARGS__) #define readvs(v,n) vs v(n); rep(i,(n)) cin >> (v).at(i); #define readd1(n) ld n; cin >> (n); #define readd2(n,m) ld n,m; cin >> (n) >> (m); #define readd3(n,m,l) ld n,m,l; cin >> (n) >> (m) >> (l); #define readd4(n,m,l,k) ld n,m,l; cin >> (n) >> (m) >> (l) >> (k); #define readd(...) GET5(__VA_ARGS__, readd4, readd3, readd2, readd1)(__VA_ARGS__) #define readvvi(v,n,m) vvi v((n),vi(m)); rep(i,(n))rep(j,(m)) cin >> (v).at(i).at(j); #define readvvs(v,n,m) vvs v((n),vs(m)); rep(i,(n))rep(j,(m)) cin >> (v).at(i).at(j); #define readvpi(v,n) vpi v(n); rep(i,(n)) cin >> (v).at(i).fi >> (v).at(i).se; #define readg(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G.at(a).push_back(b);G.at(b).push_back(a);} #define readgd(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G.at(a).push_back(b);} #define readgdrev(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G.at(b).push_back(a);} #define readt(G,n) vvi G(n);rep(i,n-1){readi(a,b);a--;b--;G.at(a).push_back(b);G.at(b).push_back(a);} using ll = long long; using ull = unsigned long long; using ld = long double; template using P = pair; template using PP = tuple; template using PPP = tuple; using pi = P; using ppi = PP; using pppi = PPP; template using V = vector; template using VV = vector>; template using VVV = vector>>; template using VVVV = vector>>>; using vi=V; using vvi=VV; using vvvi=VVV; using vvvvi=VVVV; using vpi=V; using vvpi=VV; using vppi=V; using vvppi=VV; using vpppi=V; using vvpppi=VV; using vb=V; using vvb=VV; using vs=V; using vvs=VV; const ll inf=(1 << 30); const ll Inf=((ll)1 << 40); const ll INf=((ll)1 << 50); const ll INF=((ll)1 << 60); const double eps=1e-10; ///////////////////////////////////////////////////////// template using PQ = priority_queue; template using SPQ = priority_queue,greater>; template bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template bool chmax(T&a,T b){if(a void out0s(T a); template void out0(pair p){out0s(p.fi); out0s(p.se);} template < typename Tuple, size_t ...I > array tuple_print(Tuple&& t, index_sequence){ return {{ (void( out0s(get(t))), 0)... }}; } template void out0(tuple p){ tuple_print(p, make_index_sequence>>::value>{}); } template void out0(vector v){for(T c : v) out0s(c);} template void out0(set v){for(T c : v) out0s(c);} template void out0s(T a){out0(a); cout << " ";} template void out(VV v){for(auto c : v) {out0(c); cout << endl;}} template void out(map v){for(auto c : v) {out0(c); cout << endl;}} templatevoid out(T a) {out0(a); cout << endl;} templatevoid out(T a, Ts... b) {out0(a); cout << " "; out(b...);} void out0d(ll a){cout< void out0sd(T a); template void out0d(pair p){cout << "("; out0sd(p.fi); out0d(p.se); cout << ")";} template < typename Tuple, size_t ...I > array tuple_printd(Tuple&& t, index_sequence){ return {{ (void( out0s(get(t))), 0)... }}; } template void out0d(tuple p){ cout << "("; tuple_printd(p, make_index_sequence>>::value>{}); cout << ")"; } template void out0d(vector v){for(T c : v) out0sd(c);} template void out0d(set v){for(T c : v) out0sd(c);} template void out0sd(T a){out0d(a); cout << " ";} template void outd(VV v){for(auto c : v) {out0d(c); cout << endl;}} template void outd(map v){for(auto c : v) {out0d(c); cout << endl;}} templatevoid outd(T a) {out0d(a); cout << endl;} templatevoid outd(T a, Ts... b) {out0d(a); cout << " "; outd(b...);} template void outm(T a){cout< void outvm(T v){rep(i,v.size()){if(i)cout<<' ';cout< void outvvm(T v){rep(i,v.size())outvm(v[i]);} template bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template void yesno(T b){if(b)out("yes");else out("no");} template void YesNo(T b){if(b)out("Yes");else out("No");} template void YESNO(T b){if(b)out("YES");else out("NO");} template void posimp(T b){if(b)out("possible");else out("impossible");} template void PosImp(T b){if(b)out("Possible");else out("Impossible");} template void POSIMP(T b){if(b)out("POSSIBLE");else out("IMPOSSIBLE");} void outs(ll a,ll b,ll i){if(abs(a)>=i-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll lcm(ll a,ll b){return (a / gcd(a,b)) * b;} ll powll(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;} ll modpow(ll a,ll b,ll modd){ll res=1;a%=modd;while(b){if(b&1)res=res*a%modd;a=a*a%modd;b>>=1;}return res;} ll sqrtll(ll a){assert(a >= 0); ll r = (ll)sqrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1) <= a) r++; return r;} ll cbrtll(ll a){assert(a >= 0); ll r = (ll)cbrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1)*(r+1) <= a) r++; return r;} ll modinv(ll a, ll b){assert(a); if(a == 1) return 1; if(b == 1) return 0; ll ret = (1ll-b*modinv(b%a, a))/a; ret %= b; if(ret < 0) ret += b; return ret;} vi maximal_independent_set(vvi& G){ static constexpr int MAX = 128; ll n = G.size(); assert(n <= MAX); const ll M = (ld)n * 0.0869l; if(n <= 64){ vector nbh(n); rep(i,n)for(auto j:G.at(i)) nbh[i] |= (1ull << j); unordered_map> memo; function(ull)> rec = [&](ull x){ ll degmax = -1, vmax = -1; ull y = x; ll ret = 0; ull rets = 0; while(y){ ll v = __builtin_ctzll(y); y &= ~(1ull << v); if(!(nbh[v] & x)) ret++, x &= ~(1ull << v), rets |= (1ull << v); ll deg = __builtin_popcountll(nbh[v] & x); if(deg == 1) { ll w = __builtin_ctzll(nbh[v] & x); auto [cret, crets] = rec(x & ~(1ull << v) & ~(1ull << w)); return make_pair(ret + cret + 1, rets | crets | (1ull << v)); } if(chmax(degmax,deg)) vmax = v; } if(memo.count(x)) return make_pair(ret + memo[x].fi, rets + memo[x].se); if(!x) return make_pair(ret, rets); ull z = x & ~(1ull << vmax); auto [cret1, crets1] = rec(z); if(degmax > 2){ auto [cret2, crets2] = rec(z & ~nbh[vmax]); if(chmax(cret1, cret2 + 1)) crets1 = crets2 | (1ull << vmax); } if(__builtin_popcountll(x) <= M) memo[x] = {cret1, crets1}; return make_pair(ret + cret1, rets + crets1); }; auto [_, ansset] = rec(n == 64 ? ~(0ull) : (1ull << n)-1); vi ret; while(ansset){ ll v = __builtin_ctzll(ansset); ansset &= ~(1ull << v); ret.push_back(v); } return ret; } else{ vector<__uint128_t> nbh(n); rep(i,n)for(auto j:G.at(i)) nbh[i] |= (((__uint128_t)1) << j); map<__uint128_t,pair> memo; auto ctzint128 = [&](__uint128_t x){ if((ull)x) return __builtin_ctzll((ull)x); return __builtin_ctzll((ull)(x >> 64)) + 64; }; auto popcountint128 = [&](__uint128_t x){ return __builtin_popcountll((ull)x) + __builtin_popcountll((ull)(x >> 64)); }; function(__uint128_t)> rec = [&](__uint128_t x){ ll degmax = -1, vmax = -1; __uint128_t y = x; ll ret = 0; __uint128_t rets = 0; while(y){ ll v = ctzint128(y); y &= ~(((__uint128_t)1) << v); if(!(nbh[v] & x)) ret++, x &= ~(((__uint128_t)1) << v), rets |= (((__uint128_t)1) << v); ll deg = popcountint128(nbh[v] & x); if(deg == 1) { ll w = ctzint128(nbh[v] & x); auto [cret, crets] = rec(x & ~(((__uint128_t)1) << v) & ~(((__uint128_t)1) << w)); return make_pair(ret + cret + 1, rets | crets | (((__uint128_t)1) << v)); } if(chmax(degmax,deg)) vmax = v; } if(memo.count(x)) return make_pair(ret + memo[x].fi, rets + memo[x].se); if(!x) return make_pair(ret, rets); __uint128_t z = x & ~(((__uint128_t)1) << vmax); auto [cret1, crets1] = rec(z); if(degmax > 2){ auto [cret2, crets2] = rec(z & ~nbh[vmax]); if(chmax(cret1, cret2 + 1)) crets1 = crets2 | (((__uint128_t)1) << vmax); } if(popcountint128(x) <= M) memo[x] = {cret1, crets1}; return make_pair(ret + cret1, rets + crets1); }; auto [_, ansset] = rec(n == 128 ? ~((__uint128_t)0) : (((__uint128_t)1) << n)-1); vi ret; while(ansset){ ll v = ctzint128(ansset); ansset &= ~(((__uint128_t)1) << v); ret.push_back(v); } return ret; } } int main(){ constexpr ll A = 12345; constexpr ll M = 1000003; readi(s); s = (s*A) % M; ll n = (s % 120)+2; s = (s*A) % M; ll p = s; vvi G(n); rep(i,n)rep(j,i+1,n){ s = (s*A) % M; if(s >= p){ G.at(i).push_back(j); G.at(j).push_back(i); } } auto v = maximal_independent_set(G); if(v.size() == n){ cout << -1 << endl; return 0;} cout << v.size()+1 << endl; rep(i,v.size()){ cout << v.at(i)+1; if(i < v.size()-1) cout << " "; } cout << endl; }