[Codeforces Round #630 (Div. 2)] - E. Height All the Same （组合数学）

E. Height All the Same

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Alice has got addicted to a game called Sirtet recently.

In Sirtet, player is given an n×mn×m grid. Initially ai,jai,j cubes are stacked up in the cell (i,j)(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.

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≤ai,j≤RL≤ai,j≤R for all 1≤i≤n1≤i≤n, 1≤j≤m1≤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,353998,244,353.

Input

The only line contains four integers nn, mm, LL and RR (1≤n,m,L,R≤1091≤n,m,L,R≤109, L≤RL≤R, n⋅m≥2n⋅m≥2).

Output

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

Examples

input

Copy

2 2 1 1

output

Copy

1

input

Copy

1 2 1 2

output

Copy

2

Note

In the first sample, the only initial grid that satisfies the requirements is a1,1=a2,1=a1,2=a2,2=1a1,1=a2,1=a1,2=a2,2=1. Thus the answer should be 11.

In the second sample, initial grids that satisfy the requirements are a1,1=a1,2=1a1,1=a1,2=1 and a1,1=a1,2=2a1,1=a1,2=2. Thus the answer should be 22.

题意：

现在有一个\(n*m\)的方格，第\(\mathit i\)行第\(\mathit j\)列有\(a[i][j]\)个方块。

你可以执行以下操作任意次：

1、选择\((i,j)\)使\(a[i][j]\)加上\(\text 2\)。

2、选择两个相邻的方格，将其方格数加上\(\text 1\)。

现在问初始\(a[i][j]\)可以是\([L,R]\)中的任意数，有多少种初始方案可以通过任意次数的操作后使所有的\(a[i][j]\)相等。

思路：

因为操作1不改变奇偶性，而同奇偶性的数一定可以通过操作1变成相等的数，所以对于一个\(n*m\)的方格，只考虑其奇偶性，问题可以转化为，能否选择两个相邻的方格，使其奇偶性翻转，最后使整个方格奇偶性一致。

这是一个经典的问题，解法为：奇数和偶数的个数都是奇数是不行的，否则可行。

可以观看下图，红色代表奇数，白色代表偶数。

我们可以通过一次翻转使其变成：

当将奇数移动到一些特殊的位置后，有因为剩下的偶数的个数\(cnt\)为偶数，可以通过\(cnt/2\)次翻转操作变为：

全部变成红色（奇数）。

只要奇数的个数和偶数个数的至少一个为偶数，就可以通过这种方法将其变成同奇偶性。

来思考本题的2种情况：

如果\(n*m\)是奇数，那么奇数的个数和偶数个数的至少一个为偶数，则所有初始状态都满足条件。

答案为\((R-L+1)^{n*m}\)。

否则，设\(\mathit x\)为\([L,R]\)中奇数的个数，设\(\mathit y\)为\([L,R]\)中偶数的个数。

\(ans= \sum _{i=0}^{n*m}C^{i}_{n*m}*x^i*y^{n*m-i},i\%2=0\)

那么答案就是\(\sum _{i=0}^{n*m}C^{i}_{n*m}*x^i*y^{n*m-i}\)二项式中偶数项的和。

构造二项式\((x-y)^{n*m}=\sum _{i=0}^{n*m}C^{i}_{n*m}*x^i*y^{n*m-i}*(-1)^{n*m-i},(-1)^{n*m-i}=(-1)^i\)的奇偶项为正负交替的。

则：

\(ans=\frac{(x+y)^{n*m}+(x-y)^{n*m}}{2}\)

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const ll mod = 998244353;

int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    ll n, m, l, r;
    cin >> n >> m >> l >> r;
    ll x = r - l + 1;
    if (n * m % 2 == 1)
    {
        printf("%lld\n", powmod(x, n * m, mod) );
    } else
    {
        ll ans = powmod(x, n * m, mod) + ((x & 1) ? 1 : 0);
        ans %= mod;
        ans = ans * powmod(2ll, mod - 2ll, mod);
        ans %= mod;
        printf("%lld\n", ans );
    }
    return 0;
}