問題文

この問題はリアクティブ形式の（ジャッジ側のプログラムと対話的に実行する必要がある）問題です。

最初に $3$ 個の非負整数 $N, M, L$ が与えられます。

冪乗大好きbotは冪乗が大好きなbotです。

冪乗大好きbotは正整数 $B$ を隠し持っており、$N^{(M^L)}$（$N$ の「$M$ の $L$ 乗」乗）を $B$ で割った余り $N^{(M^L)} \bmod B$ を知りたがっています。

ただしここでは $0^0$ を $1$ と定義します。

そこで、以下の質問を $0$ 回以上 $100$ 回以下の好きな回数行います。

1. まずあなたが $10^9$ 以下の非負整数 $i$ と $j$ を選び、$i^j$ を $B$ で割った余り $i^j \bmod B$ を尋ねる。
2. 続いて冪乗大好きbotが $i^j \bmod B$ を答える。

最後に $N^{(M^L)} \bmod B$ を求めてください。

入出力

最初に $N, M, L$ が半角空白区切りで標準入力から $1$ 行で与えられます。

$N$ $M$ $L$

その後で質問を $0$ 回以上 $100$ 回以下の好きな回数してください。質問は標準入出力を用いて以下の形式で行います：

1. まず $10^9$ 以下の非負整数 $i$ と $j$ を選び、?と $i$ と $j$ を半角空白区切りで $1$ 行で出力してください。

? $i$ $j$

2. 続いて $i^j \bmod B$ が $1$ 行で与えられます。この際のジャッジ計算量は $O(\log_2 \max \{1,j\})$ であることが保証されます。

$i^j \bmod B$

次にあなたはこの問題に対する答えを標準出力に以下の形式で出力してください：

• !と $N^{(M^L)} \bmod B$ を半角空白区切りで $1$ 行で出力してください。

! $N^{(M^L)} \bmod B$

最後に改行してください。

制約

入力では与えられませんが $B$ は以下の制約を満たします：

• 全ての質問の前に $B$ は固定されており、すなわち質問の前後で $B$ の値は変化しない。
• $B$ は $1 \leq B \leq 10^9$ を満たす整数である。

入力は以下の制約を満たします：

• $N$ は $0 \leq N \leq 10^2$ を満たす整数である。
• $M$ は $0 \leq M \leq 10^2$ を満たす整数である。
• $L$ は $0 \leq L \leq 10^2$ を満たす整数である。
• $10^9$ 以下の任意の非負整数 $i, j$ に対し、$i^j$ を $B$ で割った余りを尋ねた際の返答である入力 $i^j \bmod B$ は $0 \leq i^j \bmod B < B$ を満たす整数である。

注意

リアクティブ形式の問題に慣れてない方は、リアクティブ形式の問題についてのまとめも参考にしてください。

この問題において、以下の指示に従っていない提出のジャッジ結果は保証しません：

• 出力は指定された形式に厳格に従ってください。例えば余計な空白を入れたりしないでください。
• 出力を行うたびに末尾に改行を入れて標準出力をflushしてください。
• この問題に対する答えを出力した後はプログラムをすぐに終了させてください。

サンプル