Light Bulb Queries 2

Pillow has connected $N$ light bulbs in a row for Christmas. The bulbs are numbered from $1$ to $N$ from left to right. When the switch is turned on, bulb $i$ lights up with probability $P_i$. These events are mutually independent.

A block is a maximal consecutive interval of lit bulbs. Its length is the number of bulbs it contains.

Process the following $Q$ queries.

• $l\ r$: Considering only bulbs $l$ through $r$, find the expected sum of the squared lengths of all blocks of lit bulbs.

Bulbs outside the query interval are ignored. In particular, a block that extends outside the interval is cut at the interval's endpoints. If no bulb in the interval is lit, the sum of squared lengths is $0$.

Print each expectation modulo $998\,244\,353$ as described in the Output section.

The input is given in the following format.

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

For each test case, print the answers to its queries in input order, one per line. Do not print blank lines between test cases.

Write an expectation as a reduced fraction $\cfrac{a}{b}$. Let $M=998\,244\,353$. The denominator $b$ is not divisible by . For an integer satisfying , print the remainder of modulo . The printed integer must be between and , inclusive.

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