Background

“Waa—! How can there be such a weird array!”

Kruskal-chan stared at the blackboard full of $+1$ and $-1$, and felt completely overwhelmed.

“Senior, senior!” the junior tugged at her sleeve. “If I give you an interval, and the numbers inside can be rearranged freely, then how many rearrangements make the sum of products of all contiguous subsegments equal to $k$ exactly?”

Facing those sparkling eyes, Kruskal-chan could only bite the bullet and accept the challenge.

Sigh, today’s club activity seems not so peaceful again……

Problem Description

You are given an array $a$ of length $n$, where each element is either $\pm 1$.

You are also given a constant $k$ and $q$ queries. Each query specifies $l, r$. You need to compute: assuming you may arbitrarily permute the elements whose indices are in $[l, r]$, how many permutations make the sum of products of all non-empty subsegments of the new array (still of length $n$), i.e. $\sum_{i\le j}\prod_{t\in[i,j]}a_t$, equal to $k$. Output the result modulo $998244353$.

Note: even if two different permutations produce exactly the same resulting array, they are still considered different permutations.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ ($1\le T\le 10^5$), the number of test cases.

For each test case, the first line contains three integers: the array length $n$ ($1\le n\le 10^5$), the constant $k$ ($\lvert k\rvert\le\frac{n(n+1)}{2}$), and the number of queries $q$ ($1\le q\le 10^5$).

The next line contains $n$ integers. The $i$-th integer is $a_i$, satisfying $\lvert a_i\rvert=1$.

Then follow $q$ lines. Each line contains two integers. The two integers on the $i$-th line are $l_i, r_i$ for the $i$-th query ($1\le l_i\le r_i\le n$).

It is guaranteed that $\sum n, \sum q\le 10^5$.

Output Format

Output $\sum q$ lines, each containing one integer, the answer to the corresponding query.

2
5 -3 3
1 -1 -1 1 -1
1 4
2 5
3 3
3 6 1
1 -1 -1
1 3

8
12
0
0

Hint

For the first query of the first sample, the first four elements must be rearranged into $(1,-1,1,-1)$ or $(-1,1,-1,1)$. There are $8$ permutations in total that satisfy the requirement.

Translated by ChatGPT 5