問題文

$N$ 要素の整数列 $A,B,C$ を考えます。
この数列の値が、$2\le i\le 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\le r<{10}^9+7$を満たすような唯一の整数 $r$ のことを指します。

入力

$N$
$A_1{B}_1{C}_1$

入力は全て整数である。
$2\le N\le {10}^{18}$
$0\le A_1,B_1,C_1\le {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