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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Map;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.Collection;
import java.io.IOException;
import java.util.stream.Collectors;
import java.io.UncheckedIOException;
import java.util.List;
import java.util.stream.Stream;
import java.util.TreeMap;
import java.io.Closeable;
import java.io.Writer;
import java.util.Map.Entry;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            FGoodContest solver = new FGoodContest();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class FGoodContest {
        Modular mod = new Modular(998244353);
        Power power = new Power(mod);
        GravityModLagrangeInterpolation zero = new GravityModLagrangeInterpolation(mod, 1);
        GravityModLagrangeInterpolation one = new GravityModLagrangeInterpolation(mod, 1);
        int trainLimit = 100;

        {
            zero.addPoint(0, 0);
            one.addPoint(0, 1);
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int[][] lr = new int[n][2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 2; j++) {
                    lr[i][j] = in.readInt();
                }
            }

            SequenceUtils.reverse(lr, 0, n - 1);
            SegmentFunctions functions = new SegmentFunctions();
            functions.add(new SegmentFunction(-1, lr[0][0] - 1, zero));
            functions.add(new SegmentFunction(lr[0][0], lr[0][1], one));
            functions.add(new SegmentFunction(lr[0][1] + 1, (int) 1e9, zero));

            for (int i = 1; i < n; i++) {
                functions = build(functions, lr[i][0], lr[i][1], true);
            }

            functions = build(functions, 0, (int) 1e9 - 1, false);
            int valid = functions.apply((int) 1e9).p.getYByInterpolation((int) 1e9);
            int total = 1;
            for (int[] x : lr) {
                total = mod.mul(total, x[1] - x[0] + 1);
            }
            int ans = mod.mul(valid, power.inverseByFermat(total));
            out.println(ans);
        }

        public SegmentFunctions build(SegmentFunctions functions, int l, int r, boolean addTail) {
            List<Interval> intervals = new ArrayList<>();
            for (SegmentFunction x : functions.functionTreeSet.values()) {
                intervals.add(x.interval);
            }
            for (Interval interval : intervals) {
                if (interval.contain(l)) {
                    intervals.remove(interval);
                    intervals.addAll(Arrays.asList(interval.split(l - 1)));
                    break;
                }
            }
            for (Interval interval : intervals) {
                if (interval.contain(r)) {
                    intervals.remove(interval);
                    intervals.addAll(Arrays.asList(interval.split(r)));
                    break;
                }
            }
            intervals = intervals.stream().filter(x -> !x.empty()).collect(Collectors.toList());
            intervals.sort((a, b) -> a.l - b.l);
            SegmentFunctions ans = new SegmentFunctions();
            ans.add(new SegmentFunction(intervals.get(0).l - 1, intervals.get(0).l - 1, zero));
            for (Interval interval : intervals) {
                if (interval.l > r) {
                    break;
                }
                GravityModLagrangeInterpolation interpolation = new GravityModLagrangeInterpolation(mod, trainLimit);
                SegmentFunction tail = ans.functionTreeSet.lastEntry().getValue();
                SegmentFunction bot = functions.apply(interval.l);
                int ps = tail.p.getYByInterpolation(interval.l - 1);
                for (int i = 0; i < trainLimit; i++) {
                    int x = mod.valueOf(interval.l + i);
                    ps = mod.plus(ps, bot.p.getYByInterpolation(x));
                    interpolation.addPoint(x, ps);
                }
                ans.add(new SegmentFunction(interval.l, interval.r, interpolation));
            }
            while (ans.functionTreeSet.firstKey() < l) {
                ans.functionTreeSet.pollFirstEntry();
            }
            ans.add(new SegmentFunction(intervals.get(0).l, l - 1, zero));
            if (addTail) {
                ans.add(new SegmentFunction(r + 1, intervals.get(intervals.size() - 1).r, zero));
            }
            return ans;
        }

    }

    static class Modular {
        int m;

        public Modular(int m) {
            this.m = m;
        }

        public Modular(long m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public Modular(double m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public int valueOf(int x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return x;
        }

        public int valueOf(long x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return (int) x;
        }

        public int mul(int x, int y) {
            return valueOf((long) x * y);
        }

        public int plus(int x, int y) {
            return valueOf(x + y);
        }

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

        public String toString() {
            return "mod " + m;
        }

    }

    static class SequenceUtils {
        public static <T> void swap(T[] data, int i, int j) {
            T tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        public static <T> void reverse(T[] data, int l, int r) {
            while (l < r) {
                swap(data, l, r);
                l++;
                r--;
            }
        }

    }

    static class SegmentFunction {
        Interval interval;
        GravityModLagrangeInterpolation p;

        public SegmentFunction(int l, int r, GravityModLagrangeInterpolation p) {
            this.interval = new Interval(l, r);
            this.p = p;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class GravityModLagrangeInterpolation {
        private Power power;
        private Modular modular;
        Map<Integer, Integer> points = new HashMap<>();
        Polynomial xs;
        Polynomial ys;
        Polynomial lx;
        Polynomial lxBuf;
        Polynomial invW;
        int n;

        public GravityModLagrangeInterpolation(Modular modular, int expect) {
            this(new Power(modular), expect);
        }

        public GravityModLagrangeInterpolation(Power power, int expect) {
            this.modular = power.getModular();
            this.power = power;
            xs = new Polynomial(expect);
            ys = new Polynomial(expect);
            lx = new Polynomial(expect);
            lxBuf = new Polynomial(expect);
            invW = new Polynomial(expect);
            lx.setN(1);
            lx.coes[0] = 1;
        }

        public void addPoint(int x, int y) {
            x = modular.valueOf(x);
            y = modular.valueOf(y);
            Integer exist = points.get(x);
            if (exist != null) {
                if (exist != y) {
                    throw new RuntimeException();
                }
                return;
            }
            points.put(x, y);

            xs.setN(n + 1);
            xs.coes[n] = x;
            ys.setN(n + 1);
            ys.coes[n] = y;
            lx.multiply(modular.valueOf(-x), lxBuf);
            switchBuf();
            invW.setN(n + 1);
            invW.coes[n] = 1;
            for (int i = 0; i < n; i++) {
                invW.coes[i] = modular.mul(invW.coes[i], modular.subtract(xs.coes[i], x));
                invW.coes[n] = modular.mul(invW.coes[n], modular.subtract(x, xs.coes[i]));
            }
            n++;
        }

        public int getYByInterpolation(int x) {
            x = modular.valueOf(x);
            if (points.containsKey(x)) {
                return points.get(x);
            }

            int y = lx.function(x);
            int sum = 0;
            for (int i = 0; i < n; i++) {
                int val = modular.mul(invW.coes[i], modular.subtract(x, xs.coes[i]));
                val = modular.mul(power.inverseByFermat(val), ys.coes[i]);
                sum = modular.plus(sum, val);
            }

            return modular.mul(y, sum);
        }

        public Polynomial preparePolynomial() {
            Polynomial ans = new Polynomial(n);
            Polynomial ansBuf = new Polynomial(n);
            for (int i = 0; i < n; i++) {
                int c = modular.mul(ys.coes[i], power.inverseByFermat(invW.coes[i]));
                lx.div(modular.valueOf(-xs.coes[i]), ansBuf);
                ansBuf.mulConstant(c, ansBuf);
                ans.plus(ansBuf, ans);
            }
            return ans;
        }

        private void switchBuf() {
            Polynomial tmp = lx;
            lx = lxBuf;
            lxBuf = tmp;
        }

        public String toString() {
            return preparePolynomial().toString();
        }

        public class Polynomial {
            private int[] coes;
            private int n;

            public int function(int x) {
                int ans = 0;
                int xi = 1;
                for (int i = 0; i < n; i++) {
                    ans = modular.plus(ans, modular.mul(xi, coes[i]));
                    xi = modular.mul(xi, x);
                }
                return ans;
            }

            public Polynomial(int n) {
                this.n = 0;
                coes = new int[n];
            }

            public void ensureLength() {
                if (coes.length >= n) {
                    return;
                }
                int proper = coes.length;
                while (proper < n) {
                    proper = Math.max(proper + proper, proper + 10);
                }
                coes = Arrays.copyOf(coes, proper);
            }

            public void setN(int n) {
                this.n = n;
                ensureLength();
            }

            public void multiply(int b, Polynomial ans) {
                ans.setN(n + 1);
                for (int i = 0; i < n; i++) {
                    ans.coes[i] = modular.mul(coes[i], b);
                }
                ans.coes[n] = 0;
                for (int i = 0; i < n; i++) {
                    ans.coes[i + 1] = modular.plus(ans.coes[i + 1], coes[i]);
                }
            }

            public void mulConstant(int b, Polynomial ans) {
                ans.setN(n);
                for (int i = 0; i < n; i++) {
                    ans.coes[i] = modular.mul(coes[i], b);
                }
            }

            public void plus(Polynomial a, Polynomial ans) {
                ans.setN(Math.max(n, a.n));
                for (int i = 0; i < n; i++) {
                    ans.coes[i] = coes[i];
                }
                for (int i = 0; i < a.n; i++) {
                    ans.coes[i] = modular.plus(ans.coes[i], a.coes[i]);
                }
            }

            public void div(int b, Polynomial ans) {
                ans.setN(n - 1);
                int affect = 0;
                for (int i = n - 1; i >= 1; i--) {
                    affect = modular.plus(affect, coes[i]);
                    ans.coes[i - 1] = affect;
                    affect = modular.mul(-affect, b);
                }
            }

            public String toString() {
                return Arrays.toString(Arrays.copyOfRange(coes, 0, n));
            }

        }

    }

    static class Interval {
        int l;
        int r;

        public boolean contain(int x) {
            return l <= x && x <= r;
        }

        public boolean empty() {
            return l > r;
        }

        public Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }

        public Interval[] split(int m) {
            return new Interval[]{new Interval(l, m), new Interval(m + 1, r)};
        }

        public String toString() {
            return "(" + l + "," + r + ")";
        }

    }

    static class FastOutput implements AutoCloseable, Closeable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput println(int c) {
            cache.append(c);
            println();
            return this;
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class Power {
        final Modular modular;

        public Modular getModular() {
            return modular;
        }

        public Power(Modular modular) {
            this.modular = modular;
        }

        public int pow(int x, int n) {
            if (n == 0) {
                return modular.valueOf(1);
            }
            long r = pow(x, n >> 1);
            r = modular.valueOf(r * r);
            if ((n & 1) == 1) {
                r = modular.valueOf(r * x);
            }
            return (int) r;
        }

        public int inverseByFermat(int x) {
            return pow(x, modular.m - 2);
        }

    }

    static class SegmentFunctions {
        TreeMap<Integer, SegmentFunction> functionTreeSet = new TreeMap<>();

        public void add(SegmentFunction function) {
            functionTreeSet.put(function.interval.l, function);
        }

        public SegmentFunction apply(int x) {
            SegmentFunction function = functionTreeSet.floorEntry(x).getValue();
            return function;
        }

    }
}

