Problem Statement

As already mentioned, competitive programmers are shy.
Now, at a certain contest, the organizers are planning an event in which some of the competitive programmers who advanced to the onsite round are chosen to form teams and take part in something like a relay competition.
However, because competitive programmers are shy, a careless team division could result in no conversation at all.

To avoid this, a thorough investigation was carried out.
There are $N$ competitive programmers participating onsite, and a non-negative integer $F_{ij}=F_{ji}$ representing the closeness between the $i$-th person and the $j$-th person has been calculated.
If the closeness is less than a certain threshold $P$, there may be no conversation between those two people.
Also, if a team contains even $1$ pair whose closeness is at least $P$, a mood that makes talking easy is expected to spread from that pair.

To ensure fairness, teams are decided randomly.
Therefore, we want to find the minimum $k$ such that, no matter how a team of $k$ people ($2 \leq k \leq N$) is formed, there always exists a pair of competitive programmers in it whose closeness is at least $P$.
Write a program that finds this minimum $k$.
(This is not an event in which everyone participates, and there is no requirement to compete, so depending on the value of $k$, it is fine if only $1$ team can be formed or if some people are left over.)

In this problem, the necessary information is generated by random numbers, and only the random seed $S$ is given as input.
Given the random seed $S$, the information is generated by the following pseudocode.

    $S$ is given
    $S = (S \times 12345)\ {\rm mod}\ 1000003$
    $N = (S\ {\rm mod}\ 120) + 2$
    $S = (S \times 12345)\ {\rm mod}\ 1000003$
    $P = S$
    for($i$=1; $i$<=$N$; $i$++){
        for($j$=$i$+1; $j$<=$N$; $j$++){
            $S = (S \times 12345)\ {\rm mod}\ 1000003$
            $F_{ij} = F_{ji} = S$
        }
    }

Input

$S$

$1 \leq S < 1000003$, $S \in \mathbb{Z}$

Output

Output the minimum $k$ satisfying the condition on $1$ line.
If no such $k$ exists, output $\verb|-1|$ instead.
If it exists, then for confirmation, on the next line, output on $1$ line the member numbers, separated by half-width spaces, of a team of $k-1$ people in which the closeness between all of the people is less than $P$.
There may be multiple such teams; in that case, output any $1$ of them.

Since this problem uses a special judge, even a slight format difference, such as printing extra whitespace, may result in WA.

Sample

657

3
1 3

58

5
87 86 12 44

31884

37
7 36 70 79 6 35 14 78 15 59 68 56 16 46 69 28 54 81 83 8 34 53 1 24 32 13 17 66 19 38 12 18 23 41 73 40