問題文

競技プログラミング勢はシャイであることはすでに述べました．
ところで，あるコンテストでは，一つの企画としてオンサイトまで勝ち残った競技プログラミング勢から何人か選びチームを作りリレー競技みたいなことをしようと考えています．
しかし，競技プログラミング勢はシャイなので，下手なチーム分けをしてしまうと，会話が全くなくなる可能性があります．

それを避けるために念入りに調査を行いました．
オンサイトに参加している競技プログラミング勢は $N$ 人いて，$i$ 番目の人と $j$ 番目の人との親しさを表す非負整数 $F_{ij}=F_{ji}$ を計算しました．
親しさがある閾値 $P$ 未満である場合は，その両者間で会話がない可能性があります．
また，チームの中に $1$ 組でも，親しさが $P$ 以上となる組があれば，そこから話しやすいムードが広がると考えられます．

チーム決めの際は，公平を期すためランダムに決めます．
よって，どのように $k$ 人（$2 \leq k \leq N$）のチームを作ろうとも，必ず，親しさが $P$ 以上となるような競技プログラミング勢の組が存在するような最小の $k$ を求めたいです．
そのような最小の $k$ を求めるプログラムを書いてください．
（全員参加のイベントではなく，必ずしも競う必要もないので，$k$ の値によっては，$1$ チームしか作れなかったり，余りの人が出たとしても問題はありません）

この問題は，必要な情報は乱数で生成され，入力ではその乱数の種 $S$ のみが与えられます．
乱数の種 $S$ が与えられたら，以下の擬似コードによって，情報が生成されます．

    $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$
        }
    }

入力

$S$

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

出力

条件を満たす最小の $k$ を $1$ 行で出力してください．
そのような $k$ が存在しない場合は，代わりに $\verb|-1|$ を出力してください．
また，存在する場合は，念の為に，確認として，次の行には，$k-1$ 人からなるチームで，全ての人の間での親しさが $P$ 未満となるようなチームのメンバーの番号を半角スペース区切りで $1$ 行で出力してください．
そのようなチームは複数存在する可能性がありますが，その場合はどれか $1$ つを出力してください．

この問題はスペシャルジャッジのため，余分な空白を出力してしまうなど，少しのフォーマットの違いでもWAになる可能性があります．

サンプル

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