問題文

$N$ 要素の整数列 $A,B,C$ を考えます。
この数列の値が、$2 \leq i \leq N$ において、次の条件を満たすとします。

・ $A_i = A_{i-1}-B_{i-1}$
・ $B_i=B_{i-1}-C_{i-1}$
・ $C_i=C_{i-1}-A_{i-1}$

$(A_1,B_1,C_1)$ が与えられるので、$(A_N,B_N,C_N)$ をそれぞれ $10^9+7$ で割った余りを求めてください。
この問題において、整数 $X$ を $10^9+7$ で割った余りとは、整数 $q$ を用いて $X = q \times (10^9+7) + r$ と表せ、かつ $0 \leq r < 10^9+7$を満たすような唯一の整数 $r$ のことを指します。

入力

$N$
$A_1\ B_1\ C_1$

入力は全て整数である。
$2 \leq N \leq 10^{18}$
$0 \leq A_1,B_1,C_1 \leq 10^9$

出力

$(A_N,B_N,C_N)$ をそれぞれ $10^9+7$ で割った余りを、空白区切りで出力してください。 最後に改行してください。

サンプル

2
1 2 3

1000000006 1000000006 2

3
0 0 0

0 0 0

10
1000000000 998244353 924844033

945425885 912366722 142207407