using A; using AtCoder.Internal; using ModInt = AtCoder.StaticModInt; using System; using System.Buffers; using System.Collections; using System.Diagnostics; using System.Globalization; using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.Intrinsics.X86; using static A.InputUtility; class Program { static void Main() { SourceExpander.Expander.Expand(); using Output output = new(false); ModInt[] r = new ModInt[200001]; r[0] = 1; r[1] = 1; for (int i = 2; i < r.Length; i++) { r[i] = r[i - 1] + r[i - 2]; } ModInt[] e = new ModInt[200001]; e[0] = 1; e[1] = 3; for (int i = 2; i < e.Length; i++) { e[i] = e[i - 1] + e[i - 2]; } InputNewLine(); var q = NextInt32; for (int _ = 0; _ < q; _++) { InputNewLine(); var n = NextInt32 - 1; var res = 5 * r[n] * r[n] - e[n] * e[n]; Console.WriteLine(res); } } } namespace A { public static class InputUtility { private static string[]? s_inputs; private static string? s_raw; private static int s_index = 0; private static void Init() => s_index = 0; public static int NextInt32 => int.Parse(s_inputs![s_index++]!); public static uint NextUInt32 => uint.Parse(s_inputs![s_index++]!); public static long NextInt64 => long.Parse(s_inputs![s_index++]!); public static string NextString => s_inputs![s_index++]; public static char NextChar => s_inputs![s_index++][0]; public static decimal NextDecimal => decimal.Parse(s_inputs![s_index++]!); public static BigInteger NextBigInteger => BigInteger.Parse(s_inputs![s_index++]!); public static int[] GetInt32Array() => s_inputs!.Select(int.Parse).ToArray(); public static long[] GetInt64Array() => s_inputs!.Select(long.Parse).ToArray(); public static string GetRawString() => s_raw!; #if DEBUG private static TextReader? s_textReader; public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path)); #endif public static bool InputNewLine() { #if DEBUG if (s_textReader is TextReader sr) { Init(); s_raw = sr.ReadLine()!; s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries); return true; } #endif Init(); s_raw = Console.ReadLine()!; s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries); return true; } } public static class CombinationFunction { public static void PartedRotate(T[] a, int first1, int last1, int first2, int last2) { if (first1 == last1 || first2 == last2) return; int next = first2; while (first1 != next) { Swap(a, first1++, next++); if (first1 == last1) first1 = first2; if (next == last2) { next = first2; } else if (first1 == first2) { first2 = next; } } } public static bool NextCombinationImp(T[] a, int first1, int last1, int first2, int last2) where T : IComparable { if (first1 == last1 || first2 == last2) return false; int target = last1 - 1; int lastElem = last2 - 1; while (target != first1 && !(a[target].CompareTo(a[lastElem]) < 0)) target--; if (target == first1 && !(a[target].CompareTo(a[lastElem]) < 0)) { PartedRotate(a, first1, last1, first2, last2); return false; } int next = first2; while (!(a[target].CompareTo(a[next]) < 0)) next++; Swap(a, target++, next++); PartedRotate(a, target, last1, next, last2); return true; } public static bool NextCombination(T[] a, int first, int mid, int last) where T : IComparable => NextCombinationImp(a, first, mid, mid, last); public static bool PrevCombination(T[] a, int first, int mid, int last) where T : IComparable => NextCombinationImp(a, mid, last, first, mid); public static void Swap(T[] a, int i, int j) => (a[i], a[j]) = (a[j], a[i]); } public static class PermutationFunction { public static bool NextPermutation(T[] a) where T : IComparable { int n = a.Length; int i = n - 2; while (i >= 0 && a[i].CompareTo(a[i + 1]) >= 0) { i--; } if (i < 0) { return false; } int j = n - 1; while (a[j].CompareTo(a[i]) <= 0) { j--; } (a[i], a[j]) = (a[j], a[i]); Array.Reverse(a, i + 1, n - i - 1); return true; } } public readonly struct Output : IDisposable { private readonly StreamWriter _sw; #if DEBUG public Output(string path) { var fs = new FileStream(path, FileMode.Create, FileAccess.Write); _sw = new StreamWriter(fs); Console.SetOut(_sw); } #endif public Output(bool autoFlush) { _sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = autoFlush }; Console.SetOut(_sw); } public void Dispose() { _sw.Dispose(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal void Flush() { _sw.Flush(); } } public static class ArrayExtensions { public static void Swap(this T[] array, int i, int j) => (array[i], array[j]) = (array[j], array[i]); public static int LowerBound(this T[] a, T target) where T : IComparable { int ok = a.Length; int ng = -1; while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid) (ok, ng) = a[mid].CompareTo(target) >= 0 ? (mid, ng) : (ok, mid); return ok; } public static int UpperBound(this T[] a, T target) where T : IComparable { int ok = a.Length; int ng = -1; while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid) (ok, ng) = a[mid].CompareTo(target) > 0 ? (mid, ng) : (ok, mid); return ok; } public static ModInt Sum(this ModInt[] a) { long res = 0; foreach (var item in a) res += item.Value; return new ModInt(res); } public struct IndexedEnumerable : IEnumerable<(T item, int index)> { private readonly T[] _a; private readonly int _startIndex; public IndexedEnumerable(T[] a, int startIndex = 0) { _a = a; _startIndex = startIndex; } public readonly IndexedEnumerator GetEnumerator() => new IndexedEnumerator(_a, _startIndex); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); IEnumerator<(T item, int index)> IEnumerable<(T item, int index)>.GetEnumerator() => GetEnumerator(); } public struct IndexedEnumerator : IEnumerator<(T item, int index)> { public readonly (T item, int index) Current => (_a[_index], _index + _startIndex); private int _index; private int _startIndex; private T[] _a; public IndexedEnumerator(T[] a, int startIndex) { _index = -1; _a = a; _startIndex = startIndex; } public bool MoveNext() => ++_index < _a.Length; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public void Reset() => _index = -1; } /// (T value, int index) public static IndexedEnumerable Enumerate(this T[] arr, int startIndex = 0) => new IndexedEnumerable(arr, startIndex); } public static class IEnumerableExtensions { public static IEnumerable Log(this IEnumerable source) { Console.WriteLine(string.Join(' ', source)); return source; } public static ScanEnumerable Scan( this IEnumerable source, TAccumulate seed, Func accumulator) where TSource : struct where TAccumulate : struct { return new ScanEnumerable(source, accumulator, seed); } public static IEnumerable ScanExSeed( this IEnumerable source, TAccumulate seed, Func accumulator) { var accumulation = new List(); var current = seed; foreach (var item in source) { current = accumulator(current, item); accumulation.Add(current); } return accumulation; } public readonly struct ScanEnumerable : IEnumerable where TSource : struct where TAccumulate : struct { private readonly IEnumerable _source; private readonly Func _accumulator; private readonly TAccumulate _seed; public ScanEnumerable(IEnumerable source, Func accumulator, TAccumulate seed) { _source = source; _accumulator = accumulator; _seed = seed; } public readonly ScanEnumerator GetEnumerator() => new(_source, _accumulator, _seed); readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } public struct ScanEnumerator : IEnumerator where TSource : struct where TAccumulate : struct { private readonly Func _accumulator; private readonly IEnumerator _enumerator; private TAccumulate _current; private bool _secondOrLaterElement = false; public ScanEnumerator(IEnumerable source, Func accumulator, TAccumulate seed) { _enumerator = source.GetEnumerator(); _accumulator = accumulator; _current = seed; } public readonly TAccumulate Current => _current; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public bool MoveNext() { if (_secondOrLaterElement) { if (_enumerator.MoveNext()) { _current = _accumulator(_current, _enumerator.Current); return true; } return false; } else { _secondOrLaterElement = true; return true; } } public void Reset() { throw new NotSupportedException(); } } public static IEnumerable Scan( this IEnumerable source, Func accumulator) { if (source is null) throw new ArgumentNullException(paramName: nameof(source)); if (accumulator is null) throw new ArgumentNullException(paramName: nameof(accumulator)); var accumulation = new List(); if (source.Any() is false) { return accumulation; } var current = source.First(); accumulation.Add(current); foreach (var item in source.Skip(1)) { current = accumulator(current, item); accumulation.Add(current); } return accumulation; } public static CombinationEnumerable Combination(this T[] a, int k) where T : IComparable => new(a, k); public readonly struct CombinationEnumerable where T : IComparable { private readonly T[] _a; private readonly int _k; public CombinationEnumerable(T[] a, int k) { _a = a; _k = k; } public readonly CombinationEnumerator GetEnumerator() => new(_a, _k); } public struct CombinationEnumerator : IEnumerator> where T : IComparable { private readonly int _k; private readonly T[] _a; private readonly int _n; private bool _secondOrLaterElement = false; public CombinationEnumerator(T[] a, int k) { _a = a; _n = a.Length; _k = k; } public readonly ReadOnlyMemory Current => _a.AsMemory()[.._k]; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public bool MoveNext() { if (_secondOrLaterElement) { return CombinationFunction.NextCombination(_a, 0, _k, _n); } else { _secondOrLaterElement = true; return true; } } public void Reset() { throw new NotSupportedException(); } } public static PermutationEnumerable Permutation(this T[] a) where T : IComparable => new(a); public readonly struct PermutationEnumerable where T : IComparable { private readonly T[] _a; public PermutationEnumerable(T[] a) => _a = a; public readonly PermutationEnumerator GetEnumerator() => new(_a); } public struct PermutationEnumerator : IEnumerator> where T : IComparable { private readonly T[] _a; private readonly int _n; private bool _secondOrLaterElement = false; public PermutationEnumerator(T[] a) { _a = a; _n = a.Length; } public readonly ReadOnlyMemory Current => _a.AsMemory()[..]; readonly object IEnumerator.Current => Current; public readonly void Dispose() { } public bool MoveNext() { if (_secondOrLaterElement) { return PermutationFunction.NextPermutation(_a); } else { _secondOrLaterElement = true; return true; } } public void Reset() => throw new NotSupportedException(); } } public class MyMath { public static long Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(1L, (acc, x) => acc * x); public static long Pow10(int y) => Pow(10, y); public static long Pow2(int y) => Pow(2, y); } public class MyMathBigInteger { public static BigInteger Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(new BigInteger(1), (acc, x) => acc * x); public static BigInteger Pow10(int y) => Pow(10, y); public static BigInteger Pow2(int y) => Pow(2, y); } } #region Expanded by https://github.com/kzrnm/SourceExpander namespace AtCoder.Internal{public class Barrett{public readonly uint Mod;public readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[MethodImpl(256)]public uint Mul(uint a,uint b)=>Reduce((ulong)a*b);[MethodImpl(256)]public uint Reduce(ulong z){var x=Mul128.Mul128Bit(z,IM);var y=x*Mod;if(z0){if((n&1)!=0)r=Mul(r,y);y=Mul(y,y);n>>=1;}return r;}}} namespace AtCoder.Internal{public static class Mul128{[MethodImpl(256)]public static ulong Mul128Bit(ulong a,ulong b){if(Bmi2.X64.IsSupported)return Bmi2.X64.MultiplyNoFlags(a,b);return Mul128BitLogic(a,b);}[MethodImpl(256)]internal static ulong Mul128BitLogic(ulong a,ulong b){var au=a>>32;var ad=a&0xFFFFFFFF;var bu=b>>32;var bd=b&0xFFFFFFFF;var l=ad*bd;var m1=au*bd;var m2=ad*bu;var h=au*bu;var lu=l>>32;var m1d=m1&0xFFFFFFFF;var m2d=m2&0xFFFFFFFF;var c=m1d+m2d+lu;return h+(m1>>32)+(m2>>32)+(c>>32);}}} namespace AtCoder.Internal{public static class ModCalc{[MethodImpl(256)]public static long InvMod(long x,long m){var(g,res)=InvGcd(x,m);return res;}[MethodImpl(256)]public static(long,long)InvGcd(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}[MethodImpl(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[MethodImpl(256)]public static uint PowMod(long x,long n,int m){if(m==1)return 0;return new Barrett((uint)m).Pow(x,n);}[MethodImpl(256)]public static(long y,long z)Crt(long[]r,long[]m){long r0=0,m0=1;for(int i=0;i:INumberBasewhere T:INumberBase{T Inv();T Pow(ulong n);int Value{get;}abstract static int Mod{get;}}public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}} namespace AtCoder{public readonly struct StaticModInt:IEquatable>,IFormattable,IModInt>where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;public static StaticModIntZero=>default;public static StaticModIntOne=>new StaticModInt(1u);[MethodImpl(256)]public static StaticModIntRaw(int v){var u=unchecked((uint)v);return new StaticModInt(u);}[MethodImpl(256)]public StaticModInt(long v):this((uint)ModCalc.SafeMod(v,op.Mod)){}[MethodImpl(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[MethodImpl(256)]private StaticModInt(uint v)=>_v=v;[MethodImpl(256)]public static StaticModIntoperator ++(StaticModIntv){var x=v._v+1;if(x==op.Mod){x=0;}return new StaticModInt(x);}[MethodImpl(256)]public static StaticModIntoperator --(StaticModIntv){var x=v._v;if(x==0){x=op.Mod;}return new StaticModInt(x-1);}[MethodImpl(256)]public static StaticModIntoperator+(StaticModIntlhs,StaticModIntrhs){var v=lhs._v+rhs._v;if(v>=op.Mod){v-=op.Mod;}return new StaticModInt(v);}[MethodImpl(256)]public static StaticModIntoperator-(StaticModIntlhs,StaticModIntrhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod){v+=op.Mod;}return new StaticModInt(v);}}[MethodImpl(256)]public static StaticModIntoperator*(StaticModIntlhs,StaticModIntrhs)=>new StaticModInt((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModIntoperator/(StaticModIntlhs,StaticModIntrhs)=>lhs*rhs.Inv();[MethodImpl(256)]public static StaticModIntoperator+(StaticModIntv)=>v;[MethodImpl(256)]public static StaticModIntoperator-(StaticModIntv)=>new StaticModInt(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public static bool operator==(StaticModIntlhs,StaticModIntrhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModIntlhs,StaticModIntrhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt(int v)=>new StaticModInt(v);[MethodImpl(256)]public static implicit operator StaticModInt(uint v)=>new StaticModInt((ulong)v);[MethodImpl(256)]public static implicit operator StaticModInt(long v)=>new StaticModInt(v);[MethodImpl(256)]public static implicit operator StaticModInt(ulong v)=>new StaticModInt(v);[MethodImpl(256)]public StaticModIntPow(long n){return Pow((ulong)n);}[MethodImpl(256)]public StaticModIntPow(ulong n){var x=this;var r=new StaticModInt(1U);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[MethodImpl(256)]public StaticModIntInv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=ModCalc.InvGcd(_v,op.Mod);return new StaticModInt(x);}}public override string ToString()=>_v.ToString();public string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);public override bool Equals(object obj)=>obj is StaticModIntm&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModIntother)=>_v==other._v;public override int GetHashCode()=>_v.GetHashCode();public static bool TryParse(ReadOnlySpans,out StaticModIntresult){result=Zero;StaticModIntten=10u;s=s.Trim();bool minus=false;if(s.Length>0&&s[0]=='-'){minus=true;s=s.Slice(1);}for(int i=0;i=10)return false;result=result*ten+d;}if(minus)result=-result;return true;}public static StaticModIntParse(ReadOnlySpans){if(!TryParse(s,out var r))Throw();return r;void Throw()=>throw new FormatException();}static int INumberBase>.Radix=>2;static StaticModIntIAdditiveIdentity,StaticModInt>.AdditiveIdentity=>default;static StaticModIntIMultiplicativeIdentity,StaticModInt>.MultiplicativeIdentity=>new StaticModInt(1u);static StaticModIntINumberBase>.Abs(StaticModIntv)=>v;static bool INumberBase>.IsCanonical(StaticModIntv)=>true;static bool INumberBase>.IsComplexNumber(StaticModIntv)=>false;static bool INumberBase>.IsRealNumber(StaticModIntv)=>true;static bool INumberBase>.IsImaginaryNumber(StaticModIntv)=>false;static bool INumberBase>.IsEvenInteger(StaticModIntv)=>uint.IsEvenInteger(v._v);static bool INumberBase>.IsOddInteger(StaticModIntv)=>uint.IsOddInteger(v._v);static bool INumberBase>.IsFinite(StaticModIntv)=>true;static bool INumberBase>.IsInfinity(StaticModIntv)=>false;static bool INumberBase>.IsInteger(StaticModIntv)=>true;static bool INumberBase>.IsPositive(StaticModIntv)=>true;static bool INumberBase>.IsNegative(StaticModIntv)=>false;static bool INumberBase>.IsPositiveInfinity(StaticModIntv)=>false;static bool INumberBase>.IsNegativeInfinity(StaticModIntv)=>false;static bool INumberBase>.IsNormal(StaticModIntv)=>v._v!=0;static bool INumberBase>.IsSubnormal(StaticModIntv)=>false;static bool INumberBase>.IsZero(StaticModIntv)=>v._v==0;static bool INumberBase>.IsNaN(StaticModIntv)=>false;static StaticModIntINumberBase>.MaxMagnitude(StaticModIntx,StaticModInty)=>new StaticModInt(uint.Max(x._v,y._v));static StaticModIntINumberBase>.MaxMagnitudeNumber(StaticModIntx,StaticModInty)=>new StaticModInt(uint.Max(x._v,y._v));static StaticModIntINumberBase>.MinMagnitude(StaticModIntx,StaticModInty)=>new StaticModInt(uint.Min(x._v,y._v));static StaticModIntINumberBase>.MinMagnitudeNumber(StaticModIntx,StaticModInty)=>new StaticModInt(uint.Min(x._v,y._v));static StaticModIntINumberBase>.Parse(ReadOnlySpans,NumberStyles style,IFormatProvider provider)=>Parse(s);static StaticModIntINumberBase>.Parse(string s,NumberStyles style,IFormatProvider provider)=>Parse(s);static StaticModIntISpanParsable>.Parse(ReadOnlySpans,IFormatProvider provider)=>Parse(s);static StaticModIntIParsable>.Parse(string s,IFormatProvider provider)=>Parse(s);static bool ISpanParsable>.TryParse(ReadOnlySpans,IFormatProvider provider,out StaticModIntresult)=>TryParse(s,out result);static bool IParsable>.TryParse(string s,IFormatProvider provider,out StaticModIntresult)=>TryParse(s,out result);static bool INumberBase>.TryParse(ReadOnlySpans,NumberStyles style,IFormatProvider provider,out StaticModIntresult)=>TryParse(s,out result);static bool INumberBase>.TryParse(string s,NumberStyles style,IFormatProvider provider,out StaticModIntresult)=>TryParse(s,out result);bool ISpanFormattable.TryFormat(Spandestination,out int charsWritten,ReadOnlySpanformat,IFormatProvider provider)=>_v.TryFormat(destination,out charsWritten,format,provider);static bool INumberBase>.TryConvertFromChecked(TOther v,out StaticModIntr){if(WrapChecked(v,out long l)){r=l;return true;}if(WrapChecked(v,out ulong u)){r=u;return true;}r=default;return false;}static bool INumberBase>.TryConvertFromSaturating(TOther v,out StaticModIntr){if(WrapSaturating(v,out long l)){r=l;return true;}if(WrapSaturating(v,out ulong u)){r=u;return true;}r=default;return false;}static bool INumberBase>.TryConvertFromTruncating(TOther v,out StaticModIntr){if(WrapTruncating(v,out long l)){r=l;return true;}if(WrapTruncating(v,out ulong u)){r=u;return true;}r=default;return false;}static bool INumberBase>.TryConvertToChecked(StaticModIntv,out TOther r)where TOther:default=>WrapChecked(v._v,out r);static bool INumberBase>.TryConvertToSaturating(StaticModIntv,out TOther r)where TOther:default=>WrapSaturating(v._v,out r);static bool INumberBase>.TryConvertToTruncating(StaticModIntv,out TOther r)where TOther:default=>WrapTruncating(v._v,out r);[MethodImpl(256)]static bool WrapChecked(TFrom v,out TTo r)where TFrom:INumberBasewhere TTo:INumberBase =>typeof(TFrom)==typeof(TTo)?(r=(TTo)(object)v)is{}:TTo.TryConvertFromChecked(v,out r)||TFrom.TryConvertToChecked(v,out r);[MethodImpl(256)]static bool WrapSaturating(TFrom v,out TTo r)where TFrom:INumberBasewhere TTo:INumberBase =>typeof(TFrom)==typeof(TTo)?(r=(TTo)(object)v)is{}:TTo.TryConvertFromSaturating(v,out r)||TFrom.TryConvertToSaturating(v,out r);[MethodImpl(256)]static bool WrapTruncating(TFrom v,out TTo r)where TFrom:INumberBasewhere TTo:INumberBase =>typeof(TFrom)==typeof(TTo)?(r=(TTo)(object)v)is{}:TTo.TryConvertFromTruncating(v,out r)||TFrom.TryConvertToTruncating(v,out r);}} namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander