考虑对于一个数组 $a_{1,\dots ,n}$ 怎么求出答案，其中 $0$ 为根。考虑每一条边 $i \to f_i$ 的贡献，显然是 $siz_i(n+1-siz_i)$ 。那么我们可以枚举这个点的子树的 $siz$ 然后算这种情况的概率，而算概率则直接统计有多少种加边后的方案使得取到这个 $siz$ 然后除以总方案数 $n!$ 即可。考虑方案数量的计算，如果确定后面有 $s$ 个点在子树内（不包括 $i$ ），这些点的父亲的方案分别是 $1,2,3,\dots ,s$ ，因为第一个子树内的点的父亲必须是 $i$ ，第二个可以是第一个或者 $i$ …… 然后考虑这个子树之外（不包括 $i$ ）的点。这些点的方案数显然依次是 $1,2,\dots,n-s-1$ 。最后考虑 $i$ 的父亲的方案数，它可以连向 $0 \sim i-1$ ，是 $i$ ，于是式子就是：

$$\frac{1}{n!}\sum_{i=1}^n A_i \sum_{s=0}^{n-i} \binom {n-i} s s!(n-s-1)!i[(s+1)(n+1)-(s+1)^2]$$

为了方便，暂时不写最前面的 $\frac 1{n!}$ 了。

然后是推式子：

$$\begin{aligned} &\sum_{i=1}^n A_i \sum_{s=0}^{n-i} \binom {n - i}s(n-s-1)!s!i[(s+1)(n+1)-(s+1)^2]\\ =&\sum_{i=1}^n A_i i(n-i)!\sum_{s=0}^{n-i} \frac {(n-s-1)!}{s!(n-i-s)!}s![(s+1)(n+1)-(s+1)^2]\\ =&\sum_{i=1}^n A_i i(n-i)!(i-1)!\sum_{s=0}^{n-i} \frac {(n-s-1)!}{(n-i-s)!(i-1)!}[(s+1)(n+1)-(s+1)^2]\\ =&\sum_{i=1}^n A_i (n-i)!i!\sum_{s=0}^{n-i} \binom{n-s-1}{i-1} [(s+1)(n+1)-(s+1)^2]\\ \end{aligned}$$

然后运用一个组合恒等式

$$\sum_{i=0}^n \binom{i}{a}\binom{n-i}{b} = \binom{n+1}{a+b+1}$$

组合意义就是枚举分界点。

于是可以把 $s+1$ 变成 $\binom {s+1} 1$ 来解决掉，但是发现 $(s+1)^2$ 无法运用组合恒等式了。于是我们考虑代入 $\binom{s+1}{2}$ ，最后再通过 $x^2 = 2\binom x2 + x$ 推回即可。

$$\begin{aligned} =&\sum_{i=1}^n A_i (n-i)!i!\sum_{s=0}^{n-i} \binom{n-s-1}{i-1} \left[(s+1)n-2\binom{s+1}{2}\right]\\ =&\sum_{i=1}^n A_i (n-i)!i!\left[\binom{n+1}{i+1}n - 2\binom{n+1}{i+2}\right]\\ =&\sum_{i=1}^n A_i (n-i)!i!\left[\frac{(n+1)!}{(i+1)!(n-i)!}n - 2\frac{(n+1)!}{(i+2)!(n-i-1)!}\right]\\ =&(n+1)!\sum_{i=1}^n A_i \left[\frac{n}{(i+1)} - \frac{2(n-i)}{(i+2)(i+1)}\right]\\ =&(n+1)!\sum_{i=1}^n A_i \frac{(n+2)i}{(i+2)(i+1)}\\ \end{aligned}$$

最开始我们省略了一个 $\frac 1 {n!}$ 我们给它代回来

$$=(n+1)(n+2)\sum_{i=1}^n A_i \frac{i}{(i+2)(i+1)}$$

然后就获得了一个看起来非常优秀的 $O(n)$ 式子，甚至没必要算阶乘！

但是区间查询怎么做？我们可以把它写成一个差卷积的形式

$$\sum_{i-j=l} A_i \frac{j+1}{(j+2)(j+3)}$$

于是发现求的就是区间之内所有的位置提出来然后做差卷积之后在 $l$ 这个位置的和。于是我们可以分块，对每个块维护出 $l=1\sim n$ 的上述式子的值，这个可以通过 NTT 在 $O(\frac{n^2}{B}\log n)$ 解决。

而查询直接 $O(\frac{n}{B}+B)$ 枚举中间的块以及两边散的，分别算贡献即可。

复杂度 $O(n\sqrt{n\log n})$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353
int n , q;
int A[MAXN] , bl[MAXN];
const int blo = 1200;

int iv[MAXN];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int Wn[2][1000006];
void getwn( int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 ) {
		int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
		Wn[0][mid] = Wn[1][mid] = 1;
		for( int i = 1 ; i < mid ; ++ i )
			Wn[0][mid + i] = Wn[0][mid + i - 1] * 1ll * w0 % P,
			Wn[1][mid + i] = Wn[1][mid + i - 1] * 1ll * w1 % P;
	}
}
int rev[MAXN];
void getr( int len ) {
	int l = __builtin_ctz( len ) - 1;
	for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << l );
}
void NTT( int A[] , int len , int typ ) {
	for( int i = 0 ; i < len ; ++ i ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int j = i ; j < i + mid ; ++ j ) {
				int t0 = A[j] , t1 = A[j + mid] * 1ll * Wn[typ][j - i + mid] % P;
				A[j] = ( t0 + t1 > P ? t0 + t1 - P : t0 + t1 ) , A[j + mid] = ( t0 < t1 ? t0 - t1 + P : t0 - t1 );
			}
	if( typ ) for( int i = 0 , iv = Pow( len , P - 2 ) ; i < len ; ++ i ) A[i] = A[i] * 1ll * iv % P;
}

int S[406][200006];
int B[200006];

int f( int a ) {
	return ( a + 1 ) * 1ll * iv[a + 2] % P * iv[a + 3] % P;
}

void solve() {
	getwn( 1 << 18 );
	cin >> n >> q;
	rep( i , 1 , n + 114 ) iv[i] = Pow( i , P - 2 );
	rep( i , 1 , n ) scanf("%d",A + i);
	rep( i , 1 , n ) bl[i] = ( i - 1 ) / blo + 1;
	rep( i , 1 , n ) B[i] = f( n - i );
	int len = 1;
	while( len <= n + n ) len <<= 1;
	getr( len );
	NTT( B , len , 0 );
	rep( k , 1 , bl[n] ) {
		rep( i , ( k - 1 ) * blo + 1 , k * blo ) S[k][i] = A[i];
		NTT( S[k] , len , 0 );
		rep( i , 0 , len - 1 ) S[k][i] = S[k][i] * 1ll * B[i] % P;
		NTT( S[k] , len , 1 );
		rep( i , 1 , n ) S[k][i] = S[k][i + n];
		S[k][0] = 0;
		rep( i , n + 1 , len - 1 ) S[k][i] = 0;
	}
	rep( i , 1 , q ) {
		int l , r;
		scanf("%d%d",&l,&r);
		int as = 0;
		if( bl[l] == bl[r] ) {
			rep( j , l , r ) 
				as = ( as + f( j - l ) * 1ll * A[j] ) % P;
		} else {
			rep( j , l , bl[l] * blo ) as = ( as + f( j - l ) * 1ll * A[j] ) % P;
			rep( j , bl[r] * blo - blo + 1 , r ) as = ( as + f( j - l ) * 1ll * A[j] ) % P;
			rep( j , bl[l] + 1 , bl[r] - 1 ) as = ( as + S[j][l] ) % P;
		}
		printf("%d\n",as * 1ll * ( r - l + 2 ) % P * ( r - l + 3 ) % P);
	}
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}