전구의 쿼리 2

베개는 크리스마스를 위해 $N$개의 전구를 한 줄로 연결했다. 전구에는 왼쪽부터 차례로 $1$부터 $N$까지의 번호가 붙어 있다. 스위치를 켜면 $i$번 전구가 켜질 확률은 $P_i$이며, 각 전구가 켜지는 사건은 서로 독립이다.

켜져 있는 전구들이 연속해서 놓인 최대 구간을 하나의 덩어리라고 하자. 덩어리의 길이는 그 안에 있는 전구의 개수이다.

다음 쿼리 $Q$개를 처리하여라.

• $l\ r$: $l$번부터 $r$번까지의 전구만을 보았을 때, 켜져 있는 덩어리들의 길이 제곱 합의 기댓값을 구한다.

쿼리 구간 밖의 전구는 고려하지 않는다. 따라서 구간 밖에서 이어지는 덩어리도 구간의 양끝에서 끊어서 센다. 구간 안에 켜진 전구가 없다면 길이 제곱 합은 $0$이다.

각 기댓값을 $998\,244\,353$으로 나눈 나머지 형태로 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다, 쿼리의 답을 입력된 순서대로 한 줄에 하나씩 출력한다. 테스트 케이스 사이에 빈 줄은 출력하지 않는다.

기댓값을 기약분수 $\cfrac{a}{b}$로 나타내자. $M=998\,244\,353$이라 할 때, $b$는 의 배수가 아니다. 을 만족하는 정수 에 대해, 을 으로 나눈 나머지를 출력한다. 출력하는 정수는 이상 이하여야 한다.

• $1 \leq T \leq 100\,000$.
• $1 \leq N \leq 100\,000$.
• $1\le Q\le$.