// ReSharper disable ArrangeTypeMemberModifiers
// ReSharper disable ConvertIfStatementToSwitchStatement
// ReSharper disable EnforceForStatementBraces
// ReSharper disable EnforceIfStatementBraces
// ReSharper disable FieldCanBeMadeReadOnly.Global
// ReSharper disable FunctionRecursiveOnAllPaths
// ReSharper disable InconsistentNaming
// ReSharper disable InlineOutVariableDeclaration
// ReSharper disable InvertIf
// ReSharper disable JoinDeclarationAndInitializer
// ReSharper disable MemberCanBeMadeStatic.Global
// ReSharper disable MemberCanBeMadeStatic.Local
// ReSharper disable MemberCanBePrivate.Global
// ReSharper disable NonReadonlyMemberInGetHashCode
// ReSharper disable PossibleNullReferenceException
// ReSharper disable RedundantUsingDirective
// ReSharper disable SuggestVarOrType_BuiltInTypes
// ReSharper disable SuggestVarOrType_Elsewhere
// ReSharper disable TailRecursiveCall
// ReSharper disable UnusedMember.Global
// ReSharper disable UnusedMember.Local
// ReSharper disable UnusedType.Global
// ReSharper disable UseObjectOrCollectionInitializer
// ReSharper disable ForCanBeConvertedToForeach

#if true && UTAKA_LOCAL
//#if false
#define UTAKA_DEBUG
#endif

//#define TOPCODER

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
using static UtakaApp.Util;
using P = UtakaApp.Util.Pair<int, int>;

namespace UtakaApp
{
    public partial class Program
    {
        /*
        https://atcoder.jp/contests/abc151/tasks/abc151_f
        */
// F - Enclose All / 
// 実行時間制限: 2 sec / メモリ制限: 1024 MB
//
// 配点 : 600 点
//
// 問題文
// 平面上の N 個の点 ( x i , y i) が与えられます。
//
// これら全てを内部または周上に含む円の半径の最小値を求めてください。
//
// 制約
// 2 ≤ N ≤ 50
// 0 ≤ x i ≤ 1000
// 0 ≤ y i ≤ 1000
// 与えられる N 点は全て異なる
// 入力で与えられる値は全て整数
//
// 入力
// 入力は以下の形式で標準入力から与えられる。
//
// N 
// x 1 y 1 
// :
// x N y N
//
// 出力
// N 個全ての点を内部または周上に含む円の半径の最小値を出力せよ。
//
// なお、想定解答との絶対誤差または相対誤差が 10 − 6 以下であれば正解として扱われる。

        public const string SiteName    = "AtCoder";
        public const string ContestName = "abc151";
        public const string ProblemName = "F";

        private int   N;
        private V2d[] A;

        // ==========================================
        // 3分探索をx、y方向に2回行う方法
        // ==========================================

        public void Solve3()
        {
            N = cin.ReadInt;
            A = new V2d[N];

            for (int i = 0; i < N; i++)
            {
                A[i] = new V2d(cin.ReadDouble, cin.ReadDouble);
            }

            // x方向の3分探索

            double l = 0;
            double r = 1000;

            for (int i = 0; i < 80; i++)
            {
                double midL = (l * 2 + r) / 3;
                double midR = (l + r * 2) / 3;

                if (F(midL) < F(midR))
                {
                    r = midR;
                }
                else
                {
                    l = midL;
                }
            }

            double ans = F(l);
            cou.WriteLine(ans);
        }

        // xを決めて yを好きにしていいときの、N個の点までの最長距離
        public double F(double x)
        {
            double l = 0;
            double r = 1000;

            for (int i = 0; i < 80; i++)
            {
                double midL = (l * 2 + r) / 3;
                double midR = (l + r * 2) / 3;

                if (LongestDistanceToPoint(new V2d(x, midL)) < LongestDistanceToPoint(new V2d(x, midR)))
                {
                    r = midR;
                }
                else
                {
                    l = midL;
                }
            }

            return LongestDistanceToPoint(new V2d(x, l));
        }

        // 点pから、N個の点までの最長距離
        public double LongestDistanceToPoint(V2d p)
        {
            double res = 0;

            for (int i = 0; i < N; i++)
            {
                res = Math.Max(res, (p - A[i]).magnitude);
            }

            return res;
        }

        // ==========================================
        // 幾何学で求める方法 O(N^3)
        // ==========================================

        public void Solve()
        {
            int N = cin.ReadInt;

            V2d[] A = new V2d[N];

            for (int i = 0; i < N; i++)
            {
                A[i] = new V2d(cin.ReadDouble, cin.ReadDouble);
            }

            if (N < 3)
            {
                double ans2 = V2d.Distance(A[0], A[1]) / 2;
                cou.WriteLine(ans2);
                return;
            }

            double ans = 0d;

            for (int i = 0; i < N; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    for (int k = j + 1; k < N; k++)
                    {
                        ans = Math.Max(ans, GetMinimumBoundingCircleRadius(A[i], A[j], A[k]));
                    }
                }
            }

            cou.WriteLine(ans);
        }
    }

    public static partial class Util
    {
        public const int  ModInt = 1000000007;
        public const long Mod    = ModInt;

        public const double Eps = 1E-10;
    }

    // V2d addition01 最小包含円 外接円
    public static partial class Util
    {
        /// <summary>
        /// 3点a,b,cの最小包含円の半径を取得する
        /// NOTE: 鈍角がある場合は外接円にはならない
        /// </summary>
        public static double GetMinimumBoundingCircleRadius(V2d a, V2d b, V2d c)
        {
            V2d ab = b - a;
            V2d ac = c - a;
            V2d bc = c - b;

            double al = bc.magnitude;
            double bl = ac.magnitude;
            double cl = ab.magnitude;

            // s4 := 三角形abcの面積の4倍 外積の大きさは平行四辺形の大きさなので2倍したら三角形4つ分
            double s4 = Math.Abs(V2d.Cross(ab, ac)) * 2;

            // 外積の大きさが0なら、3点は1直線上に並んでいる
            if (IsZero(s4))
            {
                return Math.Max(Math.Max(al, bl), cl) / 2;
            }

            // 鈍角があるなら、外接円ではなくではなく鈍角に向かい合う2点を直径とする円が最小
            if (Cos(al, bl, cl) <= 0) return al / 2;
            if (Cos(bl, cl, al) <= 0) return bl / 2;
            if (Cos(cl, al, bl) <= 0) return cl / 2;

            // 外接円の半径を求める
            // 三角形ABCの面積Sとその外接円の半径Rとすると 4SR = abc 
            return al * bl * cl / s4;

            // 以下でも求まる
            // return al * bl * cl / Math.Sqrt((al + bl + cl) * (-al + bl + cl) * (al - bl + cl) * (al + bl - cl));
        }

        /// <summary>
        /// 三角形abcの外接円の中心と半径を求める
        /// 参考: https://risalc.info/src/circumcircle-incircle.html#r_area
        /// 参考: https://ja.wikipedia.org/wiki/%E5%A4%96%E6%8E%A5%E5%86%86
        /// </summary>
        public static void GetCircumscribedCircle(V2d a, V2d b, V2d c, out V2d center, out double r)
        {
            V2d ab = b - a;
            V2d ac = c - a;
            V2d bc = c - b;

            double alSqr = bc.sqrMagnitude;
            double blSqr = ac.sqrMagnitude;
            double clSqr = ab.sqrMagnitude;

            double al = Math.Sqrt(alSqr);
            double bl = Math.Sqrt(blSqr);
            double cl = Math.Sqrt(clSqr);

            double s = Math.Abs(V2d.Cross(ab, ac)) / 2;

            // 外積の大きさが0なら、3点は1直線上に並んでいる
            if (IsZero(s))
            {
                if (blSqr <= alSqr && clSqr <= alSqr)
                {
                    r      = Math.Sqrt(alSqr);
                    center = b + (bc / 2);
                    return;
                }
                else if (clSqr <= blSqr && alSqr <= blSqr)
                {
                    r      = Math.Sqrt(blSqr);
                    center = a + (ac / 2);
                    return;
                }
                else
                {
                    r      = Math.Sqrt(clSqr);
                    center = a + (ab / 2);
                    return;
                }
            }

            // 三角形ABCの面積Sとその外接円の半径Rとすると 4SR = abc 
            r = al * bl * cl / (s * 4);

            center = (alSqr * (blSqr + clSqr - alSqr) * a
                      + blSqr * (clSqr + alSqr - blSqr) * b
                      + clSqr * (alSqr + blSqr - clSqr) * c)
                     / (16 * s * s);
        }

        public static double Cos(double a, double b, double c)
        {
            return (b * b + c * c - a * a) / (2 * b * c);
        }
    }

    // V2d
    public static partial class Util
    {
        // ===================================================
        // doubleの誤差処理
        // ===================================================

        /// <summary>
        /// vの誤差付きの符号に従って -1, 0, 1 を返す
        /// </summary>
        public static int Sgn(double v)
        {
            if (v > Eps) return 1;
            if (v < -Eps) return -1;
            return 0;
        }

        /// <summary>
        /// 誤差付きで、aが小さければ -1、大きければ 1、同じなら0を返す
        /// </summary>
        public static int Sgn(double a, double b)
        {
            if (a < b - Eps)
            {
                return -1;
            }

            if (a > b + Eps)
            {
                return 1;
            }

            return 0;
        }

        /// <summary>
        /// vが誤差を考慮して0であるか
        /// </summary>
        public static bool IsZero(double v)
        {
            return Math.Abs(v) <= Eps;
        }

        /// <summary>
        /// a と b が誤差を考慮して同じか
        /// </summary>
        public static bool IsSame(double a, double b)
        {
            return Math.Abs(a - b) <= Eps;
        }

        // ===================================================
        // ベクトル処理
        // ===================================================

        public static bool IsOrthogonal(V2d a, V2d b)
        {
            return IsZero(V2d.Dot(a, b));
        }

        public static bool IsParallel(V2d a, V2d b)
        {
            return IsZero(V2d.Cross(a, b));
        }

        public const int COUNTER_CLOCKWISE = 1;  // 反時計回り
        public const int CLOCKWISE         = -1; // 時計回り
        public const int ONLINE_BACK       = 2;  // p2 p0 p1 の順
        public const int ONLINE_FRONT      = -2; // p0 p1 p2 の順
        public const int ON_SEGMENT        = 0;  // p2 が線分p0p1上

        /// <summary>
        /// 参照: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C&lang=ja
        /// p0を基準に、p1に対してp2の位置関係を返す。
        /// </summary>
        public static int Ccw(V2d p0, V2d p1, V2d p2)
        {
            V2d a = p1 - p0;
            V2d b = p2 - p0;
            if (V2d.Cross(a, b) > Eps) return COUNTER_CLOCKWISE;
            if (V2d.Cross(a, b) < -Eps) return CLOCKWISE;
            if (V2d.Dot(a, b) < -Eps) return ONLINE_BACK;
            if (a.sqrMagnitude < b.sqrMagnitude) return ONLINE_FRONT;
            return ON_SEGMENT;
        }

        /// <summary>
        /// 線分p1p2と線分p3p4が交差するか
        /// </summary>
        public static bool Intersect(V2d p1, V2d p2, V2d p3, V2d p4)
        {
            return Ccw(p1, p2, p3) * Ccw(p1, p2, p4) <= 0
                   && Ccw(p3, p4, p1) * Ccw(p3, p4, p2) <= 0;
        }

        /// <summary>
        /// 線分s1と線分s2が交差するか
        /// </summary>
        public static bool Intersect(Segment s1, Segment s2)
        {
            return Intersect(s1.p1, s1.p2, s2.p1, s2.p2);
        }

        /// <summary>
        /// 直線sと点pの距離を求める
        /// </summary>
        public static double GetDistanceLineAndPoint(Segment s, V2d p)
        {
            return Math.Abs(V2d.Cross(s.p2 - s.p1, p - s.p1) / V2d.Magnitude(s.p2 - s.p1));
        }

        /// <summary>
        /// 直線p1p2と点の距離を求める
        /// </summary>
        public static double GetDistanceLineAndPoint(V2d p1, V2d p2, V2d p)
        {
            return Math.Abs(V2d.Cross(p2 - p1, p - p1) / V2d.Magnitude(p2 - p1));
        }

        /// <summary>
        /// 線分sと点pの距離を求める
        /// </summary>
        public static double GetDistanceSegmentAndPoint(Segment s, V2d p)
        {
            if (V2d.Dot(s.p2 - s.p1, p - s.p1) < 0d) return V2d.Magnitude(p - s.p1);
            if (V2d.Dot(s.p1 - s.p2, p - s.p2) < 0d) return V2d.Magnitude(p - s.p2);
            return GetDistanceLineAndPoint(s, p);
        }

        /// <summary>
        /// 線分p1p2と点pの距離を求める
        /// </summary>
        public static double GetDistanceSegmentAndPoint(V2d p1, V2d p2, V2d p)
        {
            if (V2d.Dot(p2 - p1, p - p1) < 0d) return V2d.Magnitude(p - p1);
            if (V2d.Dot(p1 - p2, p - p2) < 0d) return V2d.Magnitude(p - p2);
            return GetDistanceLineAndPoint(p1, p2, p);
        }

        /// <summary>
        /// 線分s1と線分s2の距離を求める
        /// </summary>
        public static double GetDistanceSegmentAndSegment(Segment s1, Segment s2)
        {
            if (Intersect(s1, s2)) return 0d;

            return Math.Min(
                Math.Min(GetDistanceSegmentAndPoint(s1, s2.p1), GetDistanceSegmentAndPoint(s1, s2.p2)),
                Math.Min(GetDistanceSegmentAndPoint(s2, s1.p1), GetDistanceSegmentAndPoint(s2, s1.p2))
            );
        }

        /// <summary>
        /// 線分p1p2と線分p3p4の距離を求める
        /// </summary>
        public static double GetDistanceSegmentAndSegment(V2d p1, V2d p2, V2d p3, V2d p4)
        {
            if (Intersect(p1, p2, p3, p4)) return 0d;

            return Math.Min(
                Math.Min(GetDistanceSegmentAndPoint(p1, p2, p3), GetDistanceSegmentAndPoint(p1, p2, p4)),
                Math.Min(GetDistanceSegmentAndPoint(p3, p4, p1), GetDistanceSegmentAndPoint(p3, p4, p2))
            );
        }

        /// <summary>
        /// 線分s1と線分s2の交点を求める
        /// 注意: 交差する場合のみ呼べる
        /// なお、内部の距離でvecの大きさは約分で消えるので計算に含めていない。
        /// </summary>
        public static V2d GetCrossPoint(Segment s1, Segment s2)
        {
            V2d    vec       = s2.p2 - s2.p1;
            double distance1 = Math.Abs(V2d.Cross(vec, s1.p1 - s2.p1));
            double distance2 = Math.Abs(V2d.Cross(vec, s1.p2 - s2.p1));
            double t         = distance1 / (distance1 + distance2);

            return s1.p1 + (s1.p2 - s1.p1) * t;
        }

        /// <summary>
        /// 線分p1p2と線分p3p4の交点を求める
        /// 注意: 交差する場合のみ呼べる
        /// なお、内部の距離でvecの大きさは約分で消えるので計算に含めていない。
        /// </summary>
        public static V2d GetCrossPoint(V2d p1, V2d p2, V2d p3, V2d p4)
        {
            V2d    vec       = p4 - p3;
            double distance1 = Math.Abs(V2d.Cross(vec, p1 - p3));
            double distance2 = Math.Abs(V2d.Cross(vec, p2 - p3));
            double t         = distance1 / (distance1 + distance2);

            return p1 + (p2 - p1) * t;
        }

        // ===================================================
        // 線分とベクトルの構造体
        // ===================================================

        /// <summary>
        /// 二次元の線分
        /// </summary>
        public struct Segment
        {
            public V2d p1;
            public V2d p2;

            public Segment(V2d p1, V2d p2)
            {
                this.p1 = p1;
                this.p2 = p2;
            }
        }

        /// <summary>
        /// 二次元ベクトル
        /// </summary>
        public struct V2d
        {
            public const double RadToDeg = 180d / Math.PI;
            public const double DegToRad = Math.PI / 180d;

            public const double SqrEps = Eps * Eps;

            public double X;
            public double Y;

            public double this[int index]
            {
                get
                {
                    switch (index)
                    {
                        case 0:
                            return X;
                        case 1:
                            return Y;
                        default:
                            throw new IndexOutOfRangeException("Invalid index!");
                    }
                }
                set
                {
                    switch (index)
                    {
                        case 0:
                            X = value;
                            break;
                        case 1:
                            Y = value;
                            break;
                        default:
                            throw new IndexOutOfRangeException("Invalid Vector2d index!");
                    }
                }
            }

            public V2d Normalized => Normalize(this);

            public double magnitude => Math.Sqrt(X * X + Y * Y);

            public double sqrMagnitude => X * X + Y * Y;

            public static V2d zero => new V2d(0d, 0d);
            public static V2d one  => new V2d(1d, 1d);

            public V2d(double x, double y)
            {
                X = x;
                Y = y;
            }

            public static V2d operator +(V2d a, V2d b)
            {
                return new V2d(a.X + b.X, a.Y + b.Y);
            }

            public static V2d operator -(V2d a, V2d b)
            {
                return new V2d(a.X - b.X, a.Y - b.Y);
            }

            public static V2d operator -(V2d a)
            {
                return new V2d(-a.X, -a.Y);
            }

            public static V2d operator *(V2d a, double d)
            {
                return new V2d(a.X * d, a.Y * d);
            }

            public static V2d operator *(double d, V2d a)
            {
                return new V2d(a.X * d, a.Y * d);
            }

            public static V2d operator /(V2d a, double d)
            {
                return new V2d(a.X / d, a.Y / d);
            }

            public static bool operator ==(V2d lhs, V2d rhs)
            {
                return IsEqual(lhs.X, rhs.X) && IsEqual(lhs.Y, rhs.Y);
            }

            public static bool operator !=(V2d lhs, V2d rhs)
            {
                return !IsEqual(lhs.X, rhs.X) || !IsEqual(lhs.Y, rhs.Y);
            }

            public void Set(double new_x, double new_y)
            {
                X = new_x;
                Y = new_y;
            }

            public static V2d Scale(V2d a, V2d b)
            {
                return new V2d(a.X * b.X, a.Y * b.Y);
            }

            public void Scale(V2d scale)
            {
                X *= scale.X;
                Y *= scale.Y;
            }

            public static double Cross(V2d lhs, V2d rhs)
            {
                return lhs.X * rhs.Y - lhs.Y * rhs.X;
            }

            public override int GetHashCode()
            {
                return X.GetHashCode() ^ Y.GetHashCode();
            }

            public override bool Equals(object other)
            {
                if (!(other is V2d))
                    return false;

                V2d vector3d = (V2d)other;

                return this == vector3d;
            }

            public static V2d Reflect(V2d inDirection, V2d inNormal)
            {
                return -2d * Dot(inNormal, inDirection) * inNormal + inDirection;
            }

            public static V2d Normalize(V2d value)
            {
                double num = SqrMagnitude(value);
                if (num > SqrEps)
                    return value / num;
                else
                    return zero;
            }

            public void Normalize()
            {
                double num = Magnitude(this);
                if (num > SqrEps)
                    this = this / num;
                else
                    this = zero;
            }

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

            public static double Dot(V2d lhs, V2d rhs)
            {
                return lhs.X * rhs.X + lhs.Y * rhs.Y;
            }

            public static V2d Project(V2d vector, V2d onNormal)
            {
                double num = Dot(onNormal, onNormal);
                if (num < 1.40129846432482E-45d)
                    return zero;
                else
                    return onNormal * Dot(vector, onNormal) / num;
            }

            public static V2d Exclude(V2d excludeThis, V2d fromThat)
            {
                return fromThat - Project(fromThat, excludeThis);
            }

            /// <summary>
            /// 2つのベクトルの間の角度 ラジアン
            /// 与えるベクトルが正規化されている必要はない
            /// </summary>
            public static double AngleRadian(V2d from, V2d to)
            {
                double sin = from.X * to.Y - to.X * from.Y;
                double cos = from.X * to.X + from.Y * to.Y;
                return Math.Atan2(sin, cos);
            }

            /// <summary>
            /// 2つのベクトルの間の角度 度
            /// 与えるベクトルが正規化されている必要はない
            /// </summary>
            public static double AngleDegree(V2d from, V2d to)
            {
                double sin = from.X * to.Y - to.X * from.Y;
                double cos = from.X * to.X + from.Y * to.Y;
                return Math.Atan2(sin, cos) * RadToDeg;
            }

            /// <summary>
            /// 指定した点を原点中止にangle 度 回転する
            /// </summary>
            public static V2d RotationDegree(V2d v, double angle)
            {
                double rad = angle * DegToRad;
                double sin = Math.Sin(rad);
                double cos = Math.Cos(rad);

                V2d res = new V2d(
                    v.X * cos - v.Y * sin,
                    v.X * sin + v.Y * cos);
                return res;
            }

            /// <summary>
            /// 指定した点を原点中止にrad回転する
            /// </summary>
            public static V2d RotationRadian(V2d v, double rad)
            {
                double sin = Math.Sin(rad);
                double cos = Math.Cos(rad);

                V2d res = new V2d(
                    v.X * cos - v.Y * sin,
                    v.X * sin + v.Y * cos);
                return res;
            }

            /// <summary>
            /// 指定した点をbasePoint中心にangle 度回転する
            /// </summary>
            public static V2d RotationDegree(V2d v, double angle, V2d basePoint)
            {
                double rad = angle * DegToRad;
                double sin = Math.Sin(rad);
                double cos = Math.Cos(rad);
                V2d res = new V2d(
                    (v.X - basePoint.X) * cos - (v.Y - basePoint.Y) * sin + basePoint.X,
                    (v.X - basePoint.X) * sin + (v.Y - basePoint.Y) * cos + basePoint.Y);
                return res;
            }

            /// <summary>
            /// 指定した点をbasePoint中心にrad転する
            /// </summary>
            public static V2d RotationRadian(V2d v, double rad, V2d basePoint)
            {
                double sin = Math.Sin(rad);
                double cos = Math.Cos(rad);
                V2d res = new V2d(
                    (v.X - basePoint.X) * cos - (v.Y - basePoint.Y) * sin + basePoint.X,
                    (v.X - basePoint.X) * sin + (v.Y - basePoint.Y) * cos + basePoint.Y);
                return res;
            }

            public static double Distance(V2d a, V2d b)
            {
                double x = a.X - b.X;
                double y = a.Y - b.Y;
                return Math.Sqrt(x * x + y * y);
            }

            public static V2d ClampMagnitude(V2d vector, double maxLength)
            {
                if (vector.sqrMagnitude > maxLength * maxLength)
                    return vector.Normalized * maxLength;
                else
                    return vector;
            }

            public static double Magnitude(V2d a)
            {
                return Math.Sqrt(a.X * a.X + a.Y * a.Y);
            }

            public static double SqrMagnitude(V2d a)
            {
                return a.X * a.X + a.Y * a.Y;
            }

            public static V2d Min(V2d lhs, V2d rhs)
            {
                return new V2d(Math.Min(lhs.X, rhs.X), Math.Min(lhs.Y, rhs.Y));
            }

            public static V2d Max(V2d lhs, V2d rhs)
            {
                return new V2d(Math.Max(lhs.X, rhs.X), Math.Max(lhs.Y, rhs.Y));
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            private static bool IsEqual(double a, double b)
            {
                return Math.Abs(a - b) < Eps;
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            private static double Clamp(double val, double min, double max)
            {
                if (val < min)
                {
                    return min;
                }

                if (max < val)
                {
                    return max;
                }

                return val;
            }
        }
    }

    // Math
    public static partial class Util
    {
        static partial void InitializeUtilMath()
        {
            fac  = null;
            fInv = null;
            inv  = null;
            maxN = 0;
        }

        /// <summary>
        /// a^n mod.Mod を計算する
        /// </summary>
        public static long ModPow(long a, long n)
        {
            long res = 1;
            while (n > 0)
            {
                if ((n & 1) != 0) res = res * a % Mod;
                a =   a * a % Mod;
                n >>= 1;
            }

            return res;
        }

        /// <summary>
        /// mod.Mod での a の逆元 a^{-1} を求める
        /// </summary>
        public static long ModInv(long a)
        {
            long b = Mod;
            long u = 1;
            long 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 Gcd(long a, long b)
        {
            while (a != 0 && b != 0)
            {
                if (a > b)
                    a %= b;
                else
                    b %= a;
            }

            return a == 0 ? b : a;
        }

        public static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }

        // 返り値: a と b の最大公約数
        // a * x + b * y = Gcd(a, b) を満たす (x, y) を格納する
        public static long ExtGcd(long a, long b, out long x, out long y)
        {
            long g = a;
            x = 1;
            y = 0;
            if (b > 0)
            {
                g =  ExtGcd(b, a % b, out y, out x);
                y -= a / b * x;
            }

            return g;
        }

        // TODO
        // 返り値k: x^k = y (mod. Mod) O(sqrt(Mod))
        // 存在しなければ-1を返す
        public static long ModLog(long x, long y)
        {
            if (y == 1) return 0;
            long h    = (long)Math.Sqrt(Mod) + 1;
            var  dict = new Dictionary<long, long>();
            for (long b = 0, xby = y; b < h; b++, xby = (xby * x) % Mod)
            {
                dict[xby] = b;
            }

            long xH                        = 1;
            for (int i = 0; i < h; ++i) xH = xH * x % Mod;
            for (long a = 1, xaH = xH; a <= h; a++, xaH = (xaH * xH) % Mod)
                if (dict.ContainsKey(xaH))
                    return a * h - dict[xaH];

            return -1;
        }

        // https://mathtrain.jp/remainder
        // x = b[i] (mod.m[i]) を満たす 0 <= x < lcm(m[0],m[1],..,m[k])
        // 返り値: 解が存在するか
        // modはlcm(m[0],m[1],...,m[k])となる
        public static bool ChineseRemainderTheorem(IList<long> b, IList<long> m, out long x, out long mod)
        {
            long r = 0, M = 1;
            for (int i = 0; i < b.Count; ++i)
            {
                long p, q;
                long d = ExtGcd(M, m[i], out p, out q); // p is inv of M/d (mod. m[i]/d)
                if ((b[i] - r) % d != 0)
                {
                    x   = 0;
                    mod = -1;
                    return false;
                }

                long tmp = (b[i] - r) / d * p % (m[i] / d);
                r += M * tmp;
                M *= m[i] / d;
            }

            x   = (r % M + M) % M;
            mod = M;
            return true;
        }

        public static bool IsPrime(long n)
        {
            if (n <= 1) return false;
            if (n == 2) return true;
            if (n % 2 == 0) return false;

            double boundary = Math.Sqrt(n);

            for (int i = 3; i <= boundary; i += 2)
            {
                if (n % i == 0) return false;
            }

            return true;
        }

        public static bool[] Sieve(int n)
        {
            bool[] isPrime = new bool[n + 1];

            for (int i = 0; i <= n; i++)
            {
                isPrime[i] = true;
            }

            isPrime[0] = isPrime[1] = false;

            for (int i = 2; i * i <= n; i++)
            {
                if (isPrime[i])
                {
                    for (int j = i * i; j <= n; j += i)
                    {
                        isPrime[j] = false;
                    }
                }
            }

            return isPrime;
        }

        // n以下の素数の配列を得る
        public static int[] GetPrimes(int n)
        {
            List<int> primes  = new List<int>();
            bool[]    isPrime = new bool[n + 1];

            for (int i = 0; i <= n; i++)
            {
                isPrime[i] = true;
            }

            isPrime[0] = isPrime[1] = false;

            for (int i = 2; i * i <= n; i++)
            {
                if (isPrime[i])
                {
                    primes.Add(i);
                    for (int j = i * i; j <= n; j += i)
                    {
                        isPrime[j] = false;
                    }
                }
            }

            return primes.ToArray();
        }

        /// <summary>
        /// [a, b)の整数に対してエラトステネスの篩を作る
        /// isPrime[i - a] = true <=> iが素数
        /// </summary>
        public static bool[] SegmentSieve(long a, long b)
        {
            if (b - a > int.MaxValue)
            {
                throw new InvalidOperationException("aとbが離れすぎ");
            }

            int len = (int)(b - a);

            int sqrtB = (int)(Math.Sqrt(b) + 2); // 誤差の対応のため+2

            bool[] isPrime      = new bool[len];
            bool[] isPrimeSmall = new bool[sqrtB];

            for (int i = 2; (long)i * i < b; i++)
            {
                isPrimeSmall[i] = true;
            }

            for (int i = 0; i < len; i++)
            {
                isPrime[i] = true;
            }

            for (int i = 2; (long)i * i < b; i++)
            {
                if (isPrimeSmall[i])
                {
                    for (int j = i * i; (long)j * j < b; j += i)
                    {
                        isPrimeSmall[j] = false; // [2, root(b)) の篩
                    }

                    for (long j = Math.Max(2L, (a + i - 1) / i) * i; j < b; j += i)
                    {
                        isPrime[j - a] = false; // [a, b) の篩
                    }
                }
            }

            return isPrime;
        }

        // ============
        // 階乗を扱う処理
        // ============

        public static long[] fac;  // fac[i]  := iの階乗
        public static long[] fInv; // fInv[i] := 1 / (iの階乗)
        public static long[] inv;  // inv[i]  := 1 / i

        public static int maxN; // 計算対象のNの最大値

        // maxN:  1000000 で  90ms 
        // maxN: 10000000 で 900ms かかる
        public static void InitFac(int maxN)
        {
            if (fac != null) throw new InvalidOperationException("設定済み");

            Util.maxN = maxN;

            fac  = new long[maxN + 1];
            fInv = new long[maxN + 1];
            inv  = new long[maxN + 1];

            // 事前計算
            fac[0]  = fac[1]  = 1;
            fInv[0] = fInv[1] = 1;
            inv[1]  = 1;

            for (int i = 2; i < Util.maxN + 1; i++)
            {
                fac[i]  = fac[i - 1] * i % Mod;
                inv[i]  = Mod - inv[Mod % i] * (Mod / i) % Mod;
                fInv[i] = fInv[i - 1] * inv[i] % Mod;
            }
        }

        public static long Fact(long n)
        {
            if (n < 0) return 0;
            if (fac != null)
            {
                if (maxN < n) throw new InvalidOperationException($"n is larger than MaxN! maxN{maxN} n:{n}");
                return fac[n];
            }

            long numer = 1;
            for (long i = 0; i <= n; i++)
            {
                numer = numer * (i % Mod) % Mod;
            }

            return numer;
        }

        // nPk
        public static long Perm(long n, long k)
        {
            if (n < k) return 0;
            if (n < 0 || k < 0) return 0;

            if (fac != null)
            {
                if (maxN < n) throw new InvalidOperationException($"n is larger than MaxN! maxN{maxN} n:{n}");
                return fac[n] * fInv[n - k] % Mod;
            }

            long numer = 1;
            for (long i = 0; i < k; i++)
            {
                numer = numer * ((n - i) % Mod) % Mod;
            }

            return numer;
        }

        // nCk
        public static long Comb(int n, int k)
        {
            if (n < k) return 0;
            if (n < 0 || k < 0) return 0;

            if (fac != null)
            {
                if (maxN < n) throw new InvalidOperationException($"n is larger than MaxN! maxN{maxN} n:{n}");
                return fac[n] * (fInv[k] * fInv[n - k] % Mod) % Mod;
            }

            if (n - k < k) k = n - k;

            long numer = 1;
            long denom = 1;

            for (long i = 0; i < k; i++)
            {
                numer = numer * ((n - i) % Mod) % Mod;
                denom = denom * ((i + 1) % Mod) % Mod;
            }

            return numer * ModInv(denom) % Mod;
        }

        // nHk
        public static long MultiChoose(int n, int k)
        {
            return Comb(n + k - 1, k);
        }

        // ============
        // 累乗を扱う処理
        // ============

        public static Mint[] mpows;

        // baseValue ^ exponent までの配列を用意する
        public static void InitMpows(int baseValue, int exponent)
        {
            mpows    = new Mint[exponent + 1];
            mpows[0] = 1;
            for (int i = 1; i <= exponent; i++)
            {
                mpows[i] = mpows[i - 1] * baseValue;
            }
        }

        public static long[] pows;

        // baseValue ^ exponent までの配列を用意する
        public static void InitPows(int baseValue, int exponent)
        {
            pows    = new long[exponent + 1];
            pows[0] = 1;
            for (int i = 1; i <= exponent; i++)
            {
                pows[i] =  pows[i - 1] * baseValue;
                pows[i] %= Mod;
            }
        }
    }


    // ================
    // @formatter:off
    // ================

    public partial class Program
    {
#if !TOPCODER
        public static void Main()
        {
#if UTAKA_LOCAL
// #if false
            new TestCaseCheckerForAtCoder().TestProblems();
#else
            cin = new ConsoleInput(System.Console.In); cou = new MyConsole(); new Program().Solve(); cou.Flush();
#endif
        }
#endif
    }

    public static partial class Util
    {
        static partial void InitializeUtilMath();
        
        public static void InitializeUtil()
        {
            InitializeUtilMath();
        }
        
        public static ConsoleInput cin;
        public static IConsole cou;
        
        public static T[] Array1D<T>(int a, T defaultValue) where T : struct { var ret = new T[a]; for (int i = 0; i < a; i++) { ret[i] = defaultValue; } return ret; }
        public static T[] Array1D<T>(int a) where T : struct { var ret = new T[a]; return ret; }
        public static T[,] Array2D<T>(int a, int b, T defaultValue) where T : struct { var ret = new T[a, b]; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { ret[i, j] = defaultValue; } } return ret; }
        public static T[,,] Array3D<T>(int a, int b, int c, T defaultValue) where T : struct { T[,,] ret = new T[a, b, c]; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { for (int k = 0; k < c; k++) { ret[i, j, k] = defaultValue; } } } return ret; }
        public static T[][] JagArray2D<T>(int a, int b, T defaultValue) where T : struct { var ret = new T[a][]; for (int i = 0; i < a; i++) { var row = new T[b]; ret[i] = row; for (int j = 0; j < b; j++) { row[j] = defaultValue; } } return ret; }
        public static T[][] JagArray2D<T>(int a, int b) where T : struct { var ret = new T[a][]; for (int i = 0; i < a; i++) { ret[i] = new T[b]; } return ret; }
        public static T[][][] JagArray3D<T>(int a, int b, int c, T defaultValue) where T : struct { var ret = new T[a][][]; for (int i = 0; i < a; i++) { T[][] aRow = new T[b][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[] bRow = new T[c]; aRow[j] = bRow; for (int k = 0; k < c; k++) { bRow[k] = defaultValue; } } } return ret; }
        public static T[][][] JagArray3D<T>(int a, int b, int c) where T : struct { var ret = new T[a][][]; for (int i = 0; i < a; i++) { T[][] aRow = new T[b][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[] bRow = new T[c]; aRow[j] = bRow; } } return ret; }
        public static T[][][][] JagArray4D<T>(int a, int b, int c, int d, T defaultValue) where T : struct { var ret = new T[a][][][]; for (int i = 0; i < a; i++) { T[][][] aRow = new T[b][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][] bRow = new T[c][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[] cRow = new T[d]; bRow[k] = cRow; for (int l = 0; l < d; l++) { cRow[l] = defaultValue; } } } } return ret; } 
        public static T[][][][] JagArray4D<T>(int a, int b, int c, int d) where T : struct { var ret = new T[a][][][]; for (int i = 0; i < a; i++) { T[][][] aRow = new T[b][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][] bRow = new T[c][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[] cRow = new T[d]; bRow[k] = cRow; } } } return ret; }
        public static T[][][][][] JagArray5D<T>(int a, int b, int c, int d, int e, T defaultValue) where T : struct { var ret = new T[a][][][][]; for (int i = 0; i < a; i++) { T[][][][] aRow = new T[b][][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][][] bRow = new T[c][][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[][] cRow = new T[d][]; bRow[k] = cRow; for (int l = 0; l < d; l++) { T[] dRow = new T[e]; cRow[l] = dRow; for (int m = 0; m < e; m++) { dRow[m] = defaultValue; } } } } } return ret; }
        public static T[][][][][] JagArray5D<T>(int a, int b, int c, int d, int e) where T : struct { var ret = new T[a][][][][]; for (int i = 0; i < a; i++) { T[][][][] aRow = new T[b][][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][][] bRow = new T[c][][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[][] cRow = new T[d][]; bRow[k] = cRow; for (int l = 0; l < d; l++) { T[] dRow = new T[e]; cRow[l] = dRow; } } } } return ret; }

        // IListを配列をコピーして配列を返す
        public static T[] CopyArray<T>(IList<T> a) { T[] ret = new T[a.Count]; for (int i = 0; i < a.Count; i++) ret[i] = a[i]; return ret; }

        // ジャグ配列をコピーして返す。
        public static T[][] CopyJagArray2D<T>(T[][] source) where T : struct { int   len  = source.Length; T[][] dest = new T[len][]; for (int i = 0; i < len; i++) { T[] inner       = source[i]; int innerLength = inner.Length; T[] newer       = new T[innerLength]; Array.Copy(inner, newer, innerLength); dest[i] = newer; } return dest; }
        
        public static void Swap<T>(ref T a, ref T b)
        {
            T c = a;
            a = b;
            b = c;
        }
        
        public static void WriteEnumerable<T>(IEnumerable<T> A, string delimiter = " ")
        {
            var sb = new StringBuilder();
            foreach (T v in A)
            {
                sb.Append(v);
                sb.Append(delimiter);
            }

            if (sb.Length > 0)
            {
                sb.Length--;
            }

            cou.WriteLine(sb.ToString());
        }
        
        public class IntLargeComparer : IComparer<int>
        {
            public static IntLargeComparer Instance = new IntLargeComparer();

            public int Compare(int x, int y)
            {
                return y - x;
            }
        }

        public class LongLargeComparer : IComparer<long>
        {
            public static LongLargeComparer Instance = new LongLargeComparer();

            public int Compare(long x, long y)
            {
                if (x > y) return -1;
                if (x < y) return 1;
                return 0;
            }
        }
        
        [DebuggerDisplay("({First}, {Second})")]
        public class Pair<T1, T2> : IComparable<Pair<T1, T2>>, IEquatable<Pair<T1, T2>>
            where T1 : IComparable<T1>
            where T2 : IComparable<T2>
        {
            public T1 First;
            public T2 Second;
            
            public Pair() :this(default(T1), default(T2)) { }
            public Pair(T1 first, T2 second) { First  = first; Second = second; }

            public int CompareTo(Pair<T1, T2> other)
            {
                var firstComparison = First.CompareTo(other.First);
                return firstComparison != 0 ? firstComparison : Second.CompareTo(other.Second);
            }

            public override string ToString() => $"({First}, {Second})";

            public bool Equals(Pair<T1, T2> other)
            {
                return EqualityComparer<T1>.Default.Equals(First, other.First) &&
                       EqualityComparer<T2>.Default.Equals(Second, other.Second);
            }

            public override bool Equals(object obj)
            {
                return obj.GetType() == this.GetType() && Equals((Pair<T1, T2>)obj);
            }

            public override int GetHashCode()
            {
                unchecked
                {
                    return (EqualityComparer<T1>.Default.GetHashCode(First) * 397) ^
                           EqualityComparer<T2>.Default.GetHashCode(Second);
                }
            }
        }
        
        public struct Mint
        {
            public const int MintMod = ModInt;
            public const long PositiveAddition = ((long)MintMod) << 31;
            public long Value;
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public Mint(long value) { if ((Value = value % MintMod) < 0) { Value += MintMod; } } 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static implicit operator long(Mint mint) => mint.Value; 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static implicit operator Mint(long val) => new Mint(val); 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator +(Mint a, int b) => new Mint() {Value = (a.Value + b + PositiveAddition) % MintMod}; 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator +(Mint a, long b) => new Mint(a.Value + b); 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator +(Mint a, Mint b) { long res = a.Value + b.Value; return new Mint() {Value = res >= MintMod ? res - MintMod : res}; } 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator -(Mint a, int b) => new Mint() {Value = (a.Value - b + PositiveAddition) % MintMod}; 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator -(Mint a, long b) => new Mint(a.Value - b); 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator -(Mint a, Mint b) { long res = a.Value - b.Value; return new Mint() {Value = res < 0 ? res + MintMod : res}; } 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator *(Mint a, int b) => new Mint(a.Value * b); 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator *(Mint a, long b) => a * new Mint(b); 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator *(Mint a, Mint b) => new Mint() {Value = a.Value * b.Value % MintMod}; 
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Mint operator /(Mint a, Mint b) => new Mint() {Value = a.Value * GetInverse(b) % MintMod};
            [MethodImpl(MethodImplOptions.AggressiveInlining)] public override string ToString() => Value.ToString();
            [MethodImpl(MethodImplOptions.AggressiveInlining)] static long GetInverse(long a) { long p  = MintMod; long x1 = 1; long y1 = 0; long x2 = 0; long y2 = 1; while (true) { if (p == 1) return x2 + MintMod; var div = a / p; x1 -= x2 * div; y1 -= y2 * div; a  %= p; if (a == 1) return x1 + MintMod; div =  p / a; x2  -= x1 * div; y2  -= y1 * div; p   %= a; } } 
        }
    }

    public class ConsoleInput { private readonly char  _separator; private readonly TextReader  _stream; private readonly Queue<string> inputStream; public ConsoleInput(TextReader stream, char separator = ' ') { _separator  = separator; _stream     = stream; inputStream = new Queue<string>(); } public string Read { get { if (inputStream.Count != 0) { return inputStream.Dequeue(); } var tmp = _stream.ReadLine().Split(_separator); for (var i = 0; i < tmp.Length; ++i) { inputStream.Enqueue(tmp[i]); } return inputStream.Dequeue(); } } public string ReadLine   => _stream.ReadLine(); public int    ReadInt    => int.Parse(Read); public long   ReadLong   => long.Parse(Read); public double ReadDouble => double.Parse(Read); public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) { ret[i] = Read; } return ret; } public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadInt; } return ret; } public int[] ReadIntArrayMinus1(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadInt - 1; } return ret; } public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadLong; } return ret; } } 
    // ReSharper disable once UnusedMemberInSuper.Global
    public interface IConsole { void Flush(); void Write(object obj); void Write(string str); void WriteLine(object obj); void WriteLine(string str); void WriteLine(); }
    public class MyConsole : IConsole { public MyConsole() { var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; Console.SetOut(sw); } public void Flush() { Console.Out.Flush(); } public void Write(object obj) { Write(obj.ToString()); } public void Write(string str) { Console.Write(str); } public void WriteLine(object obj) { WriteLine(obj.ToString()); } public void WriteLine(string str) { Console.WriteLine(str); } public void WriteLine() { Console.WriteLine(); } }

#if UTAKA_LOCAL
    public class DebugConsole : IConsole { private readonly StringBuilder mSb; public DebugConsole() { mSb = new StringBuilder(); } public void Flush() { } public void Write(object obj) { Write(obj.ToString()); } public void Write(string str) { mSb.Append(str); } public void WriteLine(object obj) { WriteLine(obj.ToString()); } public void WriteLine(string str) { mSb.AppendLine(str); } public void WriteLine() { mSb.AppendLine(); } public string GetAllOutput() { return mSb.ToString(); } }
    
    public class TestCaseCheckerForAtCoder
    {
        private string GetDirectoryPath() { var problemPart = string.IsNullOrEmpty(Program.ProblemName) ? "" : $"/{Program.ProblemName}"; return $"{Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}"; }
        private string GetInputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in"; }
        private string GetOutputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out"; }
        public bool TestProblem(int testCaseNumber)
        {
            var inputFilePath      = GetInputFilePath(testCaseNumber); var outputFilePath     = GetOutputFilePath(testCaseNumber); var inputStream        = new StreamReader(inputFilePath); var cin                = new ConsoleInput(inputStream); var debugConsoleWriter = new DebugConsole(); Util.cin = cin; Util.cou = debugConsoleWriter;
            InitializeUtil();
            new Program().Solve(); var        output       = debugConsoleWriter.GetAllOutput(); TextReader outputStream = new StreamReader(outputFilePath); var        outputAnswer = outputStream.ReadToEnd(); Dbg.WriteLine(output); Dbg.WriteLine(outputAnswer); var isCorrect = output == outputAnswer; return isCorrect;
        }
        public void TestProblems(int targetTestCaseNumber = -1) { if (targetTestCaseNumber >= 0) { Console.WriteLine($"!!!!!!!!!!!! Check TestCase {targetTestCaseNumber} !!!!!!!!!!"); } bool isSuccessAll   = true; int  testCaseNumber = 0; while (true) { testCaseNumber++; bool foundTargetTest = targetTestCaseNumber == testCaseNumber; if (targetTestCaseNumber >= 0 && !foundTargetTest) { continue; } var inputFileName = GetInputFilePath(testCaseNumber); if (!File.Exists(inputFileName)) { break; } Console.WriteLine($"TestCase {testCaseNumber} ====================================================="); var result = TestProblem(testCaseNumber); if (result) { Console.WriteLine("Success"); } else { isSuccessAll = false; Console.WriteLine("Failure *****"); } if (foundTargetTest) { break; } } if (isSuccessAll) { Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!"); } }
    }
#endif

    public static class Dbg
    {
        [Conditional("UTAKA_DEBUG")] public static void WriteLine(string str) { Console.WriteLine(str); }
        [Conditional("UTAKA_DEBUG")] public static void WriteLine() { Console.WriteLine(); }
        [Conditional("UTAKA_DEBUG")] public static void Write(string str) { Console.Write(str); }
    }
    
    // ================
    // @formatter:on 
    // ================
}


Measured memory_bytes: 11348