using System; using System.IO; using System.Linq; using System.Collections.Generic; using System.Diagnostics; using ModInt = AtCoder_MOD.ModInt;using static AtCoder_MOD.ModCalc;using Mod_Matrix = AtCoder_MOD.MOD_Matrix; //using ModInt = AtCoder_MOD.ModInt;using static AtCoder_MOD.ModCalc;using Mod_Matrix = AtCoder_MOD.MOD_Matrix; namespace AtCoder_Main { class Program { static void Main(string[] args) { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); int Testcase = 1; //Testcase = int.Parse(Console.ReadLine()); while (Testcase-- > 0) Solve(); Console.Out.Flush(); } static void Solve() { var N = long.Parse(Console.ReadLine()); var x = Console.ReadLine().Split().Select(long.Parse).ToArray(); var A = new Mod_Matrix(3); A[0][0] = A[1][1] = A[2][2] = 1; A[0][1] = A[1][2] = A[2][0] = -1; A = A.Pow(N - 1); var ans = new ModInt[] { x[0], x[1], x[2] }; ans = A * ans; Console.WriteLine(string.Join(" ", ans)); } } } namespace AtCoder_MOD { public interface IMod { int Mod { get; } // isprime ? } public interface INTTFriendly { int primitive_root { get; } } public readonly struct Mod1000000007 : IMod { public int Mod => 1000000007; } public readonly struct Mod998244353 : IMod, INTTFriendly { public int Mod => 998244353; public int primitive_root => 3; } public struct ModInt where T : IMod { private int value; // 0 <= x < mod 以外でも OK public ModInt(int x) { if (x < 0 || x >= default(T).Mod) x %= default(T).Mod; if (x < 0) x += default(T).Mod; value = x; } public ModInt(long x) { if (x < 0 || x >= default(T).Mod) x %= default(T).Mod; if (x < 0) x += default(T).Mod; value = (int)x; } // 0 <= x < mod public ModInt(uint x) => value = (int)x; public static ModInt operator +(ModInt a, ModInt b) { var nv = a.value + b.value; if (nv >= default(T).Mod) nv -= default(T).Mod; return new ModInt((uint)nv); } public static ModInt operator ++(ModInt a) => a + 1; public static ModInt operator -(ModInt a, ModInt b) { var nv = a.value - b.value; if (nv < 0) nv += default(T).Mod; return new ModInt((uint)nv); } public static ModInt operator --(ModInt a) => a - 1; public static ModInt operator *(ModInt a, ModInt b) => new ModInt((uint)(((long)a.value * b.value) % default(T).Mod)); //符号 public static ModInt operator +(ModInt a) => a; public static ModInt operator -(ModInt a) => a.value == 0 ? a : new ModInt((uint)(default(T).Mod - a.value)); public ModInt Pow(long n) { if (n < 0) return Pow(-n).Pow(default(T).Mod - 2); var p = this; var ret = new ModInt(1u); while (n > 0) { if ((n & 1) != 0) ret *= p; p *= p; n >>= 1; } return ret; } public ModInt Inverse() { Debug.Assert(value != 0); int x, u, s, t, k; x = 1; u = 0; t = default(T).Mod; s = value; while (t > 0) { k = s / t; s -= k * t; (s, t) = (t, s); x -= k * u; (x, u) = (u, x); } return new ModInt((uint)(x < 0 ? x + default(T).Mod : x)); } public static ModInt operator /(ModInt a, ModInt b) => (a * b.Inverse()); public static bool operator ==(ModInt a, ModInt b) => a.value == b.value; public static bool operator !=(ModInt a, ModInt b) => a.value != b.value; public override bool Equals(object obj) => obj is ModInt && this == (ModInt)obj; public override int GetHashCode() => value.GetHashCode(); public override string ToString() => value.ToString(); //キャスト public static implicit operator ModInt(int n) => new ModInt(n); public static implicit operator ModInt(long n) => new ModInt(n); public static explicit operator int(ModInt a) => a.value; public static explicit operator long(ModInt a) => a.value; public static int GetMod() => default(T).Mod; } public static class ModCalc where T : IMod { static readonly List> fac = new List>() { 1 }; static List> facinv; static int MAX_N; // Do Use Init(Max_n) Before using other functions public static void Init_Mod(int n) { MAX_N = n; for (int i = 1; i <= n; i++) fac.Add(fac.Last() * i); facinv = new List>() { fac[n].Inverse() }; for (int i = n; i > 0; i--) facinv.Add(facinv.Last() * i); facinv.Reverse(); } public static void Reset() { MAX_N = -1; fac.Clear(); facinv.Clear(); } public static ModInt Fac(int n) { Debug.Assert(n <= MAX_N); return fac[n]; } public static ModInt Finv(int n) { Debug.Assert(n <= MAX_N); return facinv[n]; } public static ModInt Comb(int n, int r) { Debug.Assert(n <= MAX_N); if (n < 0 || r < 0 || n < r) return 0; return fac[n] * facinv[n - r] * facinv[r]; } public static ModInt ModPow(long x, long n) => new ModInt(x).Pow(n); public static ModInt ModPow(int x, long n) => new ModInt((uint)x).Pow(n); public static ModInt ModPow(ModInt x, long n) => x.Pow(n); public static ModInt Inv(long x) => new ModInt(x).Inverse(); public static ModInt Inv(int x) => new ModInt((uint)x).Inverse(); public static List> GetFac() => fac; public static List> GetFacInv() => facinv; } public struct MOD_Matrix where T : IMod { int n; ModInt[][] mat; public MOD_Matrix(int size) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; } public MOD_Matrix(int size, ModInt[,] A) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j]; } public MOD_Matrix(int size, ModInt[][] A) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j]; } public MOD_Matrix(int size, long[,] A) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j]; } public MOD_Matrix(int size, long[][] A) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j]; } public MOD_Matrix(int size, int[,] A) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j]; } public MOD_Matrix(int size, int[][] A) { n = size; mat = new ModInt[n][]; for (var i = 0; i < n; i++) mat[i] = new ModInt[n]; for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j]; } public ModInt[] this[int id] { set { Debug.Assert(0 <= id && id < n); mat[id] = value; } get { Debug.Assert(0 <= id && id < n); return mat[id]; } } public ModInt this[int id1, int id2] { set { Debug.Assert(0 <= id1 && id1 < n && 0 <= id2 && id2 < n); mat[id1][id2] = value; } get { Debug.Assert(0 <= id1 && id1 < n && 0 <= id2 && id2 < n); return mat[id1][id2]; } } public static MOD_Matrix operator +(MOD_Matrix A, MOD_Matrix B) { Debug.Assert(A.n == B.n); for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] += B[i][j]; return A; } public static MOD_Matrix operator -(MOD_Matrix A, MOD_Matrix B) { Debug.Assert(A.n == B.n); for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] -= B[i][j]; return A; } public static MOD_Matrix operator *(MOD_Matrix A, MOD_Matrix B) { Debug.Assert(A.n == B.n); var ret = new MOD_Matrix(A.n); for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) { for (var k = 0; k < A.n; k++) ret[i][j] += A[i][k] * B[k][j]; } return ret; } public static ModInt[] operator *(MOD_Matrix A, ModInt[] V) { Debug.Assert(A.n == V.Length); var ret = new ModInt[A.n]; for(var i = 0; i < A.n; i++) { for (var j = 0; j < A.n; j++) ret[i] += A[i][j] * V[j]; } return ret; } public static MOD_Matrix operator *(MOD_Matrix A, ModInt k) { for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] *= k; return A; } public MOD_Matrix Pow(long K) { var ret = new MOD_Matrix(n); var P = this; for (var i = 0; i < n; i++) ret[i][i] = 1; while (K > 0) { if ((K & 1) != 0) ret *= P; P *= P;K >>= 1; } return ret; } } public class MOD_NTT where T : IMod, INTTFriendly { private readonly int mod; private readonly int root; public MOD_NTT() { mod = default(T).Mod; root = default(T).primitive_root; } void NTT(ref ModInt[] a, bool rev = false) { var n = a.Length; if (n == 1) return; var b = new ModInt[n]; var s = new ModInt(root).Pow(rev ? mod - 1 - (mod - 1) / n : (mod - 1) / n); var kp = new List>() { 1 }; int i, j, k, l, r; for (i = 0; i < (n >> 1); ++i) kp.Add(kp.Last() * s); for (i = 1, l = (n >> 1); i < n; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { for (k = 0, s = kp[i * j]; k < i; ++k) { var p = a[k + r]; var q = a[k + r + n / 2]; b[k + 2 * r] = (p + q); b[k + 2 * r + i] = ((p - q) * s); } } (a, b) = (b, a); } if (rev) { s = new ModInt(n).Inverse(); for (i = 0; i < n; ++i) a[i] *= s; } } public ModInt[] Convolution_MOD(ModInt[] a, ModInt[] b) { int N = a.Length + b.Length - 1; int t = 1; while (t < N) t <<= 1; var nxa = new ModInt[t]; var nxb = new ModInt[t]; for (var i = 0; i < a.Length; ++i) nxa[i] = a[i]; for (var i = 0; i < b.Length; ++i) nxb[i] = b[i]; NTT(ref nxa); NTT(ref nxb); for (var i = 0; i < t; i++) nxa[i] *= nxb[i]; NTT(ref nxa, true); return nxa[0..N]; } public ModInt[] Convolution_MOD(long[] a, long[] b) { int N = a.Length + b.Length - 1; int t = 1; while (t < N) t <<= 1; var nxa = new ModInt[t]; var nxb = new ModInt[t]; for (var i = 0; i < a.Length; ++i) nxa[i] = a[i]; for (var i = 0; i < b.Length; ++i) nxb[i] = b[i]; NTT(ref nxa); NTT(ref nxb); for (var i = 0; i < t; i++) nxa[i] *= nxb[i]; NTT(ref nxa, true); return nxa[0..N]; } } //次数固定、NTT対応modのみ public struct FormalPowerSeries where T : IMod, INTTFriendly { int n; ModInt[] P; static readonly MOD_NTT C = new MOD_NTT(); public FormalPowerSeries(int n) { this.n = n; P = new ModInt[n + 1]; } public int Length => n; public ModInt this[int id] { set { Debug.Assert(0 <= id && id <= n); P[id] = value; } get { Debug.Assert(0 <= id && id <= n); return P[id]; } } //Add //O(min(n,m)) public static FormalPowerSeries operator +(FormalPowerSeries F, FormalPowerSeries G) { int m = Math.Min(F.Length, G.Length); for (var i = 0; i <= m; i++) F[i] += G[i]; return F; } //O(1) public static FormalPowerSeries operator +(FormalPowerSeries F, ModInt a) { F[0] += a; return F; } //Subtract //O(min(n,m)) public static FormalPowerSeries operator -(FormalPowerSeries F, FormalPowerSeries G) { int m = Math.Min(F.Length, G.Length); for (var i = 0; i <= m; i++) F[i] -= G[i]; return F; } //O(1) public static FormalPowerSeries operator -(FormalPowerSeries F, ModInt a) { F[0] -= a; return F; } // Multiply //O(nlog(n)) //下位 n 項のみ残すことに注意 public static FormalPowerSeries operator *(FormalPowerSeries F, FormalPowerSeries G) { F.P = C.Convolution_MOD(F.P, G.P)[0..(F.n + 1)]; return F; } //O(n) public static FormalPowerSeries operator *(FormalPowerSeries F, ModInt a) { for (var i = 0; i <= F.n; i++) F[i] *= a; return F; } //Divide //Todo F/=G //O(n+log(mod)) public static FormalPowerSeries operator /(FormalPowerSeries F, ModInt a) { var inv = a.Inverse(); for (var i = 0; i <= F.n; i++) F[i] *= inv; return F; } } }