题目背景

“呜哇——！怎么会有这么奇怪的数组啊！”

克露丝卡尔酱盯着黑板上写满的 $+1$ 和 $-1$，整个人都不好了。

“前辈前辈！”后辈拽着她的袖子，“如果给你一个区间，里面的数字可以随便重新排列，那有多少种排法能让所有连续子段的乘积加起来正好等于 $k$ 呢？”

面对那双闪闪发亮的眼睛，克露丝卡尔酱只能硬着头皮接下了这个挑战。

唉，今天的社团活动，似乎又不太平静呢……

题目描述

给定长度为 $n$ 的数组 $a$，每个元素都是 $\pm 1$ 之一。

给定常数 $k$ 以及 $q$ 次询问，每次询问指定 $l,r$，计算：假如你可以任意排列 $[l,r]$ 下标范围内的元素，有多少种排列方式，使得新数组（长度仍为 $n$）的所有非空子段乘积之和（即 $\sum_{i\le j}\prod_{t\in[i,j]}a_t$）为 $k$。结果对 $998244353$ 取模。

注意：即使两个不同的排列得到的数组完全相同，也将它们视为不同的排列。

输入格式

本题有多组测试数据。

首先输入一行，包含一个整数 $T$（$1\le T\le 10^5$），表示测试数据组数。

每组数据首先输入一行，包含三个整数，分别表示数组长度 $n$ ($1\le n\le 10^5$)、常数 $k$ ($\lvert k\rvert\le\frac{n(n+1)}{2}$)、询问总数 $q$ ($1\le q\le 10^5$)。

接下来输入一行，包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$，满足 $\lvert a_i\rvert=1$。

接下来输入 $q$ 行，每行包含两个整数，其中第 $i$ 行的两个整数分别表示第 $i$ 次查询的 $l_i,r_i$ ($1\le l_i\le r_i\le n$)。

保证 $\sum n,\sum q\le 10^5$。

输出格式

输出 $\sum q$ 行，每行一个整数，表示询问结果。

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

提示

对于第一组样例的第一次询问，必须将前四个元素排列为 $(1,-1,1,-1)$ 或 $(-1,1,-1,1)$，共有 $8$ 种排列方式满足要求。