CodeForcesTemplate.md
```cs
using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
using System.Text;
using System.Data;
using System.ComponentModel;
using System.Security.AccessControl;
internal class Program
{
private static void Main(string[] args)
{
#if Sigma
using TextReader textReader = File.OpenText("input.txt");
Console.SetIn(textReader);
DateTime lastNow = DateTime.Now;
#endif
Prepare();
int t = 1;
t = InputInt();
for (int i = 0; i < t; i++)
{
MainProblem();
}
#if Sigma
Console.WriteLine($"---");
Console.WriteLine($"Выполненно за {(DateTime.Now - lastNow).TotalMilliseconds} мс");
#endif
}
internal static int Mod = 10_000_007;
private static void Prepare()
{
}
private static void MainProblem()
{
}
#region Пресеты
private static int Gcd(int a, int b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a | b;
}
private static long Gcd(long a, long b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a | b;
}
private static ulong Gcd(ulong a, ulong b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a | b;
}
private static ulong PositiveIntPow(ulong x, int pow)
{
ulong ret = 1;
pow = Math.Abs(pow);
while (pow != 0)
{
if ((pow & 1) == 1)
ret *= x;
x *= x;
pow >>= 1;
}
return ret;
}
private static ulong ActualBitsNOT(ulong number)
{
if (number == 0 || BitOperations.IsPow2(number))
{
return number - 1;
}
else
{
ulong mask = BitOperations.RoundUpToPowerOf2(number) - 1;
return ~number & mask;
}
}
private static ulong GetMaxBit(ulong number)
{
if (number == 0)
return 0;
return 1UL << BitOperations.Log2(number);
}
private static ulong ChangeFlag(ulong value, ulong mask)
{
return value ^ mask;
}
private static ulong GetFlag(ulong value, ulong mask)
{
return value & mask;
}
private static ulong SetFlag(ulong value, ulong mask)
{
return value | mask;
}
private static ulong RemoveFlag(ulong value, ulong mask)
{
return value & ~mask;
}
private static bool HasFlag(ulong value, ulong mask)
{
return GetFlag(value, mask) != 0;
}
private static string RepeatString(string text, int n)
{
var textAsSpan = text.AsSpan();
var span = new Span(new char[textAsSpan.Length * n]);
for (var i = 0; i < n; i++)
{
textAsSpan.CopyTo(span.Slice(i * textAsSpan.Length, textAsSpan.Length));
}
return span.ToString();
}
private static (T, int, T, int) MinIndexMaxIndex(T[] arr)
where T : IComparable
{
int minIndex = int.MaxValue, maxIndex = int.MinValue;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].CompareTo(arr[minIndex]) < 0)
minIndex = i;
if (arr[i].CompareTo(arr[maxIndex]) > 0)
maxIndex = i;
}
return (arr[minIndex], minIndex, arr[maxIndex], maxIndex);
}
private static void Swap(ref T left, ref T right)
{
T temp = left;
left = right;
right = temp;
}
private static int NumberCharToInt(char c)
{
return (int)(c) - 48;
}
private static char IntToNumberChar(int c)
{
return (char)(c + 48);
}
private static int[] PrefixSum(int[] arr)
{
int[] newArr = new int[arr.Length + 1];
newArr[0] = 0;
for (long i = 0; i < arr.Length; i++)
{
newArr[i + 1] = arr[i] + newArr[i];
}
return newArr;
}
private static long[] PrefixSum(long[] arr)
{
long[] newArr = new long[arr.Length + 1];
newArr[0] = 0;
for (long i = 0; i < arr.Length; i++)
{
newArr[i + 1] = arr[i] + newArr[i];
}
return newArr;
}
private static ulong[] PrefixSum(ulong[] arr)
{
ulong[] newArr = new ulong[arr.Length + 1];
newArr[0] = 0;
for (int i = 0; i < arr.Length; i++)
{
newArr[i + 1] = arr[i] + newArr[i];
}
return newArr;
}
private static (T, T) InputTuple2(Func parser)
{
var array = InputArray(parser);
return (array[0], array[1]);
}
private static (T, T, T) InputTuple3(Func parser)
{
var array = InputArray(parser);
return (array[0], array[1], array[3]);
}
private static (T, T, T, T) InputTuple4(Func parser)
{
var array = InputArray(parser);
return (array[0], array[1], array[3], array[4]);
}
private static int[] InputIntArray(bool length = false)
{
return InputArray(int.Parse, length);
}
private static long[] InputLongArray(bool length = false)
{
return InputArray(long.Parse, length);
}
private static ulong[] InputULongArray(bool length = false)
{
return InputArray(ulong.Parse, length);
}
private static IEnumerable InputEnumerable(Func parser)
{
return Console.ReadLine()!.Split(' ').Select(parser);
}
private static T[] InputArray(Func parser, bool length = false)
{
if (length)
Console.ReadLine();
return InputEnumerable(parser).ToArray();
}
private static List InputList(Func parser, bool length = false)
{
if (length)
Console.ReadLine();
return InputEnumerable(parser).ToList();
}
private static char[] InputString()
{
return Console.ReadLine()!.ToCharArray();
}
private static int InputInt()
{
return int.Parse(Console.ReadLine()!);
}
private static long InputLong()
{
return long.Parse(Console.ReadLine()!);
}
private static ulong InputULong()
{
return ulong.Parse(Console.ReadLine()!);
}
private static void Yes()
{
Console.WriteLine("YES");
}
private static void No()
{
Console.WriteLine("NO");
}
private static void PrintEnumerable(IEnumerable enumerable)
{
Console.WriteLine(string.Join(' ', enumerable));
}
private static void PrintString(char[] enumerable)
{
Console.WriteLine(new string(enumerable));
}
#endregion
}
public struct MInt32
{
private int value;
public MInt32(int val)
{
value = val % Program.Mod;
}
public static implicit operator MInt32(int number)
{
return new MInt32(number);
}
public static implicit operator int(MInt32 mint)
{
return mint.value;
}
public static MInt32 operator+(MInt32 l, MInt32 r)
{
return l.value + r.value;
}
public static MInt32 operator-(MInt32 l, MInt32 r)
{
return (l.value - r.value) + Program.Mod;
}
public static MInt32 operator*(MInt32 l, MInt32 r)
{
return (int)((1L * l.value * r.value) % Program.Mod);
}
}
```