Alice has got addicted to a game called Sirtet recently.

In Sirtet, player is given an n × m grid. Initially a_{i,j} cubes are stacked up in the cell (i,j). Two cells are called adjacent if they share a side. Player can perform the following operations: 

  * stack up one cube in two adjacent cells; 
  * stack up two cubes in one cell. 



Cubes mentioned above are identical in height.

Here is an illustration of the game. States on the right are obtained by performing one of the above operations on the state on the left, and grey cubes are added due to the operation.

<image>

Player's goal is to make the height of all cells the same (i.e. so that each cell has the same number of cubes in it) using above operations. 

Alice, however, has found out that on some starting grids she may never reach the goal no matter what strategy she uses. Thus, she is wondering the number of initial grids such that 

  * L ≤ a_{i,j} ≤ R for all 1 ≤ i ≤ n, 1 ≤ j ≤ m; 
  * player can reach the goal using above operations. 



Please help Alice with it. Notice that the answer might be large, please output the desired value modulo 998,244,353.

Input

The only line contains four integers n, m, L and R (1≤ n,m,L,R ≤ 10^9, L ≤ R, n ⋅ m ≥ 2).

Output

Output one integer, representing the desired answer modulo 998,244,353.

Examples

Input


2 2 1 1


Output


1


Input


1 2 1 2


Output


2

Note

In the first sample, the only initial grid that satisfies the requirements is a_{1,1}=a_{2,1}=a_{1,2}=a_{2,2}=1. Thus the answer should be 1.

In the second sample, initial grids that satisfy the requirements are a_{1,1}=a_{1,2}=1 and a_{1,1}=a_{1,2}=2. Thus the answer should be 2.
import java.awt.*;
import java.io.*;
import java.lang.reflect.Array;
import java.util.StringTokenizer;
import java.util.*;

public class Solution {
    private static final long mod = 998244353;
    static short dp[][];
    static HashMap<Integer,ArrayList<Integer>> map ;
    static HashMap<Integer,String> hm;
    static int n;

    public static void main(String args[]) throws Exception {

        FastScanner sc = new FastScanner();

        int t;
        t = 1;//sc.nextInt();
        PrintWriter out = new PrintWriter(System.out);

        while (t-- > 0) {
            solve(sc, out);
        }
        out.close();


    }

    public static void solve(FastScanner sc, PrintWriter out) {
        long n = sc.nextInt();
        long m = sc.nextLong();
        long l = sc.nextInt();
        long r = sc.nextInt();

        long ans = 0;
        long k = r - l + 1;
        ans = pow(k,n*m,mod );

        if(n*m % 2 == 0){
            if(k % 2 != 0)
                ans = (ans + 1)%mod;
         ans = (ans *  modInverse(2,mod))%mod;
           // ans = ans / 2;
        }

        out.println(ans);
    }

    public static long pow(long a, long n, long mod){
        if(n == 0) return 1;
        else if(n%2 == 0){
            return pow((a*a)%mod,n/2,mod)%mod;
        }
        else return (pow((a*a)%mod,n/2,mod)%mod * a)%mod;
    }

    public static long modInverseCoPrime(long n, long mod){
        return pow(n,mod-2,mod);
    }

    static long modInverse(long A, long M)
    {
        extendedEuclid(A,M);
        return (x%M+M)%M;    //x may be negative
    }

    static long d, x, y;
    static void extendedEuclid(long A, long B) {
        if(B == 0) {
            d = A;
            x = 1;
            y = 0;
        }
        else {
            extendedEuclid(B, A%B);
            long temp = x;
            x = y;
            y = temp - (A/B)*y;
        }
    }

    public static boolean recurse(ArrayList<Integer> ans, int i, int k, ArrayList<String> in){
    if (i == n) {
      if (k == 0) return true;
      return false;
          }
        if(k < 0) return false;

        if(dp[i][k] != 0) return dp[i][k] == 1? true: false;

        int valid = -1;
        String input = in.get(i);
        ArrayList<Pair> p = getNumbers(input);
        boolean check = false;
        for(Pair element : p){
            if(recurse(ans,i+1,k-element.y,in)){
                valid = Math.max(valid, element.x);
                check = true;
                break;
            }
        }


        if(check){ dp[i][k] = 1;ans.add(valid);}
        else dp[i][k] = 2;
        return check;

    }

    public static ArrayList<Pair> getNumbers(String a){
        ArrayList<Pair> ans = new ArrayList<>();


        for (int i = 9; i >=0; i--) {
            int count = 0;
            boolean check = true;
            String b = hm.get(i);
            for (int j = 0; j < a.length(); j++) {
                if (a.charAt(j) == '1' && b.charAt(j) != '1') {check = false; break;}
                if (a.charAt(j) == '0' && b.charAt(j) == '1') count++;
            }

        if (check)
            ans.add(Pair.of(i,count));

        }

        return ans;
    }


    public static  <T> void clear(HashMap<Integer,ArrayList<T>> hm){
        for(int key : hm.keySet())
            hm.put(key, new ArrayList<>());
    }

    public static  <T> void fill(HashMap<Integer,ArrayList<T>> hm, int m){
        for(int i = 1;i<=m;i++)
            hm.put(i, new ArrayList<>());
    }



    static long calcChanges(long[] a, long val, int n, long k){
        long ans = 0;
        for(int i = 1;i<=n/2;i++){
            long x = a[i];
            long y = a[n-i-1];
            if((k + x < val && k + y < val) || ( 1 + x > val && 1 + y > val)){
                ans = ans + 2;
            } else if(x + y != val) ans = ans + 1;
        }
        return ans;
    }


    public static class Pair{
        int x;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pair)) return false;
            Pair pair = (Pair) o;
            return x == pair.x &&
                    y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        int y;
        public static Pair of(int x, int y){
            Pair p = new Pair();
            p.x = x;
            p.y = y;
            return p;
        }
    }



    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public String next() {
            while (!st.hasMoreElements())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

    }
}



class DFS{


    public void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n  = sc.nextInt();
        Graph g = new Graph();
        for(int i = 1;i<=n;i++)
            g.addNode(i);

        int e = sc.nextInt();
        while(e-->0){
            int one = sc.nextInt();
            int two = sc.nextInt();
            g.addEdge(one, two);
            g.addEdge(two, one);
        }
        g.resetVisited();
        g.DFS(g.nodes.get(1));


    }
}


class Node{
    int label;
    long touristP;
    long sum;
    Node parent;
    boolean visited = false;
    Node(int l){
        label=l;
        sum = 0;
        touristP = 0;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Node)) return false;
        Node node = (Node) o;
        return label == node.label &&
                touristP == node.touristP &&
                sum == node.sum &&
                visited == node.visited;
    }

    @Override
    public int hashCode() {
        return Objects.hash(label);
    }
}

class Graph{

    HashMap<Node,ArrayList<Node>> hm = new HashMap<>();
    HashMap<Integer,Node> nodes = new HashMap<>();
    Graph(){

    }

    void addNode(int n){
        Node node= new Node(n);
        this.nodes.put(n,node);
    }

    void addEdge(int f,int t){
        Node from = nodes.get(f);
        Node to = nodes.get(t);
        if(!hm.containsKey(from))
            hm.put(from,new ArrayList<>());

        hm.get(from).add(to);
    }

    void resetVisited(){
        for(Node n : hm.keySet()){
            n.visited = false;
            for(Node nn:hm.get(n))
                nn.visited = false;
        }
    }

    void DFS(Node n){
        if(n.visited)
            return;

        n.visited = true;
        System.out.print(n.label + " ");
        if(hm.containsKey(n))
            for(Node an : hm.get(n))
                DFS(an);
    }


    long DFSSum(Node n){
        if(n.visited)
            return 0l;

        n.visited = true;
        if(hm.containsKey(n)) {
            for (Node an : hm.get(n)) {
                n.sum = n.sum + DFSSum(an);

            }
        }

        return n.sum+1;
    }

    void BFS(Node n){
        Queue<Node> q = new LinkedList<>();
        q.add(n);

        while(!q.isEmpty()){
            Node node = q.poll();

            System.out.print(node.label+" ");
            node.visited = true;

            if(!hm.containsKey(node))
                continue;

            for(Node nn: hm.get(node)){
                if(nn.visited == false)
                {
                    if(!nn.visited)
                        q.add(nn);
                }
            }
        }

    }
}
