def maximum_clique_BK(G):
    def dfs(R, P, cnt):
        nonlocal ans,val
        if P==0:
            if val < cnt:
                val = cnt
                ans = R
            return
        PP = P&~g[(P&-P).bit_length() - 1]
        while PP:
            v = PP&-PP
            vv = v.bit_length() - 1
            dfs(R|v, P&g[vv], cnt+1)
            P ^= v
            PP ^= v

    n = len(G)
    #assert n <= 63
    N = 1<<n
    g = [0]*n
    for a in range(n):
        for b in range(n):
            if G[a][b] == 0 and a != b:
                g[a] ^= 1<<b
    ans = val = 0
    dfs(R=0, P=N-1, cnt=0)
    return ans,val


s = int(input())
MOD = 1000003
s = s*12345%MOD
n = s%120+2
g = [[0]*n for _ in range(n)]
p = s = s*12345%MOD
for i in range(n):
    for j in range(i+1,n):
        s = s*12345%MOD
        if s >= p:
            g[i][j] = g[j][i] = 1
ans, val = maximum_clique_BK(g)
print(val+1)
ans = [i+1 for i,c in enumerate(bin(ans)[2:][::-1]) if c == "1"]
print(*ans)