using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Collections;
using System.Text;
using System.Text.RegularExpressions;
using static Tmpl;
using static CPDebug;
using System.Collections.Specialized;
using System.Globalization;
using System.Diagnostics;

StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
//using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite));
Console.SetOut(writer);
//using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open));
//Console.SetIn(reader);

Solver.Solve();

Console.Out.Flush();

public static class Solver
{
    private static readonly CPIO cin = new CPIO();

    public static unsafe void Solve()
    {
        int N = cin.Int();
        int M = cin.Int();
        long T = cin.Long();

        SquareMatrix<MP> mat = SquareMatrix<MP>.Zero(N);

        for (int i = 0; i < M; i++)
        {
            int a = cin.Int();
            int b = cin.Int();

            mat[b, a] = new(1);
        }

        SquareMatrix<MP> power = mat.Power(T);

        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            if (power[i, 0].Value == 1) ans++;
        }

        print(ans);
    }
}

public struct MP : IAdditionOperators<MP, MP, MP>, IMultiplyOperators<MP, MP, MP>, IAdditiveIdentity<MP, MP>, IMultiplicativeIdentity<MP, MP>, IEqualityOperators<MP, MP, bool>
{
    public static MP AdditiveIdentity => new(0);
    public static MP MultiplicativeIdentity => new(1);


    public long Value;

    public MP(long v)
    {
        Value = v;
    }

    public static MP operator +(MP a, MP b)
    {
        return new(a.Value | b.Value);
    }

    public static MP operator *(MP a, MP b)
    {
        return new MP(a.Value & b.Value);
    }

    public static bool operator ==(MP a, MP b) => a.Value == b.Value;
    public static bool operator !=(MP a, MP b) => a.Value != b.Value;

    public override bool Equals([NotNullWhen(true)] object obj)
    {
        if (obj is MP m) return this == m;
        else return false;
    }

    public override int GetHashCode()
    {
        return base.GetHashCode();
    }

    public override string ToString()
    {
        return Value.ToString();
    }
}

public sealed class SquareMatrix<T> : IEquatable<SquareMatrix<T>>
                                    where T :
                                    IAdditionOperators<T, T, T>,
                                    IMultiplyOperators<T, T, T>,
                                    IAdditiveIdentity<T, T>,
                                    IMultiplicativeIdentity<T, T>,
                                    IEqualityOperators<T, T, bool>
{
    private T[,] _m;
    private int _size;

    public T this[int r, int c]
    {
        get
        {
            return _m[r, c];
        }
        set
        {
            _m[r, c] = value;
        }
    }

    public T[,] M => _m;
    public int Size => _size;

    private SquareMatrix(int size)
    {
        if (size <= 0)
        {
            throw new InvalidOperationException();
        }

        _size = size;
        _m = new T[size, size];
    }

    public static SquareMatrix<T> operator +(SquareMatrix<T> left, SquareMatrix<T> right)
    {
        if (left.Size != right.Size)
        {
            throw new InvalidOperationException();
        }
        SquareMatrix<T> dest = Zero(left.Size);

        for (int r = 0; r < left.Size; r++)
        {
            for (int c = 0; c < left.Size; c++)
            {
                dest[r, c] = left[r, c] + right[r, c];
            }
        }

        return dest;
    }

    public static SquareMatrix<T> operator *(SquareMatrix<T> left, SquareMatrix<T> right)
    {
        if (left.Size != right.Size)
        {
            throw new InvalidOperationException();
        }

        SquareMatrix<T> result = Zero(left.Size);

        for (int r = 0; r < result.Size; r++)
        {
            for (int c = 0; c < result.Size; c++)
            {
                for (int i = 0; i < result.Size; i++)
                {
                    result[r, c] += right[i, c] * left[r, i];
                }
            }
        }

        return result;
    }

    public SquareMatrix<T> Power(long exp)
    {
        if (exp == 0) return Identity(_size);
        if (exp == 1) return this;

        SquareMatrix<T> half = Power(exp / 2);
        SquareMatrix<T> res = half * half;
        if (exp % 2 == 1) res *= this;

        return res;
    }

    public SquareMatrix<T> Transpose()
    {
        SquareMatrix<T> result = new(_size);

        for (int i = 0; i < _size; i++)
        {
            for (int j = 0; j < _size; j++)
            {
                result[j, i] = this[i, j];
            }
        }

        return result;
    }

    public static SquareMatrix<T> Zero(int size)
    {
        SquareMatrix<T> result = new SquareMatrix<T>(size);

        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                result[i, j] = T.AdditiveIdentity;
            }
        }

        return result;
    }

    public static SquareMatrix<T> Identity(int size)
    {
        SquareMatrix<T> result = new SquareMatrix<T>(size);

        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (i == j) result[i, j] = T.MultiplicativeIdentity;
                else result[i, j] = T.AdditiveIdentity;
            }
        }

        return result;
    }

    public bool Equals(SquareMatrix<T> other)
    {
        if (_size != other.Size) return false;

        for (int i = 0; i < _size; i++)
        {
            for (int j = 0; j < _size; j++)
            {
                if (this[i, j] != other[i, j]) return false;
            }
        }

        return true;
    }

    public override bool Equals(object obj)
    {
        if (obj is SquareMatrix<T> mat)
        {
            return Equals(mat);
        }
        else
            return false;
    }

    public override int GetHashCode()
    {
        return base.GetHashCode();
    }

    public static bool operator ==(SquareMatrix<T> a, SquareMatrix<T> b) => a.Equals(b);
    public static bool operator !=(SquareMatrix<T> a, SquareMatrix<T> b) => !a.Equals(b);

    public override string ToString()
    {
        int[] maxwidths = new int[_size];
        for (int i = 0; i < _size; i++)
        {
            for (int j = 0; j < _size; j++)
            {
                maxwidths[j] = int.Max(maxwidths[j], _m[i, j].ToString().Length);
            }
        }

        StringBuilder sb = new();

        for (int i = 0; i < _size; i++)
        {
            sb.Append('|');
            sb.Append(' ');
            for (int j = 0; j < _size; j++)
            {
                sb.Append(_m[i, j].ToString().PadRight(maxwidths[j], ' '));
                if (j < _size - 1) sb.Append(' ');
            }
            sb.Append(' ');
            sb.Append('|');
            if (i < _size - 1)
                sb.Append(Environment.NewLine);
        }

        return sb.ToString();
    }
}

public readonly struct Point
{
    public readonly int X;
    public readonly int Y;

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public override int GetHashCode() => (X, Y).GetHashCode();

    public override string ToString()
    {
        return $"({X}, {Y})";
    }
}

public sealed class ReverseComparer<T> : IComparer<T>
{
    public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(Comparer<T>.Default);

    public static ReverseComparer<T> Reverse(IComparer<T> comparer)
    {
        return new ReverseComparer<T>(comparer);
    }

    private readonly IComparer<T> comparer = Default;

    private ReverseComparer(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public int Compare(T x, T y)
    {
        return comparer.Compare(y, x);
    }
}

/// <summary>
/// Standard input reader for competitive programming.
/// </summary>
public sealed class CPIO
{
    Queue<string> _readQueue = new Queue<string>();

    static CPIO()
    {
        // faster standard output
        StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(writer);
    }

    private void LoadQueue()
    {
        if (_readQueue.Count > 0) return;
        string line = Console.ReadLine();
        string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void Guard()
    {
        if (_readQueue.Count == 0)
        {
            throw new Exception("Standard input queue was empty.");
        }
    }

    public int Int()
    {
        LoadQueue();
        Guard();
        return int.Parse(_readQueue.Dequeue());
    }

    public long Long()
    {
        LoadQueue();
        Guard();
        return long.Parse(_readQueue.Dequeue());
    }

    public string String()
    {
        LoadQueue();
        Guard();
        return _readQueue.Dequeue();
    }

    public short Short()
    {
        LoadQueue();
        Guard();
        return short.Parse(_readQueue.Dequeue());
    }

    public byte Byte()
    {
        LoadQueue();
        Guard();
        return byte.Parse(_readQueue.Dequeue());
    }

    public char Char()
    {
        LoadQueue();
        Guard();
        return char.Parse(_readQueue.Dequeue());
    }

    public double Double()
    {
        LoadQueue();
        Guard();
        return double.Parse(_readQueue.Dequeue());
    }

    public float Float()
    {
        LoadQueue();
        Guard();
        return float.Parse(_readQueue.Dequeue());
    }

    public T Read<T>()
    {
        Type type = typeof(T);
        if (type == typeof(int)) return (T)(object)Int();
        else if (type == typeof(long)) return (T)(object)Long();
        else if (type == typeof(float)) return (T)(object)Float();
        else if (type == typeof(double)) return (T)(object)Double();
        else if (type == typeof(short)) return (T)(object)Short();
        else if (type == typeof(byte)) return (T)(object)Byte();
        else if (type == typeof(char)) return (T)(object)Char();
        else if (type == typeof(string)) return (T)(object)String();
        else return default(T);
    }

    public int[] IntArray(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int();
        }

        return arr;
    }

    public int[] ZeroIndexedPermutation(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int() - 1;
        }

        return arr;
    }

    public long[] LongArray(int n)
    {
        if (n == 0) return Array.Empty<long>();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Long();
        }

        return arr;
    }

    public double[] DoubleArray(int n)
    {
        if (n == 0) return Array.Empty<double>();

        double[] arr = new double[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Double();
        }

        return arr;
    }

    public string[] StringArray(int n)
    {
        if (n == 0) return Array.Empty<string>();

        string[] arr = new string[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = String();
        }

        return arr;
    }

    public T[] ReadArray<T>(int n)
    {
        if (n == 0) return Array.Empty<T>();

        T[] arr = new T[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Read<T>();
        }

        return arr;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void YesNo(bool t)
    {
        Console.WriteLine(t ? "Yes" : "No");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Print<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        Console.WriteLine(string.Join(delimiter, array));
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Print(string value) => Console.WriteLine(value);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Print(int value) => Console.WriteLine(value);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Print(long value) => Console.WriteLine(value);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Print(double value, int digits = 10) => Console.WriteLine(Math.Round(value, digits).ToString());
}

public static class CPDebug
{
    public static void check<T>(T value, [CallerArgumentExpression(nameof(value))] string name = "value") where T : struct
    {
#if DEBUG
        Console.Error.WriteLine($"[DEBUG] {name}={value.ToString()}");
#endif
    }

    public static void check<T>(IEnumerable<T> value, [CallerArgumentExpression(nameof(value))] string name = "value")
    {
#if DEBUG
        Console.Error.WriteLine($"[DEBUG] {name}=({string.Join(' ', value)})");
#endif
    }
}

public static class Tmpl
{
    public static long pow(long b, long exp)
    {
        if (exp == 0) return 1;
        if (exp == 1) return b;

        long m = pow(b, exp / 2L);
        m *= m;
        if (exp % 2L == 1) m *= b;

        return m;
    }

    public static long modpow(long b, long exp, long mod)
    {
        if (exp == 0) return 1;
        if (exp == 1) return b % mod;

        long m = modpow(b, exp / 2L, mod);
        m *= m;
		m %= mod;
        if (exp % 2L == 1) m *= b % mod;
        m %= mod;

        return m;
    }

	static long modinv( long a, long mod )
	{
		long b = mod, u = 1, v = 0;
		while ( b > 0 )
		{
			long t = a / b;
			a -= t * b; swap( ref a, ref b );
			u -= t * v; swap( ref u, ref v );
		}
		u %= mod;
		if (u < 0) u += mod;
		return u;
	}

    public static long calcLcm(long a, long b)
    {
        return a * b / calcGcd(a, b);
    }

    public static long calcGcd(long a, long b)
    {
        if (a % b == 0) return b;
        return calcGcd(b, a % b);
    }

    // ax ≡ b (mod m)なる最小のxを求める
    public static bool solveModLinear(long a, long b, long m, out long minSolution)
    {
        long gcd = calcGcd(calcGcd(a, b), m);
        a /= gcd;
        b /= gcd;
        m /= gcd;
        if (calcGcd(a, m) == 1)
        {
            long inv = modinv(a, m);
            minSolution = (b * inv) % m;
            return true;
        }
        minSolution = 0;
        return false;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void YesNo(bool t)
    {
        Console.WriteLine(t ? "Yes" : "No");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void YESNO(bool t)
    {
        Console.WriteLine(t ? "YES" : "NO");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void yesno(bool t)
    {
        Console.WriteLine(t ? "yes" : "no");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool checkBit(int bit, int n)
    {
        return ((1 << n) & bit) != 0;
    }

    public static bool nextSubset(ref int set, int super)
    {
        set = (set - 1) & super;
        return set != 0;
    }

    public static bool nextCombination(int n, int r, int[] array)
    {
        int i = array.Length - 1;
        while (i >= 0 && array[i] == i + n - r)
        {
            i--;
        }

        if (i < 0) return false;

        array[i]++;
        for (int j = i + 1; j < r; j++)
        {
            array[j] = array[j - 1] + 1;
        }

        return true;
    }

    public static bool nextPermutation<T>(T[] array, int start, int length) where T : IComparable<T>
    {
        int end = start + length - 1;

        if (end <= start) return false;

        int last = end;
        while (true)
        {
            int pos = last--;
            
            if (array[last].CompareTo(array[pos]) < 0)
            {
                int i;
                for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }
                T tmp = array[last]; array[last] = array[i]; array[i] = tmp;
                Array.Reverse(array, pos, end - pos + 1);
                return true;
            }
            if (last == start)
            {
                Array.Reverse(array, start, end - start);
                return false;
            }
        }

        throw new Exception("NextPermutation: Fatal error");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool chmax<T> (ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        if (value > target)
        {
            target = value;
            return true;
        }
        return false;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool chmin<T>(ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        if (value < target)
        {
            target = value;
            return true;
        }
        return false;
    }

    public static ReadOnlySpan<T> spanOf<T>(List<T> list)
    {
        return CollectionsMarshal.AsSpan(list);
    }

    public static int lowerBound<T>(T[] array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
    { 
        int low = start;
        int high = end;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid;
        }

        if (low == array.Length - 1 && array[low] < value)
        {
            return array.Length;
        }
        return low;
    }

    public static int lowerBound<T>(List<T> array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
    { 
        int low = start;
        int high = end;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid;
        }

        if (low == array.Count - 1 && array[low] < value)
        {
            return array.Count;
        }
        return low;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void swap<T>(ref T a, ref T b) where T : struct
    {
        T temp = a;
        a = b;
        b = temp;
    }

    public static int[] compressCoords<T>(T[] a) where T : struct, IComparisonOperators<T, T, bool>
    {
        T[] b = a.OrderBy(x => x).Distinct().ToArray();
        int[] result = new int[a.Length];

        for (int i = 0; i < a.Length; i++)
        {
            result[i] = lowerBound(b, 0, b.Length - 1, a[i]);
        }

        return result;
    }

    public static List<RunLengthElement<T>> compressRunLength<T>(T[] array) where T : struct, IEquatable<T>
    {
        List<RunLengthElement<T>> list = new List<RunLengthElement<T>>();

        int count = 1;
        int start = 0;
        T prev = array[0];

        for (int i = 1; i < array.Length; i++)
        {
            if (prev.Equals(array[i]))
            {
                count++;
            }
            else
            {
                list.Add(new RunLengthElement<T>(start, count, prev));
                start = i;
                count = 1;
            }

            prev = array[i];
        }

        list.Add(new RunLengthElement<T>(start, count, prev));

        return list;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        Console.WriteLine(string.Join(delimiter, array));
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        print(array);
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(string msg)
    {
        Console.WriteLine(msg);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(string msg)
    {
        Console.WriteLine(msg);
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(int val)
    {
        print(val.ToString());
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(long val)
    {
        print(val.ToString());
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print<T>(ModInt<T> val) where T : struct, IMod
    {
        print(val.ToString());
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(int val)
    {
        print(val.ToString());
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(long val)
    {
        print(val.ToString());
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint<T>(ModInt<T> val) where T : struct, IMod
    {
        fprint(val.ToString());
        Console.Out.Flush();
    }

    public static void print<T>(T[,] grid)
    {
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                Console.Write(grid[y, x] + "\t");
            }
            Console.WriteLine();
        }
    }

    public static void print01(bool t)
    {
        Console.WriteLine(t ? "1" : "0");
    }

    public static TSrc lowerBoundKth<TSrc, TCnt>(TSrc min, TSrc max, Func<TSrc, TCnt> f, TCnt bound)
        where TSrc: struct, INumber<TSrc> where TCnt: struct, INumber<TCnt>
    {
        TSrc left = min;
        TSrc right = max;
        TSrc two = TSrc.CreateChecked(2);
        TSrc one = TSrc.CreateChecked(1);
        while (right > left)
        {
            TSrc mid = left + (right - left) / two;
            TCnt c = f(mid);
            if (c < bound)
            {
                left = mid + one;
            }
            else
            {
                right = mid;
            }
        }

        return left;
    }

    public static bool isSquareNumber(long n)
    {
        long q = (long)Math.Floor(Math.Sqrt(n));
        return q * q == n;
    }

    public static T[][] makeDPTable2D<T>(int length1, int length2, T value)
    {
        bool fill = !default(T).Equals(value);
        T[][] table = new T[length1][];
        for (int i = 0; i < length1; i++)
        {
            table[i] = new T[length2];
            if (fill)
            {
                Array.Fill(table[i], value);
            }
        }

        return table;
    }

    public static T[][][] makeDPTable3D<T>(int length1, int length2, int length3, T value)
    {
        bool fill = !default(T).Equals(value);
        T[][][] table = new T[length1][][];
        for (int i = 0; i < length1; i++)
        {
            table[i] = new T[length2][];
            for (int j = 0; j < length2; j++)
            {
                table[i][j] = new T[length3];
                if (fill)
                {
                    Array.Fill(table[i][j], value);
                }
            }
        }

        return table;
    }
}

public readonly struct RunLengthElement<T> where T : struct
{
    public readonly int Count;
    public readonly int StartIndex;
    public readonly T Value;

    public RunLengthElement(int startIndex, int count, T value)
    {
        this.StartIndex = startIndex;
        this.Count = count;
        this.Value = value;
    }
}

public readonly struct Edge<T> : IEquatable<Edge<T>>, IComparable<Edge<T>> where T : struct, INumber<T>
{
    public readonly int To;
    public readonly int From;
    public readonly T Weight;

    public Edge(int to, T weight)
    {
        this.To = to;
        this.Weight = weight;
    }

    public Edge(int from, int to, T weight)
    {
        this.To = to;
        this.From = from;
        this.Weight = weight;
    }

    public override bool Equals(object obj)
    {
        if (obj is Edge<T> edge)
        {
            return this.Equals(edge);
        }
        else
        {
            return false;
        }
    }

    public int CompareTo(Edge<T> other)
    {
        return Weight.CompareTo(other.Weight);
    }

    public bool Equals(Edge<T> edge)
    {
        return To == edge.To && From == edge.From && Weight == edge.Weight;
    }

    public override int GetHashCode()
    {
        return (To, From, Weight).GetHashCode();
    }

    public static bool operator ==(Edge<T> left, Edge<T> right)
    {
        return left.Equals(right);
    }

    public static bool operator !=(Edge<T> left, Edge<T> right)
    {
        return !left.Equals(right);
    }
}

/// <summary>
/// Integer on F_p. (p: prime)
/// </summary>
/// <typeparam name="T">Modulus.</typeparam>
public readonly struct ModInt<T> : INumber<ModInt<T>>, IMinMaxValue<ModInt<T>>
                                    where T : struct, IMod
{
    public static long Mod => default(T).Mod;

    public readonly uint Value;

    public long ValueLong => Value;

    /// <summary>
    /// Returns 1. Time complexity is O(1).
    /// </summary>
    public static ModInt<T> One { get; } = CreateFast(1);

    /// <summary>
    /// Returns 0. Time complexity is O(1).
    /// </summary>
    public static ModInt<T> Zero { get; } = CreateFast(0);

    public static int Radix => 10;
    public static ModInt<T> MinValue => CreateFast(0);
    public static ModInt<T> MaxValue => CreateFast(default(T).Mod - 1);

    /// <summary>
    /// Returns the additive identity, 0. Time complexity is O(1).
    /// </summary>
    public static ModInt<T> AdditiveIdentity { get; } = CreateFast(0);
    /// <summary>
    /// Returns the multiplicative identity, 1. Time complexity is O(1).
    /// </summary>
    public static ModInt<T> MultiplicativeIdentity { get; } = CreateFast(1);

    public ModInt(long value)
    {
        value %= default(T).Mod;
        if (value < 0) value += default(T).Mod;
        Value = (uint)value;
    }

    public ModInt(uint value)
    {
        value %= default(T).Mod;
        Value = value;
    }

    private ModInt(uint value, bool dummy)
    {
        Value = value;
    }

    /// <summary>
    /// Constructs the modint with the value. Can only be used when 0 <= value < MOD. Maybe slightly faster than implicit cast. Time complexity is O(1).
    /// </summary>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ModInt<T> CreateFast(uint value)
    {
        return new ModInt<T>(value, false);
    }

    /// <summary>
    /// Calculates the power to e. Time complexity is O(loge)
    /// </summary>
    public readonly ModInt<T> Power(long e)
    {
        if (e < 0)
        {
            return Power(-e).Inv();
        }
        else
        {
            ulong res = 1;
            ulong b = Value;
            while (e > 0)
            {
                if ((e & 1) == 1) res = res * b % default(T).Mod;
                b = b * b % default(T).Mod;
                e >>= 1;
            }

            return CreateFast((uint)res);
        }
    }

    /// <summary>
    /// Returns the inverse. Do not call this function when 0. Time complexity is O(logp).
    /// Reference: https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
    /// </summary>
    public readonly ModInt<T> Inv()
    {
        long x = 1, y = 0;
        long x1 = 0, y1 = 1;
        long b = default(T).Mod;
        long a = Value;

        while (b != 0)
        {
            long q = a / b;
            long t = a % b;
            a = b;
            b = t;

            long tx = x - q * x1;
            long ty = y - q * y1;
            x = x1;
            y = y1;
            x1 = tx;
            y1 = ty;
        }

        return new(x);
    }

    [MethodImpl(256)]
    public static ModInt<T> operator +(ModInt<T> left, ModInt<T> right) => CreateFast((left.Value + right.Value) % default(T).Mod);

    [MethodImpl(256)]
    public static ModInt<T> operator +(ModInt<T> self) => self;

    [MethodImpl(256)]
    public static ModInt<T> operator -(ModInt<T> left, ModInt<T> right) => CreateFast(left.Value >= right.Value ? left.Value - right.Value : (left.Value + default(T).Mod) - right.Value);

    [MethodImpl(256)]
    public static ModInt<T> operator -(ModInt<T> self) => CreateFast(default(T).Mod - self.Value);

    [MethodImpl(256)]
    public static ModInt<T> operator *(ModInt<T> left, ModInt<T> right) => CreateFast((uint)((ulong)left.Value * right.Value % default(T).Mod));

    [MethodImpl(256)]
    public static ModInt<T> operator /(ModInt<T> left, ModInt<T> right)
    {
        if (right.Value == 0)
        {
            throw new DivideByZeroException();
        }

        ModInt<T> inv = right.Inv();
        return left * inv;
    }

    public static ModInt<T> operator %(ModInt<T> left, ModInt<T> right)
    {
        throw new NotImplementedException();
    }

    public static bool operator <(ModInt<T> left, ModInt<T> right) => left.Value < right.Value;

    public static bool operator >(ModInt<T> left, ModInt<T> right) => left.Value > right.Value;

    public static bool operator <=(ModInt<T> left, ModInt<T> right) => left.Value <= right.Value;

    public static bool operator >=(ModInt<T> left, ModInt<T> right) => left.Value >= right.Value;

    [MethodImpl(256)]
    public static bool operator ==(ModInt<T> left, ModInt<T> right) => left.Value == right.Value;

    [MethodImpl(256)]
    public static bool operator !=(ModInt<T> left, ModInt<T> right) => !(left == right);

    [MethodImpl(256)]
    public static ModInt<T> operator ++(ModInt<T> self) => CreateFast((self.Value + 1) % default(T).Mod);

    [MethodImpl(256)]
    public static ModInt<T> operator --(ModInt<T> self) => CreateFast((self.Value + default(T).Mod - 1) % default(T).Mod);

    [MethodImpl(256)]
    public bool Equals(ModInt<T> other) => Value == other.Value;

    [MethodImpl(256)]
    public override bool Equals(object other)
    {
        if (other is ModInt<T> m)
        {
            return this == m;
        }
        else return false;
    }

    [MethodImpl(256)]
    public override int GetHashCode() => Value.GetHashCode();

    [MethodImpl(256)]
    public static implicit operator ModInt<T>(long v) => new(v);

    [MethodImpl(256)]
    public static implicit operator ModInt<T>(int v) => new(v);

    public override string ToString() => Value.ToString();

    public string ToString(string format, IFormatProvider provider) => Value.ToString(format, provider);

    #region INumberBase<TSelf> Implementation

    public static ModInt<T> Abs(ModInt<T> value) => value;
    public static bool IsCanonical(ModInt<T> value) => true;
    public static bool IsComplexNumber(ModInt<T> value) => false;
    public static bool IsFinite(ModInt<T> value) => true;
    public static bool IsImaginaryNumber(ModInt<T> value) => false;
    public static bool IsInfinity(ModInt<T> value) => false;
    public static bool IsInteger(ModInt<T> value) => true;
    public static bool IsNaN(ModInt<T> value) => false;
    public static bool IsNegative(ModInt<T> value) => false;
    public static bool IsPositive(ModInt<T> value) => value.Value != 0;
    public static bool IsRealNumber(ModInt<T> value) => true;
    public static bool IsZero(ModInt<T> value) => value.Value == 0;
    public static bool IsEvenInteger(ModInt<T> value) => (value.Value & 1) == 0;
    public static bool IsOddInteger(ModInt<T> value) => (value.Value & 1) == 1;
    public static bool IsPositiveInfinity(ModInt<T> value) => false;
    public static bool IsNegativeInfinity(ModInt<T> value) => false;
    public static bool IsNormal(ModInt<T> value) => false;
    public static bool IsSubnormal(ModInt<T> value) => false;


    public static ModInt<T> MaxMagnitude(ModInt<T> x, ModInt<T> y)
    {
        if (x.Value > y.Value) return x;
        else return y;
    }
    public static ModInt<T> MaxMagnitudeNumber(ModInt<T> x, ModInt<T> y) => MaxMagnitude(x, y);
    public static ModInt<T> MinMagnitude(ModInt<T> x, ModInt<T> y)
    {
        if (x.Value < y.Value) return x;
        else return y;
    }
    public static ModInt<T> MinMagnitudeNumber(ModInt<T> x, ModInt<T> y) => MinMagnitude(x, y);

    public static ModInt<T> CreateChecked<TOther>(TOther value) where TOther : INumberBase<TOther>
        => new(long.CreateChecked(value));
    public static ModInt<T> CreateSaturating<TOther>(TOther value) where TOther : INumberBase<TOther>
        => new(long.CreateSaturating(value));
    public static ModInt<T> CreateTruncating<TOther>(TOther value) where TOther : INumberBase<TOther>
        => new(long.CreateTruncating(value));

    public static ModInt<T> Parse(string s, NumberStyles style, IFormatProvider provider) => Parse(s.AsSpan(), style, provider);

    public static ModInt<T> Parse(ReadOnlySpan<char> s, NumberStyles style, IFormatProvider provider) => new(long.Parse(s, style, provider));

#if NET10_0_OR_GREATER
    public static ModInt<T> Parse(ReadOnlySpan<byte> s, NumberStyles style, IFormatProvider provider) => new(long.Parse(s, style, provider));
#endif

    public static ModInt<T> Parse(string s, IFormatProvider provider) => new(long.Parse(s, provider));

    public static ModInt<T> Parse(ReadOnlySpan<char> s, IFormatProvider provider) => new(long.Parse(s, provider));

#if NET10_0_OR_GREATER
    public bool TryFormat(Span<byte> dest, out int bytesWritten, ReadOnlySpan<char> format, IFormatProvider provider)
    {
        return Value.TryFormat(dest, out bytesWritten, format, provider);
    }
#endif

    public bool TryFormat(Span<char> destination, out int charsWritten, ReadOnlySpan<char> format, IFormatProvider provider)
    {
        return Value.TryFormat(destination, out charsWritten, format, provider);
    }

    public static bool TryParse(ReadOnlySpan<char> s, NumberStyles style, IFormatProvider provider, out ModInt<T> result)
    {
        if (long.TryParse(s, style, provider, out long inner))
        {
            result = new(inner);
            return true;
        }
        else
        {
            result = Zero;
            return false;
        }

    }

    public static bool TryParse(string s, NumberStyles style, IFormatProvider provider, out ModInt<T> result)
    {
        if (long.TryParse(s, style, provider, out long inner))
        {
            result = new(inner);
            return true;
        }
        else
        {
            result = Zero;
            return false;
        }
    }



    public static bool TryParse(ReadOnlySpan<char> s, IFormatProvider provider, out ModInt<T> result)
    {
        if (long.TryParse(s, provider, out long inner))
        {
            result = new(inner);
            return true;
        }
        else
        {
            result = Zero;
            return false;
        }
    }

    public static bool TryParse(string s, IFormatProvider provider, out ModInt<T> result)
    {
        if (long.TryParse(s, provider, out long inner))
        {
            result = new(inner);
            return true;
        }
        else
        {
            result = Zero;
            return false;
        }
    }

    public static bool TryConvertFromChecked<TOther>(TOther value, out ModInt<T> result) where TOther : INumberBase<TOther>
    {
        throw new NotImplementedException();
    }

    public static bool TryConvertFromSaturating<TOther>(TOther value, out ModInt<T> result) where TOther : INumberBase<TOther>
    {
        throw new NotImplementedException();
    }

    public static bool TryConvertFromTruncating<TOther>(TOther value, [MaybeNullWhen(false)] out ModInt<T> result) where TOther : INumberBase<TOther>
    {
        throw new NotImplementedException();
    }

    public static bool TryConvertToChecked<TOther>(ModInt<T> value, [MaybeNullWhen(false)] out TOther result) where TOther : INumberBase<TOther>
    {
        throw new NotImplementedException();
    }

    public static bool TryConvertToSaturating<TOther>(ModInt<T> value, [MaybeNullWhen(false)] out TOther result) where TOther : INumberBase<TOther>
    {
        throw new NotImplementedException();
    }

    public static bool TryConvertToTruncating<TOther>(ModInt<T> value, [MaybeNullWhen(false)] out TOther result) where TOther : INumberBase<TOther>
    {
        throw new NotImplementedException();
    }


    #endregion

    #region INumber<TSelf> Implementation

    public int CompareTo(ModInt<T> other) => Value.CompareTo(other.Value);
    public int CompareTo(object other) => Value.CompareTo(other);


    #endregion
}

/// <summary>
/// Used to specify modulus.
/// </summary>
public interface IMod
{
    public uint Mod { get; }
}

public readonly struct Mod998244353 : IMod { public uint Mod => 998244353; }
public readonly struct Mod1000000007 : IMod { public uint Mod => 1000000007; }
public readonly struct Mod897581057 : IMod { public uint Mod => 897581057; }
public readonly struct Mod880803841 : IMod { public uint Mod => 880803841; }

/// <summary>
/// Segment tree. (Non-recursive, can be used with non-commutative monoid)
/// </summary>
/// <typeparam name="T">Type of values.</typeparam>
public sealed class SegmentTree<T> where T : struct
{
    public delegate T Monoid(T x, T y);

    private int _treeSize;
    private int _dataSize;
    private int _originalDataSize;
    private T[] _data;
    private Monoid _operator;
    private Monoid _update;
    private T _identity;

    public int OriginalDataSize => _originalDataSize;
    public int TreeSize => _treeSize;
    public T Identity => _identity;

    /// <summary>
    /// Gets the value by index. Time complexity is O(1).
    /// </summary>
    public T this[int index]
    {
        get
        {
            return _data[_dataSize - 1 + index];
        }
    }

    /// <summary>
    /// Builds the segment tree. Time complexity is O(n).
    /// </summary>
    public SegmentTree(int n, Monoid op, Monoid update, T identity)
    {
        _originalDataSize = n;

        int size = 1;
        while (n > size)
        {
            size <<= 1;
        }

        _dataSize = size;
        _treeSize = 2 * size - 1;

        _data = new T[_treeSize];
        Array.Fill(_data, identity);
        _identity = identity;
        _operator = op;
        _update = update;
    }

    /// <summary>
    /// Rebuild the segment tree from the array. Time complexity is O(n).
    /// Since the time complexity of n Update() calls is O(nlogn), when initializing the segment tree with an array, 
    /// call this function to make it faster.
    /// </summary>
    public void Build(T[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            _data[i + _dataSize - 1] = array[i];
        }

        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }

    public void UpdateByArray(T[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            _data[i + _dataSize - 1] = _update(_data[i + _dataSize - 1], array[i]);
        }

        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }

    /// <summary>
    /// Fill the array with the uniform value. Time complexity is O(n).
    /// </summary>
    public void Fill(T value)
    {
        for (int i = 0; i < _originalDataSize; i++)
        {
            _data[i + _dataSize - 1] = value;
        }

        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }

    /// <summary>
    /// Update the value at the specified position. Time complexity is O(logn).
    /// </summary>
    public void Update(int index, T value)
    {
        index += _dataSize - 1;
        _data[index] = _update(_data[index], value);

        while (index > 0)
        {
            index = (index - 1) >> 1;
            _data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
        }
    }

    /// <summary>
    /// Gets the product of the range [l, r). Time complexity is O(logn).
    /// </summary>
    public T Fold(int l, int r)
    {
        l += _dataSize - 1;
        r += _dataSize - 1;

        T leftFold = _identity;
        T rightFold = _identity;
        while (l < r)
        {
            if ((l & 1) == 0)
            {
                leftFold = _operator(leftFold, _data[l]);
                l++;
            }
            if ((r & 1) == 0)
            {
                r--;
                rightFold = _operator(_data[r], rightFold);
            }

            l = (l - 1) >> 1;
            r = (r - 1) >> 1;
        }

        return _operator(leftFold, rightFold);
    }

    /// <summary>
    /// Returns the span of the underlying data. Time complexity is O(1).
    /// </summary>
    public ReadOnlySpan<T> AsSpan()
    {
        return _data.AsSpan(_dataSize - 1, _originalDataSize);
    }
}

/// <summary>
/// Segment Tree with lazy evaluation. (Recursive, can be used with non-commutative monoid)
/// </summary>
public sealed class LazySegmentTree<T, M> where T : struct, IEquatable<T> where M : struct, IEquatable<M>
{
    public delegate T Monoid(T x, T y);
    public delegate M Composition(M x, M y);
    public delegate T Mapping(T x, M y, int l);

    private int _treeSize;
    private int _dataSize;
    private int _originalDataSize;
    private T[] _data;
    private M?[] _lazy;
    private Monoid _operator;
    private Mapping _mapping;
    private Composition _composition;
    private T _identity;

    /// <summary>
    /// Gets the value by index. Time complexity is O(logn).
    /// </summary>
    public T this[int index]
    {
        get
        {
            return Access(index);
        }
    }

    /// <summary>
    /// Builds the segment tree. Time complexity is O(n).
    /// </summary>
    /// <param name="n">Size of the segment tree.</param>
    /// <param name="op">Binary operation.</param>
    /// <param name="mapping">Mapping function.</param>
    /// <param name="composition">Composition function. composition(x, y) := yox</param>
    /// <param name="identity">Identity.</param>
    public LazySegmentTree(int n, Monoid op, Mapping mapping, Composition composition, T identity)
    {
        _originalDataSize = n;

        int size = 1;
        while (n > size)
        {
            size <<= 1;
        }

        _dataSize = size;
        _treeSize = 2 * size - 1;

        _data = new T[_treeSize];
        _data.AsSpan().Fill(_identity);
        _lazy = new M?[_treeSize];

        _identity = identity;
        _operator = op;
        _mapping = mapping;
        _composition = composition;
    }

    /// <summary>
    /// Rebuild the segment tree from the array. Time complexity is O(n).
    /// Since the time complexity of n Update() calls is O(nlogn), when initializing the segment tree with an array, 
    /// call this function to make it faster.
    /// </summary>
    public void Build(T[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            _data[i + _dataSize - 1] = array[i];
        }

        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }

     /// <summary>
    /// Fill the array with the uniform value. Time complexity is O(n).
    /// </summary>
    public void Fill(T value)
    {
        for (int i = 0; i < _originalDataSize; i++)
        {
            _data[i + _dataSize - 1] = value;
        }

        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }

    private void Evaluate(int index, int l, int r)
    {
        if (_lazy[index] is null)
        {
            return;
        }

        if (index < _dataSize - 1)
        {
            _lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
            _lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
        }

        _data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
        _lazy[index] = null;
    }

    private M GuardComposition(M? a, M? b)
    {
        if (a is null)
        {
            return (M)b;
        }
        else
        {
            return _composition((M)a, (M)b);
        }
    }

    /// <summary>
    /// Update the range [l, r) by m. Time complexity is O(logn).
    /// </summary>
    public void Update(int l, int r, M m)
    {
        if (l == r) return;

        if (0 <= l && l < r && r <= _originalDataSize)
            ApplyRec(l, r, m, 0, 0, _dataSize);
    }
    
    private void ApplyRec(int a, int b, M m, int index, int l, int r)
    {
        Evaluate(index, l, r);

        if (a >= r || b <= l)
        {
            return;
        }

        if (a <= l && r <= b)
        {
            _lazy[index] = GuardComposition(_lazy[index], m);
            Evaluate(index, l, r);
        }
        else
        {
            ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);
            ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);
            _data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
        }
    }

    /// <summary>
    /// Gets the product of the range [l, r). Time complexity is O(logn).
    /// </summary>
    /// <param name="l"></param>
    /// <param name="r"></param>
    /// <returns></returns>
    public T Fold(int l, int r)
    {
        if (l == r) return _identity;

        if (0 <= l && l < r && r <= _originalDataSize)
            return QueryRec(l, r, 0, 0, _dataSize);
        else
            return _identity;
    }

    private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
    {
        Evaluate(index, nodeLeft, nodeRight);

        if (left >= nodeRight || right <= nodeLeft)
        {
            return _identity;
        }

        if (left <= nodeLeft && nodeRight <= right)
        {
            return _data[index];
        }

        T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
        T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);

        return _operator(leftChild, rightChild);
    }

    /// <summary>
    /// Gets the value at the specified index. Time complexity is O(logn).
    /// </summary>
    public T Access(int index)
    {
        if (index < 0 || index >= _originalDataSize)
        {
            throw new Exception("Index is out of range.");
        }

        return AccessRec(index, 0, 0, _dataSize);
    }

    private T AccessRec(int target, int index, int l, int r)
    {
        Evaluate(index, l, r);

        if (index >= _dataSize - 1)
        {
            return _data[index];
        }

        int mid = (l + r) / 2;
        if (target < mid)
        {
            return AccessRec(target, (index << 1) + 1, l, mid);
        }
        else
        {
            return AccessRec(target, (index << 1) + 2, mid, r);
        }
    }

    private void EvaluateAll(int index, int l, int r)
    {
        if (_lazy[index] is null)
        {
            if (index < _dataSize - 1)
            {
                EvaluateAll((index << 1) + 1, l, (l + r) / 2);
                EvaluateAll((index << 1) + 2, (l + r) / 2, r);
            }
            return;
        }

        if (index < _dataSize - 1)
        {
            _lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
            _lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
            EvaluateAll((index << 1) + 1, l, (l + r) / 2);
            EvaluateAll((index << 1) + 2, (l + r) / 2, r);
        }

        _data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
        _lazy[index] = null;
    }

    /// <summary>
    /// Returns the span of the underlying data. Time complexity is O(n).
    /// </summary>
    /// <returns></returns>
    public ReadOnlySpan<T> AsSpan()
    {
        EvaluateAll(0, 0, _dataSize);

        return _data.AsSpan(_dataSize - 1, _originalDataSize);
    }
}

public static class SegmentTreeBuilder
{
    public static LazySegmentTree<T, T> RangeAddMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Max,
        (x, m, l) =>
        {
            return x + m;
        },
        (a, b) => { return a + b; },
        identity);
    }

    public static LazySegmentTree<T, T> RangeUpdateMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Max,
        (x, m, l) =>
        {
            return m;
        },
        (x, y) => { return y; },
        identity);
    }

    public static LazySegmentTree<T, T> RangeAddMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Min,
        (x, m, l) =>
        {
            return x + m;
        },
        (a, b) => { return a + b; },
        identity);
    }

    public static LazySegmentTree<T, T> RangeUpdateMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Min,
        (x, m, l) =>
        {
            return m;
        },
        (x, y) => { return y; },
        identity);
    }

    public static LazySegmentTree<T, T> RangeAddSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, (x, y) => x + y,
        (x, m, l) =>
        {
            return x + m * T.CreateChecked(l);
        },
        (a, b) => { return a + b; },
        identity);
    }

    public static LazySegmentTree<T, T> RangeUpdateSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, (x, y) => x + y,
        (x, m, l) =>
        {
            return m * T.CreateChecked(l);
        },
        (a, b) => { return b; },
        identity);
    }

    public static SegmentTree<T> PointUpdateMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Max, (a, b) => b, identity);
    }

    public static SegmentTree<T> PointAddMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Max, (a, b) => a + b, identity);
    }

    public static SegmentTree<T> PointUpdateMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Min, (a, b) => b, identity);
    }

    public static SegmentTree<T> PointAddMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Min, (a, b) => a + b, identity);
    }

    public static SegmentTree<T> PointUpdateSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => b, identity);
    }

    public static SegmentTree<T> PointAddSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => a + b, identity);
    }
}

public sealed class PrefixSum2D<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>
{
    private T[,] _sums;

    public PrefixSum2D(T[,] sequence)
    {
        int height = sequence.GetLength(0);
        int width = sequence.GetLength(1);

        _sums = new T[height + 1, width + 1];

        // build prefix sum
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                _sums[y + 1, x + 1] = _sums[y + 1, x] + _sums[y, x + 1] - _sums[y, x] + sequence[y, x];
            }
        }
    }

    public T Sum(int startInclX, int startInclY, int endExclX, int endExclY)
    {
        return _sums[endExclY, endExclX] + _sums[startInclY, startInclX] - _sums[startInclY, endExclX] - _sums[endExclY, startInclX];
    }

    public T AllSum()
    {
        return _sums[_sums.GetLength(0) - 1, _sums.GetLength(1) - 1];
    }
}

public sealed class PrefixSum<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IAdditiveIdentity<T, T>
{
    private T[] _sums;

    public PrefixSum(T[] sequence)
    {
        _sums = new T[sequence.Length + 1];

        _sums[0] = T.AdditiveIdentity;
        for (int i = 0; i < sequence.Length; i++)
        {
            _sums[i + 1] = _sums[i] + sequence[i];
        }
    }

    // [a, b)
    public T Sum(int aIncl, int bExcl)
    {
        return _sums[bExcl] - _sums[aIncl];
    }

    public T AllSum()
    {
        return _sums[^1];
    }

    public T[] GetArray()
    {
        return _sums;
    }
}

/// <summary>
/// Union-Find(disjoint set union).
/// </summary>
public sealed class UnionFind
{
    private int[] _parents;
    private int[] _size;
    private int _vertexCount;

    public int VertexCount => _vertexCount;

    public UnionFind(int n)
    {
        _vertexCount = n;
        _parents = new int[n];
        _size = new int[n];
        for (int i = 0; i < n; i++)
        {
            _parents[i] = i;
            _size[i] = 1;
        }
    }

    /// <summary>
    /// Gets the leader(root) of the connected component x belongs to. Time complexity is O(α(n)).
    /// </summary>
    public int Leader(int x)
    {
        if (_parents[x] == x)
            return x;
        return _parents[x] = Leader(_parents[x]);
    }

    /// <summary>
    /// Gets the size of the connected component x belongs to. Time complexity is O(α(n)).
    /// </summary>
    public int Size(int x)
    {
        return _size[Leader(x)];
    }

    /// <summary>
    /// Merge the two connected components. Time complexity is O(α(n)).
    /// </summary>
    public void Unite(int x, int y)
    {
        int rootX = Leader(x);
        int rootY = Leader(y);
        if (rootX == rootY)
            return;
            
        int from = rootX;
        int to = rootY;
        
        // union by size.(small-to-large merging)
        if (_size[from] > _size[to])
        {
            (from, to) = (to, from);
        }

        _size[to] += _size[from];
        _parents[from] = to;
    }

    /// <summary>
    /// Gets the list of vertices which belong to the connected component of x. Time complexity is O(n).
    /// </summary>
    public List<int> GetGroup(int x)
    {
        int rootX = Leader(x);
        List<int> set = new List<int>();
        for (int i = 0; i < _vertexCount; i++)
        {
            if (Leader(i) == rootX)
                set.Add(i);
        }

        return set;
    }

    /// <summary>
    /// Gets the vertex list of all connected components. Time complexity is O(n).
    /// </summary>
    public Dictionary<int, List<int>> FindAll()
    {
        Dictionary<int, List<int>> sets = new Dictionary<int, List<int>>();
        for (int i = 0; i < _vertexCount; i++)
        {
            int root = Leader(i);
            if (sets.ContainsKey(root))
                sets[root].Add(i);
            else
                sets[root] = new List<int>() { i };
        }

        return sets;
    }

    /// <summary>
    /// Determines if the x and y belong to the same connected component. Time complexity is O(α(n)).
    /// </summary>
    public bool Same(int x, int y)
    {
        int rootX = Leader(x);
        int rootY = Leader(y);
        return rootX == rootY;
    }

    /// <summary>
    /// Clears the data. Time complexity is O(n).
    /// </summary>
    public void Clear()
    {
        for (int i = 0; i < _vertexCount; i++)
        {
            _parents[i] = i;
            _size[i] = 1;
        }
    }
}