using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            cin = new input();
            mod = new mod(1000000007);
            toolbox = new toolbox();
            Priority_Queue = new Priority_Queue(false);
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            int n = cin.intreed();
            var ab = new List<(long, long)>();
            var a = cin.arraylong(n);
            var b = cin.arraylong(n);
            for(int i=0; i<n; i++)
            {
                ab.Add((a[i], b[i]));
            }
            ab=ab.OrderBy(x=>((decimal)x.Item2-1)/(decimal)x.Item1).Reverse().ToList();

            long lv = 1;
            long ans = 0;
            foreach(var i in ab)
            {
                ans = mod.addition(ans, lv * i.Item1);
                lv = mod.multiplication(lv, i.Item2);
            }
            Console.WriteLine(ans);
            Console.Out.Flush();
        }
        static input cin;
        static mod mod;
        static toolbox toolbox;
        static UnionFind UnionFind;
        static BFS BFS;
        static DFS DFS;
        static Priority_Queue Priority_Queue;
        static Warshall_Floyd Warshall_Floyd;
        static SPFA SPFA;
        static Kruskal Kruskal;
        static FF FF;
        static TSP TSP;
    }

    public static class Extensions
    {
        public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key)
        {
            if (dic.ContainsKey(key))
                dic[key]++;
            else
                dic.Add(key, 1);
            return dic;
        }

        public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value)
        {
            if (dic.ContainsKey(key))
                dic[key].Add(value);
            else
                dic.Add(key, new List<T2>() { value });
            return dic;
        }

        public static T list_pop_back<T>(this List<T> a)
        {
            var k = a[a.Count - 1];
            a.RemoveAt(a.Count - 1);
            return k;
        }

        public static T chmin<T>(ref this T a, T b)
            where T : struct, IComparable
        {
            if (a.CompareTo(b) > 0)
                return a = b;
            else
                return a;
        }
        public static T chmax<T>(ref this T a, T b)
            where T : struct, IComparable
        {
            if (a.CompareTo(b) < 0)
                return a = b;
            else
                return a;
        }

    }

    internal class input
    {
        string[] soloinput;
        int t;
        public input()
        {
            soloinput = new string[0];
            t = 0;
        }
        public string soloreed()
        {
            if (t < soloinput.Length)
            {
                return soloinput[t++];
            }
            string input = Console.ReadLine();
            while (input == "")
            {
                input = Console.ReadLine();
            }
            soloinput = input.Split(" ");
            t = 0;
            return soloinput[t++];
        }
        public int intreed()
        {
            return int.Parse(soloreed());
        }
        public int[] arrayint(int N)
        {
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = intreed();
            }
            return A;
        }
        public long longreed()
        {
            return long.Parse(soloreed());
        }
        public long[] arraylong(long N)
        {
            long[] A = new long[N];
            for (long i = 0; i < N; i++)
            {
                A[i] = longreed();
            }
            return A;
        }
        public decimal decimalreed()
        {
            return decimal.Parse(soloreed());
        }
        public decimal[] arraydecimal(long N)
        {
            decimal[] A = new decimal[N];
            for (decimal i = 0; i < N; i++)
            {
                A[(long)i] = decimalreed();
            }
            return A;
        }


    }

    internal class mod
    {
        public long T { get; set; }
        public mod(long mod = 1000000007)
        {
            T = mod;
        }
        public long addition(long A, long B)
        {
            decimal C = A + B;
            return (long)C % T;
        }
        public long subtraction(long A, long B)
        {
            decimal C = A - B;
            return C % T >= 0 ? (long)C % T : (long)(C + T) % T;
        }
        public long multiplication(long A, long B)
        {
            return ((A % T) * (B % T)) % T;
        }

    }

    internal class toolbox
    {

        string Y = "Yes";
        string N = "No";
        static input cin;
        public toolbox()
        {
            cin = new input();
        }

        public long[] CumulativeSum(long[] A, bool mode = true)
        {
            if (mode == false) Array.Reverse(A);
            long[] back = new long[A.Length + 1];
            back[0] = 0;
            for (int i = 1; i <= A.Length; i++)
            {
                back[i] = back[i - 1] + A[i - 1];
            }
            if (mode == false) Array.Reverse(A);
            return back;
        }

        public long[] Eratosthenes(long A)
        {
            A++;
            var back = new List<long>();
            bool[] ch = new bool[A];
            for (int i = 2; i < A; i++) ch[i] = true;
            for (long i = 2; i < Math.Sqrt(A); i++)
            {
                if (ch[i] == true)
                {
                    back.Add(i);
                    for (long t = 1; i * t < A; t++)
                    {
                        ch[i * t] = false;
                    }
                }
            }
            for (long i = 0; i < A; i++)
            {
                if (ch[i] == true) back.Add(i);
            }
            return back.Distinct().ToArray();
        }
        public void Swap<T>(ref T a, ref T b)
        {
            var i = a;
            a = b;
            b = i;
        }

        public void LSwap<T>(ref List<T> A, int a, int b)
        {
            var i = A[a];
            A[a] = A[b];
            A[b] = i;
        }

        public long Gcd(long A, long B)
        {
            while (A != 0)
            {
                B %= A;
                Swap(ref A, ref B);
            }
            return B;
        }

        public long[] AllDivisors(long N)
        {
            var back = new List<long>();
            for (int i = 1; Math.Pow(i, 2) <= N; i++)
            {
                if (N % i == 0)
                {
                    back.Add(i);
                    back.Add(N / i);
                }
            }
            return back.Distinct().ToArray();
        }

        public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata)
        {
            if (indata.Count() == 1) yield return new T[] { indata.First() };
            foreach (var i in indata)
            {
                var used = new T[] { i };
                var unused = indata.Except(used);
                foreach (var t in ExhaustiveEnumeration(unused))
                    yield return used.Concat(t).ToArray();
            }
            //How to use
            //var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));
        }

        public bool[,] bitallsearch(int N)
        {
            bool[,] back = new bool[(int)Math.Pow(2, N), N];
            for (int i = 0; i < Math.Pow(2, N); i++)
            {
                for (int t = 0; t < N; t++)
                {
                    var k = (i >> t) & 1;
                    if (k == 1)
                    {
                        back[i, t] = true;
                    }
                }
            }
            return back;
        }

        public static int BS<T>(T[] A, T key)
            where T : IComparable
        {
            //このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)
            int left = 0;
            int right = A.Length;
            int mid = 0;
            while (left < right)
            {
                mid = (left + right) / 2;
                if (A[mid].CompareTo(key) == 0)
                    return mid;
                else if (A[mid].CompareTo(key) > 0)
                    right = mid;
                else if (A[mid].CompareTo(key) < 0)
                    left = mid + 1;
            }
            return -1;
        }

        public static int lower_bound<T>(T[] a, T v)
        {
            return lower_bound(a, v, Comparer<T>.Default);
        }

        public static int lower_bound<T>(T[] A, T key, Comparer<T> v)
        {
            int left = 0;
            int right = A.Length - 1;
            int mid = 0;
            var W = 0;
            while (left <= right)
            {
                mid = (left + right) / 2;
                W = v.Compare(A[mid], key);
                if (W == -1)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            return left;
        }

        public long[] prime_factorize(long N)
        {
            long T = N;
            var back = new List<long>();
            for (long i = 2; i * i <= T; i++)
            {
                if (T % i != 0) continue;
                while (T % i == 0)
                {
                    back.Add(i);
                    T /= i;
                }
            }
            if (T != 1) back.Add(T);
            return back.ToArray();
        }

        public long[] One_dimensional_Coordinate_Compression(long[] A)
        {
            long[] back = new long[A.Length];
            var T = A.Distinct().ToList();
            T.Sort();
            for (int i = 0; i < A.Length; i++)
                back[i] = T.BinarySearch(A[i]);
            return back;
        }

        public void setYN(string A = "Yes", string B = "No")
        {
            Y = A;
            N = B;
        }

        public void YN(bool ans)
        {
            if (ans)
                Console.WriteLine(Y);
            else
                Console.WriteLine(N);
        }

        public string[] x_dekakou(int H, int W)
        {
            var s = new string[H + 2];
            for (int i = 0; i < W + 2; i++)
            {
                s[0] += "x";
                s[H + 1] += "x";
            }
            for (int i = 1; i < H + 1; i++)
            {
                //x場外　.白　#黒
                s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";
            }
            return s;
        }

        public List<List<string>> x_dekakou_string(int H, int W)
        {
            var back = new List<List<string>>();
            for (int i = 0; i < H + 2; i++)
                back.Add(Enumerable.Repeat<string>("", W + 2).ToList());
            for (int i = 0; i < W + 2; i++)
            {
                back[0][i] = "x";
                back[H + 1][i] = "x";
            }
            for (int i = 1; i <= H; i++)
            {
                back[i][0] = "x";
                back[i][W + 1] = "x";
                for (int t = 1; t <= W; t++)
                    back[i][t] = cin.soloreed();
            }
            return back;
        }
    }

    internal class UnionFind
    {
        public int[] tree { get; private set; }
        static toolbox toolbox;

        public UnionFind(int s)
        {
            tree = Enumerable.Repeat<int>(-1, s + 1).ToArray();
        }

        public int getroot(int i)
        {
            return tree[i] < 0 ? i : tree[i] = getroot(tree[i]);
        }

        public bool groupcheck(int i, int t)
        {
            return getroot(i) == getroot(t);
        }

        public bool unite(int i, int t)
        {
            toolbox = new toolbox();
            var x = getroot(i);
            var y = getroot(t);
            if (x != y)
            {
                if (tree[x] > tree[y])
                {
                    toolbox.Swap(ref x, ref y);
                }
                tree[x] += tree[y];
                tree[y] = x;
            }
            return x != y;
        }

        public int get_cnt(int i)
        {
            return tree[getroot(i)] * -1;
        }
    }

    internal class BFS
    {
        //この関数は基本的に1_indexで処理される
        public int[] dist { get; set; }
        public bool interactive { get; set; }
        private Queue<int> que = new Queue<int>();
        private List<List<int>> Graph = new List<List<int>>();

        public BFS(int i, bool cnt = true)
        {
            Set_BFS(i, cnt);
        }


        public void Set_BFS(int i, bool cnt = true)
        {
            //(頂点数、双方向グラフであるT/F)
            dist = Enumerable.Repeat<int>(-1, i + 1).ToArray();
            interactive = cnt;
            for (int t = 0; t <= i; t++)
            {
                Graph.Add(new List<int>());
            }
        }

        public void Connect_Graph(int i, int t)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph[i].Add(t);
            if (interactive)
                Graph[t].Add(i);
        }

        public void Start_BFS(int i)
        {
            //(捜索を始める頂点(int))
            dist = Enumerable.Repeat<int>(-1, Graph.Count).ToArray();
            que.Enqueue(i);
            dist[i] = 0;
            while (que.Count != 0)
            {
                var t = que.Dequeue();
                for (int w = 0; w < Graph[t].Count; w++)
                {
                    if (dist[Graph[t][w]] == -1)
                    {
                        que.Enqueue(Graph[t][w]);
                        dist[Graph[t][w]] = dist[t] + 1;
                    }
                }
            }
        }

        public void Start_BFS(List<int> i)
        {
            dist = Enumerable.Repeat<int>(-1, Graph.Count).ToArray();
            foreach (var t in i)
            {
                que.Enqueue(t);
                dist[t] = 0;
            }
            while (que.Count != 0)
            {
                var t = que.Dequeue();
                for (int w = 0; w < Graph[t].Count; w++)
                {
                    if (dist[Graph[t][w]] == -1)
                    {
                        que.Enqueue(Graph[t][w]);
                        dist[Graph[t][w]] = dist[t] + 1;
                    }
                }
            }
        }

    }

    internal class DFS
    {
        //この関数は基本的に1_indexで処理される
        private int[] dist;
        private bool interactive = true;
        private Stack<int> stc = new Stack<int>();
        private List<List<int>> Graph = new List<List<int>>();

        public DFS()
        {
        }


        public void Set_DFS(int i, bool cnt = true)
        {
            //(頂点数、双方向グラフであるT/F)
            dist = Enumerable.Repeat<int>(-1, i + 1).ToArray();
            interactive = cnt;
            for (int t = 0; t <= i; t++)
            {
                Graph.Add(new List<int>());
            }
        }

        public void Connect_Graph(int i, int t)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph[i].Add(t);
            if (interactive)
                Graph[t].Add(i);
        }

        public void Start_DFS(int i, bool cnt = false)
        {
            //(捜索を始める頂点(int))
            stc.Push(i);
            dist[i] = 0;
            while (stc.Count != 0)
            {
                var t = stc.Pop();
                for (int w = 0; w < Graph[t].Count; w++)
                {
                    if (dist[Graph[t][w]] == -1)
                    {
                        stc.Push(Graph[t][w]);
                    }
                }
            }
        }

        public int Get_Cost(int i)
        {
            return dist[i];
        }
    }

    internal class Dijkstra
    {
        static Priority_Queue Priority_Queue;
        public long[] dist { get; set; }
        public bool interactive { get; set; }
        public int[] prev { get; set; }
        /// <summary>
        /// 行先,コスト
        /// </summary>
        public List<List<(long, long)>> Graph { get; set; }

        public Dijkstra(int n, bool cnt = true)
        {
            Priority_Queue = new Priority_Queue(false);
            dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
            Graph = new List<List<(long, long)>>();
            prev = Enumerable.Repeat<int>(-1, n + 1).ToArray();//前の頂点を保管する
            for (int i = 0; i <= n; i++)
            {
                Graph.Add(new List<(long, long)>());
            }
            interactive = cnt;
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph[i].Add((t, cost));
            if (interactive)
                Graph[t].Add((i, cost));
        }

        public void Start_Dijkstra(long i)
        {
            dist[i] = 0;
            Priority_Queue.Enqueue(0, i);
            while (Priority_Queue.Queue.Count != 0)
            {
                var t = Priority_Queue.Dequeue();
                int v = (int)t.Item2;
                if (dist[v] < t.Item1)
                    continue;
                for (int w = 0; w < Graph[v].Count; w++)
                {
                    var e = Graph[v][w];
                    if (dist[(int)e.Item1] <= dist[v] + e.Item2)
                        continue;
                    else
                    {
                        dist[(int)e.Item1] = dist[v] + e.Item2;
                        Priority_Queue.Enqueue(dist[(int)e.Item1], e.Item1);
                        prev[e.Item1] = v;
                    }
                }
            }
        }

        public List<(int, int)> Get_tree()
        {
            var back = new List<(int, int)>();
            for (int i = 1; i <= dist.Length - 1; i++)
            {
                back.Add((i, prev[i]));
            }
            return back;
        }


    }

    internal class Priority_Queue
    {
        toolbox toolbox = new toolbox();
        public List<(long, long)> Queue { get; private set; }
        /// <summary>
        /// true==>大きいやつから出るよ　false==>小さいやつからでるよ
        /// </summary>
        public bool revase { get; set; }
        public Priority_Queue(bool cnt = true)
        {
            Queue = new List<(long, long)>();
            revase = cnt;
        }

        public void Enqueue(long a, long b)
        {
            if (revase == false)
                a *= -1;
            int i = Queue.Count, t;
            Queue.Add((a, b));
            while (i != 0)
            {
                t = (i - 1) / 2;
                if (Queue[i].Item1 > Queue[t].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[t];
                    Queue[t] = k;
                    i = t;
                }
                else
                {
                    break;
                }
            }
        }

        public (long, long) Dequeue()
        {
            int a = Queue.Count - 1;
            var back = Queue[0];
            Queue[0] = Queue[a];
            Queue.RemoveAt(a);
            for (int i = 0, j; (j = 2 * i + 1) < a;)
            {
                if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
                    j++;
                if (Queue[i].Item1 < Queue[j].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[j];
                    Queue[j] = k;
                    i = j;
                }
                else
                {
                    break;
                }
            }
            if (revase == false)
                back.Item1 *= -1;
            return back;

        }
    }

    internal class Generic_Priority_Queue<T>
    {
        toolbox toolbox = new toolbox();
        public List<(long, T)> Queue { get; private set; }
        /// <summary>
        /// true==>大きいやつから出るよ　false==>小さいやつからでるよ
        /// </summary>
        public bool revase { get; set; }
        public Generic_Priority_Queue(bool cnt = true)
        {
            Queue = new List<(long, T)>();
            revase = cnt;
        }

        public void Enqueue(long a, T b)
        {
            if (revase == false)
                a *= -1;
            int i = Queue.Count, t;
            Queue.Add((a, b));
            while (i != 0)
            {
                t = (i - 1) / 2;
                if (Queue[i].Item1 > Queue[t].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[t];
                    Queue[t] = k;
                    i = t;
                }
                else
                {
                    break;
                }
            }
        }

        public (long, T) Dequeue()
        {
            int a = Queue.Count - 1;
            var back = Queue[0];
            Queue[0] = Queue[a];
            Queue.RemoveAt(a);
            for (int i = 0, j; (j = 2 * i + 1) < a;)
            {
                if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
                    j++;
                if (Queue[i].Item1 < Queue[j].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[j];
                    Queue[j] = k;
                    i = j;
                }
                else
                {
                    break;
                }
            }
            if (revase == false)
                back.Item1 *= -1;
            return back;

        }

        public (long, T) get_first()
        {
            if (Queue.Count == 0)
                return (default(long), default(T));
            else
                return Queue[0];
        }
    }

    internal class SPFA
    {
        private Queue<long> que;
        public long[] dist { get; set; }
        public bool interactive { get; set; }
        public List<List<(long, long)>> Graph { get; set; }

        public List<long> times { get; set; }
        public List<bool> pending { get; set; }

        public SPFA(int n, bool cnt = true)
        {
            que = new Queue<long>();
            dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
            times = Enumerable.Repeat<long>(0, n + 1).ToList();
            pending = Enumerable.Repeat<bool>(false, n + 1).ToList();
            Graph = new List<List<(long, long)>>();
            for (int i = 0; i <= n; i++)
            {
                Graph.Add(new List<(long, long)>());
            }
            interactive = cnt;
            BFS = new BFS(n, false);
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph[i].Add((t, cost));
            if (interactive)
                Graph[t].Add((i, cost));
            BFS.Connect_Graph(i, t);
        }

        public bool Start_SPFA(int i)
        {
            //(捜索を始める頂点(int))
            que.Enqueue(i);
            pending[i] = true;
            dist[i] = 0;
            times[i]++;
            while (que.Count != 0)
            {
                var t = (int)que.Dequeue();
                pending[t] = false;
                for (int w = 0; w < Graph[t].Count; w++)
                {
                    long cost_before = dist[t] + Graph[t][w].Item2;
                    if (dist[Graph[t][w].Item1] <= cost_before)
                        continue;
                    dist[Graph[t][w].Item1] = cost_before;
                    if (!pending[(int)Graph[t][w].Item1])
                    {
                        if (times[(int)Graph[t][w].Item1]++ >= Graph.Count)
                        {
                            BFS.Start_BFS((int)Graph[t][w].Item1);
                            if (BFS.dist[times.Count - 1] != -1)
                                return false;
                            else
                                continue;
                        }
                        que.Enqueue(Graph[t][w].Item1);
                        pending[(int)Graph[t][w].Item1] = true;
                    }
                }
            }
            return true;
        }


        static BFS BFS;
    }

    internal class Bellman_Ford
    {
        public long[] dist { get; set; }
        public bool interactive { get; set; }
        /// <summary>
        /// 移動元,移動先,コスト
        /// </summary>
        public List<(long, long, long)> Graph { get; set; }
        public int v;

        public Bellman_Ford(int n, bool cnt = true)
        {
            v = n;
            //ここの初期値(long.MaxValue/40)注意　オーバーフローしそう
            dist = Enumerable.Repeat<long>(long.MaxValue / 40, n + 1).ToArray();
            Graph = new List<(long, long, long)>();
            interactive = cnt;
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph.Add((i, t, cost));
            if (interactive)
                Graph.Add((t, i, cost));
        }

        public bool Start_Bellman_Ford(int i)
        {
            dist[i] = 0;
            int cnt = 0;
            while (cnt < v)
            {
                bool end = true;
                foreach (var t in Graph)
                {
                    if (t.Item1 != long.MaxValue && dist[t.Item1] + t.Item3 < dist[t.Item2])
                    {
                        dist[t.Item2] = dist[t.Item1] + t.Item3;
                        end = false;
                    }
                }
                if (end)
                    break;
                cnt++;
            }
            return (cnt == v);
        }

    }

    internal class Warshall_Floyd
    {
        public long[,] dist { get; private set; }
        public bool interactive { get; set; }
        public int v;

        public Warshall_Floyd(int n, bool cnt = true)
        {
            dist = new long[n + 1, n + 1];
            for (int i = 0; i <= n; i++)
                for (int t = 0; t <= n; t++)
                {
                    if (i == t)
                    {
                        dist[i, t] = 0;
                    }
                    else
                    {
                        dist[i, t] = long.MaxValue / 40;
                    }
                }
            interactive = cnt;
            v = n;
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            dist[i, t] = cost;
            if (interactive)
                dist[t, i] = cost;
        }

        public void Start_Warshall_Floyd()
        {
            for (int i = 1; i <= v; i++)
                for (int t = 1; t <= v; t++)
                    for (int w = 1; w <= v; w++)
                        dist[t, w] = Math.Min(dist[t, w], dist[t, i] + dist[i, w]);

            //dist[t, w] = Math.Min(dist[t, w], dist[t, i] + dist[i, w]);
        }
    }

    internal class Binary_Trie
    {
        Node tree;
        const int SZ = 64;
        //const int SZ = 12;
        int ans = 0;
        List<byte> ans_byte;

        public Binary_Trie()
        {
            tree = new Node();
            ans_byte = new List<byte>();
        }

        public void add(long i)
        {
            tree = add_fx(tree, i);
        }

        private Node add_fx(Node now, long x, int now_height = SZ - 1)
        {
            if (now == null)
                now = new Node();
            now.cnt++;
            if (now_height == -1)
                return now;
            long ne = x >> now_height & 1;
            now[(int)ne] = add_fx(now[(int)ne], x, now_height - 1);
            return now;
        }

        public void delete(long i)
        {
            tree = delete_fx(tree, i);
        }

        private Node delete_fx(Node now, long x, int now_height = SZ - 1)
        {
            if (now == null)
                return now;
            if (now.cnt == 0)
                return now;
            else
                now.cnt--;
            if (now_height == -1)
                return now;
            long ne = x >> now_height & 1;
            now[(int)ne] = delete_fx(now[(int)ne], x, now_height - 1);
            return now;
        }

        public int search(long i)
        {
            ans = 0;
            search_fx(tree, i);
            return ans;
        }

        private Node search_fx(Node now, long x, int now_height = SZ - 1)
        {
            if (now == null)
            {
                ans = 0;
                return now;
            }
            else
            {
                if (now_height == -1)
                    return now;
                long ne = x >> now_height & 1;
                ans = now.cnt;
                now[(int)ne] = search_fx(now[(int)ne], x, now_height - 1);
                return now;
            }
        }

        public int get_min_cnt(long i)
        {
            ans = 0;
            get_min_cnt_fx(tree, i);
            return ans;
        }

        private Node get_min_cnt_fx(Node now, long x, int now_height = SZ - 1)
        {
            if (now == null)
                return now;
            else
            {
                if (now_height == -1)
                {
                    ans += now.cnt;
                    return now;
                }
                long ne = x >> now_height & 1;
                if (ne == 1 && now[0] != null)
                    ans += now[0].cnt;
                now[(int)ne] = get_min_cnt_fx(now[(int)ne], x, now_height - 1);
                return now;
            }
        }

        public int get_max_cnt(long i)
        {
            ans = 0;
            get_max_cnt_fx(tree, i);
            return ans;
        }

        private Node get_max_cnt_fx(Node now, long x, int now_height = SZ - 1)
        {
            if (now == null)
                return now;
            else
            {
                if (now_height == -1)
                {
                    ans += now.cnt;
                    return now;
                }
                long ne = x >> now_height & 1;
                if (ne == 0 && now[1] != null)
                    ans += now[1].cnt;
                now[(int)ne] = get_max_cnt_fx(now[(int)ne], x, now_height - 1);
                return now;
            }
        }

        public long get_min(int xor = 0)
        {
            return get_min_fx(tree, xor);
        }

        private long get_min_fx(Node now, int xor, int now_height = SZ - 1)
        {
            if (SZ == -1) return 0;
            int ne = xor >> SZ & 1;
            if (now[ne] == null || now[ne].cnt == 0)
            {

            }
            return 1;
        }
        public void ch()
        {
            int k = 0;
        }

        public class Node
        {
            public int cnt { get; set; }
            public Node[] node = new Node[2];
            public Node()
            {
                cnt = 0;
                node[0] = null;
                node[1] = null;
            }

            public Node this[int i]
            {
                get { return this.node[i]; }
                set { this.node[i] = value; }
            }
            public void make_node(int i)
            {
                node[i] = new Node();
            }
        }

    }

    public class Kruskal
    {
        public List<(long, int, int)> Graph { get; set; }//コスト　行先、行先
        static UnionFind UnionFind;
        public Kruskal(int n)
        {
            Graph = new List<(long, int, int)>();
            UnionFind = new UnionFind(n);
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる)
            Graph.Add((cost, i, t));
        }

        public List<(long, int, int)> start_Kruskal()
        {
            var back = new List<(long, int, int)>();
            Graph = Graph.OrderBy(i => i.Item1).ToList();
            foreach (var i in Graph)
            {
                if (!UnionFind.groupcheck(i.Item2, i.Item3))
                {
                    UnionFind.unite(i.Item2, i.Item3);
                    back.Add(i);
                }
            }
            return back;
        }

        public bool conected(int x, int y)
        {
            return UnionFind.groupcheck(x, y);
        }

    }

    public class FF
    {
        public List<List<(int, long, int)>> Graph { get; set; }//行先,コスト,逆辺のインデックス
        public List<bool> flag { get; set; }
        public int end { get; set; }

        public FF(int n, int g = -1)
        {
            if (g == -1)
                g = n;
            flag = Enumerable.Repeat<bool>(false, n + 1).ToList();
            Graph = new List<List<(int, long, int)>>();
            for (int i = 0; i <= n; i++)
            {
                Graph.Add(new List<(int, long, int)>());
            }
            end = g;
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる、気合で逆辺もつなげる)
            int cnt_sei = Graph[i].Count;//正の辺のインデックス
            int cnt_gixyaku = Graph[t].Count;//逆辺のインデックス
            Graph[i].Add((t, cost, cnt_gixyaku));
            Graph[t].Add((i, 0, cnt_sei));
        }

        public int Start_FF(int x, int fl)
        {
            if (flag[x])
                return -1;
            flag[x] = true;
            if (x == end)
                return fl;
            int r = -1;
            for (int t = 0; t < Graph[x].Count; t++)
            {
                var hen = Graph[x][t];
                var w = hen.Item1;//行先
                var c = hen.Item2;//コスト
                var i = hen.Item3;//逆辺でのインデックス
                if (c == 0)
                    continue;
                r = Start_FF((int)w, (int)Math.Min(fl, c));
                if (r == -1)
                    continue;
                else
                {
                    //容量減らす
                    Graph[x][t] = (w, c - r, i);
                    //逆辺増やす
                    Graph[w][i] = (x, Graph[w][i].Item2 + r, t);
                    return r;
                }
            }
            return -1;
        }
    }

    internal class RMQ
    {
        List<int> tree { get; set; }
        int n = -1;

        public RMQ(int i)
        {

            tree = Enumerable.Range(1, i * 2).Select(i => int.MaxValue / 20).ToList();
        }

        public void update(int i, int x)
        {
            i += n - 1;
            tree[i] = x;
            while (i > 0)
            {
                i = (i - 1) / 2;
                tree[i] = Math.Min(tree[i * 2 + 1], tree[i * 2 + 2]);
            }
        }

    }

    public class TSP
    {
        /// <summary>
        /// 0indexedです！！！！　1にしたいけど無理！！！！！！！！！
        /// 引数も0indexで投げてください
        /// </summary>

        public readonly double double_inf = double.MaxValue / 128;
        const long long_inf = long.MaxValue / 128;

        public List<List<double>> dp { get; set; }
        public bool interactive { get; set; }
        public List<(double x,double y)> Graph { get; set; }

        public TSP(int n, bool cnt = true)
        {
            dp = new List<List<double>>();
            for (int i = 0; i < Math.Pow(2, n); i++)
            {
                dp.Add(new List<double>(n));
                for (int t = 0; t < n; t++)
                {
                    dp[i].Add(double_inf);
                }
            }
            Graph = new List<(double x, double y)>();
            interactive = cnt;
        }

        public void Connect_Graph(double x, double y)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph.Add((x, y));

        }

        public void start_tsp(int n)
        {
            for(int i=0; i<Graph.Count; i++)
            {
                dp[1 << i][i] = Math.Sqrt(Graph[i].x * Graph[i].x + Graph[i].y * Graph[i].y);
            }
            for (int flag = 0; flag < 1 << Graph.Count; flag++)
            {
                var cnt_get_booster = 1 << BitOperations.PopCount((uint)flag >> n);
                for (int now = 0; now < Graph.Count; now++)
                {
                    if (dp[flag][now] == double_inf)
                        continue;
                    for (int next = 0; next < Graph.Count; next++)
                    {
                            if ((flag & (1 << next)) != 0)
                                continue;
                            dp[flag | (1 << next)][next] = Math.Min(dp[flag | (1 << next)][next],dp[flag][now] + get_cost(now,next)/cnt_get_booster);
                    }
                }
            }
        }

        public double get_cost(int i,int t)
        {
            return Math.Sqrt(Math.Pow(2, (Graph[i].x - Graph[t].x) + Math.Pow(2, (Graph[i].y - Graph[t].y))));
        }
    }

}