Đồng đều chiều cao

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một lưới $n \times m$ . Ban đầu tại ô $(i, j)$ có $a_{i, j}$ khối lập phương được xếp chồng lên nhau. Người chơi có thể thực hiện các thao tác sau bao nhiêu lần tùy ý:

Chọn hai ô kề cạnh và đặt thêm một khối lên mỗi ô đó (tổng cộng thêm $2$ khối).
Chọn một ô và đặt thêm hai khối lên ô đó.

Mục tiêu là đưa lưới về trạng thái mà tất cả các ô có cùng số khối.

Người chơi muốn biết: có bao nhiêu lưới khởi đầu ${a_{i, j}}$ thỏa mãn:

$L \leq a_{i, j} \leq R$ với mọi $1 \leq i \leq n$ , $1 \leq j \leq m$ ;
Có thể đạt được mục tiêu bằng các thao tác nêu trên.

Vì đáp số có thể rất lớn, hãy in ra phần dư khi chia cho $998 244 353$ .

Dữ liệu vào

Một dòng duy nhất chứa bốn số nguyên $n$ , $m$ , $L$ , $R$ .

Dữ liệu ra

In ra một số nguyên — đáp số cần tìm theo modulo $998 244 353$ .

Ràng buộc

$1 \leq n, m, L, R \leq 10^{9}$
$L \leq R$
$n \cdot m \geq 2$

Ví dụ

Input	Output	Giải thích
2 2 1 1	1	Lưới duy nhất thỏa mãn là $a_{1, 1} = a_{2, 1} = a_{1, 2} = a_{2, 2} = 1$ (đã đồng đều sẵn).
1 2 1 2	2	Hai lưới hợp lệ: $(1, 1)$ và $(2, 2)$ . Hai lưới $(1, 2)$ và $(2, 1)$ có tổng lẻ nên không thể về cùng giá trị.

Bình luận

Không có bình luận tại thời điểm này.