1332_E. Height All the Same_36669
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 io
import os

from collections import Counter, defaultdict, deque

DEBUG = False


def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


def solve(N, M, L, R):
    MOD = 998244353

    num = R - L + 1
    numCells = N * M

    # Answer doesn't have to lie with L and R so can always add 2 so that only parity matters
    # Once it's a 0 and 1 matrix, adding to two adjacent is equivalent to a swap, so order doesn't matter
    # If the number of odd cells is even or number of even cells is even, flip their parity so the matrix is all odd or all even
    if numCells % 2 == 1:
        # Anything works since one of the parity must be even count
        return pow(num, numCells, MOD)

    # If num cells is even, can't have odd even cells and odd odd cells. Can only have even even cell and even odd cells
    # Want to choose `2 * i` odd cells within numCells
    # Once parity is fixed the number of choices is numOdds^(2 * i) * numEvens^(numCells - 2 * i)

    # Plug into wolfram alpha:
    # numCells = 2 * K
    # \sum_{i=0}^{K} binomial(2 * K, 2 * i) * X^(2 * i) * Y^(2 * K - 2 * i)
    K = numCells // 2
    X = num // 2  # number of values within range [L, R] that are odd
    Y = num // 2  # ditto for even
    if num % 2 != 0:
        if L % 2 == 0:
            X += 1
        else:
            Y += 1

    assert numCells % 2 == 0

    ans = (
        (pow(X + Y, numCells, MOD) + pow(X - Y, numCells, MOD)) * modInverse(2, MOD)
    ) % MOD
    if DEBUG:

        def nCr(n, r):
            def fact(i):
                if i == 0:
                    return 1
                return i * fact(i - 1)

            return fact(n) // (fact(n - r) * fact(r))

        brute = 0
        for i in range(numCells // 2 + 1):
            brute += nCr(numCells, 2 * i) * pow(X, 2 * i) * pow(Y, numCells - 2 * i)
        print(brute % MOD, ans)
        assert brute % MOD == ans

    return ans


if DEBUG:
    for n in range(1, 5):
        for m in range(1, 5):
            for l in range(1, 5):
                for r in range(l, 5):
                    if n * m < 2:
                        continue
                    solve(n, m, l, r)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, M, L, R = [int(x) for x in input().split()]
    ans = solve(N, M, L, R)
    print(ans)

2 2 1 1
 1 2 1 2
 2 2 3 4
 290186487 840456810 858082702 987072033
 646353335 282521795 600933409 772270276
 763237207 414005655 302120151 421405724
 692 210 44175861 843331069
 3 2 2 4
 2 2 1 998244353
 1 2 1 86583718
 707552887 989427996 933718708 955125306
 999999999 999999999 1 998244353
 268120620 443100795 102749301 604856694
 3 3 3 4
 3 2 2 5
 1 2 1 911660635
 3 3 1 998244353
 998244352 2 1 998244353
 13 635 761278633 941090619
 1 1000000000 1 1000000000
 3 2 3 5
 28837644 722454262 471150744 905552093
 2 2 2 5
 2 3 2 4
 1000000000 1000000000 1 998244353
 2 3 2 5
 850754220 853938121 172337487 490664825
 3 3 2 5
 672670796 425613469 728300037 940234946
 3 2 3 4
 124919287 578590669 9354715 32571540
 2 3 3 5
 3 3 1 1
 151236748 16649639 841754047 855153000
 885636311 857944136 232531966 493119835
 202669473 255300152 987865366 994537507
 140 713 711390561 727285861
 485 117 386829368 748204956
 2 2 2 4
 407070359 971940670 264302148 270591105
 461 650 18427925 104278996
 2 2 3 5
 999999999 1000000000 1755648 1000000000
 2 3 1 998244353
 2 3 3 4
 946835863 300009121 565317265 947272048
 1000000000 1 1000000000 1000000000
 564 558 305171115 960941497
 911953772 296003106 210155490 889555498
 795069900 869551950 803936044 964554424
 63719735 431492981 971536712 994663491
 589 790 462465375 766499149
 494587372 852064625 134519483 167992226
 329320172 739941588 435534601 986184053
 3 3 2 4
 741 806 424647372 965259389
 824436759 415879151 194713963 293553316
 3 3 3 5
 2 2 4 4
 290186487 963439466 858082702 987072033
 646353335 15598467 600933409 772270276
 763237207 10059688 302120151 421405724
 692 210 44175861 696277426
 3 2 1 4
 1 2 1 115138214
 929044619 989427996 933718708 955125306
 999999999 999999999 1 1751444496
 268120620 490740208 102749301 604856694
 3 1 2 5
 1 2 1 1135049535
 3 3 1 1882534256
 998244352 4 1 998244353
 13 635 761278633 1498700598
 1 1000000000 1 1000000100
 3 4 3 5
 2 1 2 5
 2 1 2 4
 4 3 2 5
 1555494676 853938121 172337487 490664825
 3 3 1 5
 672670796 425613469 346192993 940234946
 124919287 578590669 10050250 32571540
 151236748 16649639 231315154 855153000
 885636311 1133047284 232531966 493119835
 202669473 293869799 987865366 994537507
 34 713 711390561 727285861
 485 117 386829368 993670092
 565741959 971940670 264302148 270591105
 5 650 18427925 104278996
 2 2 1 5
 999999999 1000000000 1755648 1000010000
 1076117758 300009121 565317265 947272048
 564 558 167912043 960941497
 911953772 296003106 365339447 889555498
 795069900 869551950 803936044 1279842333
 589 790 462465375 979668553
 517059176 739941588 435534601 986184053
 889 806 424647372 965259389
 824436759 415879151 194713963 345824016
 3 4 1 5
 319970184 963439466 858082702 987072033
 646353335 26639522 600933409 772270276
 314730919 10059688 302120151 421405724
 692 210 44175861 663765090
 1 2 1 226264785
 929044619 989427996 423941448 955125306
 999999999 280070957 1 1751444496
 268120620 490740208 102749301 530066001
 3 3 1 1549765013
 16 635 761278633 1498700598
 1 1000000000 2 1000000100
 2 1 4 5
 1000000000 1000010000 1 157723280
 6 3 2 5
 1555494676 853938121 172337487 934154841
 6 3 1 5
 766395182 425613469 346192993 940234946
 124919287 855557585 10050250 32571540
 127955947 16649639 231315154 855153000
 885636311 1133047284 232531966 349391993
 202669473 293869799 67636906 994537507
 485 137 386829368 993670092
 5 650 7276039 104278996
 2 2 1 6
 1076117758 300009121 565317265 727297660
 1000000001 1 1000000000 1000100000
 564 558 236666487 960941497
 804532225 296003106 365339447 889555498
 795069900 486218179 803936044 1279842333
 589 790 287797694 979668553
 517059176 739941588 136502094 986184053
 889 198 424647372 965259389
 824436759 338642776 194713963 345824016
 6 4 1 5
 319970184 963439466 858082702 1717563345
 646353335 26639522 600933409 769803874
 331001581 10059688 302120151 421405724
 692 210 44175861 379655013
 1227604962 989427996 423941448 955125306
 268120620 892252233 102749301 530066001
 3 3 2 1549765013
 506732226 4 1 1036960811
 27 635 761278633 1498700598
 1000000000 1000010010 1 157723280
 1555494676 853938121 146580940 934154841
 1000000000 1000010000 1 998244353
 6 2 3 4
 2 2 2 2
 1000000001 1 1000000000 1000000000
 3 3 4 4
 2 4 1 1
 3 4 1 4
 506732226 4 1 998244353
 2 1 2 2
 6 4 3 4
 1 2 2 2
 3 2 4 4
 2 7 1 1

1
 2
 8
 366829057
 13680108
 193545831
 714028205
 365
 499122177
 499122176
 355610620
 0
 834319192
 512
 2048
 0
 0
 499122177
 893955177
 285141888
 365
 740846915
 128
 365
 499122177
 2048
 237240423
 262144
 779704132
 32
 263200129
 365
 1
 108988868
 779245677
 926661352
 641355762
 735420370
 41
 992759231
 936348652
 41
 499122177
 499122177
 32
 337235143
 1
 880111542
 225799480
 884379548
 97582142
 374887989
 552905694
 425887732
 19683
 861647194
 453443939
 19683
 1
 943089184
 868957657
 789740075
 300231232
 2048
 764729365
 333781882
 83952613
 166225280
 64
 348997428
 75798834
 499122177
 736795412
 695465869
 265721
 8
 5
 8388608
 866256663
 1953125
 29690062
 937731504
 340662707
 572179871
 162513873
 206198813
 17556038
 323945512
 775270955
 313
 806269727
 963831390
 809407133
 509074630
 815573759
 57848166
 202008368
 68845298
 437871452
 122070313
 83748992
 141379446
 486421210
 426963982
 338981825
 177053020
 478264160
 610048192
 917493570
 680575632
 869112724
 2
 955910994
 419430366
 599977663
 701918583
 175789213
 569800619
 700900828
 852097377
 373691575
 920873051
 242020515
 648
 869963988
 634146264
 153070438
 843931986
 537096643
 974322845
 945643224
 571567488
 261975244
 765389505
 969181275
 390223434
 915764022
 623382036
 854159807
 976280878
 662980583
 786632872
 954400758
 924845028
 923809870
 499122177
 2048
 1
 1
 1
 1
 8388608
 499122177
 1
 8388608
 1
 1
 1
