Professor Alex is an expert in the study of ancient buildings.

When he was surveying an ancient temple, he found ruins containing several fallen stone pillars. There are $$$n$$$ stone pillars in the ruins, numbered $$$1,2,\cdots,n$$$. For each $$$i \in \{1,2,\cdots,n-1\}$$$, the $$$(i+1)^{\rm th}$$$ stone pillar is next to the $$$i^{\rm th}$$$ stone pillar from west to east. As time went on, some stone pillars were badly destroyed.

Each stone pillar can be regarded as a series of continuous cubic stones, and we label the cubic stones $$$1,2,3,\cdots,10^9$$$ from south to north. Every two east-west adjacent cubic stones have the same label. The $$$i^{\rm th}$$$ stone pillar remains cubic stones $$$l_i,l_i+1,\cdots,r_i$$$.

Here is an example: $$$n = 4, \{l_i\} = \{4,2,3,3\}, \{r_i\} = \{5,5,6,4\}$$$,

Whenever a year goes by, the outer cubic stone will be destroyed by acid rain. In the above example, those blue squares will disappear one year later. Alex wants to know when the all of cubic stones of the $$$i^{\rm th}$$$ stone pillar will disappear for each $$$i = 1,2,\cdots, n$$$. Assume that the $$$i^{\rm th}$$$ stone pillar will disappear $$$f_i$$$ years later. You need to output the answer: $$$$$$ \mathrm{answer} = \sum_{i=1}^{n} f_i \cdot 3^{i-1} \bmod 998244353 $$$$$$ Since the number of stone pillars can be very large, we generate the test data in a special way. We will provide five parameters $$$L,X,Y,A,B$$$, and please refer to the code (written in C++) below:

typedef unsigned long long u64;

u64 xorshift128p(u64 &A, u64 &B) {
	u64 T = A, S = B;
	A = S;
	T ^= T << 23;
	T ^= T >> 17;
	T ^= S ^ (S >> 26);
	B = T;
	return T + S;
}
	
void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) {
	for (int i = 1; i <= n; i ++) {
		l[i] = xorshift128p(A, B) % L + X;
		r[i] = xorshift128p(A, B) % L + Y;
		if (l[i] > r[i]) swap(l[i], r[i]);
	}
}