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.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<long long, long long>;
const long long MOD = 998244353;
const long long INF = 2000000000;
const long long DESPACITO = 1000000000000000000;
namespace minmax {
template <class T>
T max(T&& A) {
  return A;
}
template <class T>
T min(T&& A) {
  return A;
}
template <class T>
T max(T&& A, T&& B) {
  return A > B ? A : B;
}
template <class T>
T chmin2(T&& A, T&& B) {
  return A < B ? A : B;
}
template <class T, class... Ts>
T max(T&& A, Ts&&... ts) {
  T B = max(ts...);
  return A > B ? A : B;
}
template <class T, class... Ts>
T min(T&& A, Ts&&... ts) {
  T B = min(ts...);
  return A < B ? A : B;
}
template <class T, class... Ts>
T chmax(T&& A, Ts&&... ts) {
  A = max(A, ts...);
  return A;
}
template <class T, class... Ts>
T chmin(T&& A, Ts&&... ts) {
  A = min(A, ts...);
  return A;
}
template <class T1, class T2>
void chmin2(T1&& A, T2&& Aa, T1&& B, T2&& Bb) {
  if (B < A) A = B, Aa = Bb;
}
template <class T1, class T2>
void chmax2(T1&& A, T2&& Aa, T1&& B, T2&& Bb) {
  if (B > A) A = B, Aa = Bb;
}
}  // namespace minmax
namespace input {
template <class T>
void re(T&& Xx) {
  cin >> Xx;
}
template <class T1, class T2>
void re(pair<T1, T2>& Pp) {
  re(Pp.first);
  re(Pp.second);
}
template <class T>
void re(vector<T>& Aa) {
  for (long long i = 0; i < (long long)(Aa).size(); i++) re(Aa[i]);
}
template <class T1, class T2>
void rea(T1&& Aa, T2 t) {
  for (long long i = 0; i < t; i++) re(Aa[i]);
}
template <class T1, class T2, class... Ts>
void rea(T1&& Aa, T2 t, Ts&&... ts) {
  rea(Aa, t);
  rea(ts...);
}
template <class T1, class T2>
void rea1(T1&& Aa, T2 t) {
  for (long long i = 1; i <= t; i++) re(Aa[i]);
}
template <class T1, class T2, class... Ts>
void rea1(T1&& Aa, T2 t, Ts&... ts) {
  rea1(Aa, t);
  rea1(ts...);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int32_t Xx) { cout << Xx; }
void pr(bool Xx) { cout << Xx; }
void pr(long long Xx) { cout << Xx; }
void pr(long long unsigned Xx) { cout << Xx; }
void pr(double Xx) { cout << Xx; }
void pr(char Xx) { cout << Xx; }
void pr(const string& Xx) { cout << Xx; }
void pr(const char* Xx) { cout << Xx; }
void pr(const char* Xx, size_t len) { cout << string(Xx, len); }
void ps() { cout << "\n"; }
void pn() {}
void pw() { pr(" "); }
void pc() {
  pr("]");
  ps();
}
template <class T1, class T2>
void pr(const pair<T1, T2>& Xx) {
  pr(Xx.first);
  pw();
  pr(Xx.second);
}
template <class T>
void pr(const T&);
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
bool parsepair(const pair<T1, T2>& Xx) {
  return true;
}
template <class T>
bool parsepair(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& Aa, T2 t) {
  for (long long i = 0; i < t; i++) pr(Aa[i]), pw();
  ps();
}
template <class T1, class T2>
void pna(T1&& Aa, T2 t) {
  for (long long i = 0; i < t; i++) pr(Aa[i]), ps();
}
template <class T1, class T2>
void psa2(T1&& Aa, T2 t1, T2 t2) {
  for (long long i = 0; i < t1; i++) {
    for (long long j = 0; j < t2; j++) pr(Aa[i][j]), pw();
    ps();
  }
}
template <class T>
void pr(const T& Xx) {
  if (!(long long)(Xx).size()) return;
  bool fst = 1;
  bool op = 0;
  if (parsepair(*Xx.begin())) op = 1;
  for (const auto& Aa : Xx) {
    if (!fst) pw();
    if (op) pr("{");
    pr(Aa), fst = 0;
    if (op) pr("}");
  }
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pw();
  }
  ps(ts...);
}
template <class T>
void pn(const T& t) {
  for (const auto& Aa : t) ps(Aa);
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pw();
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  bool op = 0;
  if (parsepair(t)) op = 1;
  if (op) pr("{");
  pr(t);
  if (op) pr("}");
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& Xx, const T2& y) {
  pr("[", y, "] = ");
  ps(Xx);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& Xx, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, Xx, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& Xx, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, Xx, y, rest...);
}
template <class T>
void __fn(long long n, const char* name, const T& Xx) {
  for (long long i = 0; i < n; i++) pr(name), __f(name, Xx[i], i);
}
}  // namespace trace
}  // namespace output
using namespace minmax;
using namespace input;
using namespace output;
using namespace output::trace;
const long long N = 2e5 + 5;
template <class T1, class T2>
long long expo(T1 A, T2 B) {
  if (B == 0) return 1;
  if (B & 1) return (long long)(1ll * A * expo(A, B - 1) % MOD);
  A = expo(A, B / 2);
  return (long long)(1ll * A * A % MOD);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long i, n, m, l, r;
  re(n, m, l, r);
  n *= m;
  if (n & 1) return ps(expo(r - l + 1, n)), 0;
  long long x = l + (l & 1);
  long long y = r - (r & 1);
  long long even = (r - l) / 2 + 1;
  long long odd = (r - l + 1) - even;
  long long ans = expo(odd + even, n) + expo(abs(odd - even), n);
  ans %= MOD;
  ans *= expo(2ll, MOD - 2);
  ans %= MOD;
  ps(ans);
  return 0;
}
