An online contest will soon be held on ForceCoders, a large competitive programming platform. The authors have prepared n problems; and since the platform is very popular, 998244351 coder from all over the world is going to solve them.

For each problem, the authors estimated the number of people who would solve it: for the i-th problem, the number of accepted solutions will be between l_i and r_i, inclusive.

The creator of ForceCoders uses different criteria to determine if the contest is good or bad. One of these criteria is the number of inversions in the problem order. An inversion is a pair of problems (x, y) such that x is located earlier in the contest (x < y), but the number of accepted solutions for y is strictly greater.

Obviously, both the creator of ForceCoders and the authors of the contest want the contest to be good. Now they want to calculate the probability that there will be no inversions in the problem order, assuming that for each problem i, any integral number of accepted solutions for it (between l_i and r_i) is equally probable, and all these numbers are independent.

Input

The first line contains one integer n (2 ≤ n ≤ 50) — the number of problems in the contest.

Then n lines follow, the i-th line contains two integers l_i and r_i (0 ≤ l_i ≤ r_i ≤ 998244351) — the minimum and maximum number of accepted solutions for the i-th problem, respectively.

Output

The probability that there will be no inversions in the contest can be expressed as an irreducible fraction x/y, where y is coprime with 998244353. Print one integer — the value of xy^{-1}, taken modulo 998244353, where y^{-1} is an integer such that yy^{-1} ≡ 1 (mod 998244353).

Examples

Input


3
1 2
1 2
1 2


Output


499122177


Input


2
42 1337
13 420


Output


578894053


Input


2
1 1
0 0


Output


1


Input


2
1 1
1 1


Output


1

Note

The real answer in the first test is 1/2.
/**
 * BaZ :D
 */

import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class ACMIND
{
    static FastReader scan;
    static PrintWriter pw;
    static long MOD = 998244353;
    static long INF = 1_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null,null,"BaZ",1<<27)
        {
            public void run()
            {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
    static int n,l[],r[];
    static boolean can[][];
    static ArrayList<Pair> segments;
    static long res,dp[][][];
    static void solve() throws IOException
    {
        scan = new FastReader();
        pw = new PrintWriter(System.out,true);
        StringBuilder sb = new StringBuilder();
        n = ni();
        l = new int[n];
        r = new int[n];
        TreeSet<Integer> set = new TreeSet<>();
        for(int i=0;i<n;++i) {
            l[i] = ni();
            r[i] = ni();
            set.add(l[i]);
            set.add(r[i]);
        }
        segments = new ArrayList<>();
        while(!set.isEmpty()) {
            int x = set.pollFirst();
            segments.add(new Pair(x,x));
            if(!set.isEmpty() && x+1<set.first()) {
                segments.add(new Pair(x+1, set.first()-1));
            }
        }
        //pa("segments", segments);
        can = new boolean[n][segments.size()];
        for(int i=0;i<n;++i) {
            for(int j=0;j<segments.size();++j) {
                if(segments.get(j).x >= l[i] && segments.get(j).y<=r[i]) {
                    can[i][j] = true;
                }
            }
        }
//        for(int i=0;i<n;++i) {
//            for(int j=0;j<segments.size();++j) {
//                p(can[i][j]);
//            }
//            pl();
//        }
        dp = new long[n][segments.size()][n+1];
        for(int i=0;i<n;++i) {
            for(int j=0;j<segments.size();++j) {
                for(int k=0;k<=n;++k) {
                    dp[i][j][k] = -1;
                }
            }
        }
        long den = 1;
        for(int i=0;i<n;++i) {
            den*=1L * (r[i] - l[i] + 1);
            den%=MOD;
        }
        //pl("Den : "+den);
        long ans = f(0,segments.size() - 1,0);
        //pl("ans : "+ans);
        ans*=modpow(den, MOD-2, MOD);
        ans%=MOD;
        pl(ans);
        pw.flush();
        pw.close();
    }
    static long f(int idx, int which, int prev) {
        if(idx==n) {
            if(which>=0) {
                return calc(segments.get(which).y - segments.get(which).x + prev ,prev);
            }
            return 0;
        }
        if(which<0) {
            return 0;
        }
        if(dp[idx][which][prev] != -1) {
            return dp[idx][which][prev];
        }
        long ans = 0;
        if(can[idx][which]) {
            ans+=f(idx+1, which, prev+1);
        }
        ans+=calc(segments.get(which).y - segments.get(which).x + prev ,prev) * f(idx, which-1, 0);
        ans%=MOD;
        return dp[idx][which][prev] = ans;
    }
    static long calc(long n, long r) {
        if(r<0 || r>n) {
            return 0;
        }
        long num = 1, den = 1;
        for(int i=1;i<=r;++i) {
            num*=(n-r+i);
            num%=MOD;
            den*=i;
            den%=MOD;
        }
        return (num*modpow(den, MOD-2, MOD))%MOD;
    }
    static long modpow(long x,long y,long mod)
    {
        res = 1;
        while(y>0)
        {
            if((y&1)==1)
                res = (res*x)%mod;
            y>>=1;
            x = (x*x)%mod;
        }
        return res;
    }
    static class Pair implements Comparable<Pair>
    {
        int x,y;
        Pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
        public int compareTo(Pair other)
        {
            if(this.x!=other.x)
                return this.x-other.x;
            return this.y-other.y;
        }
        public String toString()
        {
            return "("+x+","+y+")";
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[1000000];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
}
