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.util.*;
import java.io.*;
import java.math.*;
public class Main{


	//static int p=1000000007;
	
	static long pr = 998244353;
	
	static BigInteger p =  new BigInteger(998244353+"");
	
	static void err() {
		System.out.println(-1);
	}
	
	public static void main (String args[])throws IOException{
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		
		int t = 1;
		//t = sc.nextInt();
		
		while(t-->0) {
			
			long n=sc.nextInt(), m=sc.nextInt(), l=sc.nextInt(), r=sc.nextInt(), k=r-l, even=k/2+1, odd=(k+1)/2;
			
			if((n*m)%2==1) {
				out.print(new BigInteger(k+1+"").modPow(new BigInteger(n*m+""), p));
			}else {
				
				BigInteger temp1 = new BigInteger(even+odd+"").modPow(new BigInteger(n*m+""), p);
				BigInteger temp2 = new BigInteger(even-odd+"").modPow(new BigInteger(n*m+""), p);
				
				out.println(((Long.parseLong(temp1.toString())+Long.parseLong(temp2.toString()))*(pr+1)/2)%pr);
			}
			
		}
		out.flush();
	}
	
	public static String reverseString(String str){  
	    StringBuilder sb=new StringBuilder(str);  
	    sb.reverse();  
	    return sb.toString();  
	}
	
	static boolean isPalindrome(String str) 
    { 
        int i = 0, j = str.length() - 1; 
  
        while (i < j) { 
  
            if (str.charAt(i) != str.charAt(j)) 
                return false; 
  
            
            i++; 
            j--; 
        } 
        return true;
    }
	
	
	static void print(int[] arr) {
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	
	public static int abs(int x) {return ((x > 0) ? x : -x);}
	public static long abs(long x) {return ((x > 0) ? x : -x);}
	
	public static int max(int a, int b) {return Math.max(a, b);}
	public static long max(long a, long b) {return Math.max(a, b);}
	
	public static int min(int a, int b) {return Math.min(a, b);}
	public static long min(long a, long b) {return Math.min(a, b);}
	
	
	 static int gcd(int a, int b)  
	    { 
	        if (a == 0) 
	            return b; 
	        return gcd(b % a, a); 
	    } 
	
	
    static int modInverse(int a, int m) 
    { 
        int g = gcd(a, m); 
        if (g != 1) 
            return -1;
        else 
        	return power(a, m - 2, m); 
        
    } 
      
    // To compute x^y under modulo m 
    static int power(int x, int y, int m)  
    { 
        if (y == 0) 
            return 1; 
          
        int p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    } 
	
	
    static int[] primeGenerator(int num) {
    	int length=0, arr[]=new int[num], a=num, factor=1;
    	if(num%2==0) {
    		while(num%2==0) {
    			num/=2;
    			factor*=2;
    		}
    		arr[length++]=factor;
    	}
    	for(int i=3; i*i<=a; i++) {
    		factor=1;
    		if(num%i==0) {
        		while(num%i==0) {
        			num/=i;
        			factor*=i;
        		}
        		arr[length++]=factor;
    		}
    	}
    	if(num>1)
    		arr[length++]=num;
    	return Arrays.copyOfRange(arr, 0, length);
    }
    
    


    static boolean isPrime(int n) 
    { 
        // Corner cases 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
  
        // This is checked so that we can skip 
        // middle five numbers in below loop 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
  
        for (int i = 5; i * i <= n; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
  
        return true; 
    }




	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

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

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

	static void sort(int[] a) {
		shuffle(a);
		Arrays.sort(a);
	}

	static void shuffle(int[] a) {
		int n = a.length;
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			int tmpIdx = rand.nextInt(n);
			int tmp = a[i];
			a[i] = a[tmpIdx];
			a[tmpIdx] = tmp;
		}
	}
}

class Pair{
	int x;
	int y;
	Pair(int a, int b){
		x=a;
		y=b;
	}
	
	void print() {
		System.out.println(this.x+" "+this.y);
	}
}

