AT_utpc2021_k Divide Polynomials by #Subset Sums

[problemUrl]: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_k $ P $ を素数 $ 998244353 $ とします。 多項式 $ f(x) $ に対して次の一連の操作を定めます。 1. $ f(x) $ と $ (1\ +\ x^k)g(x) $ の各次数の係数を $ P $ で割った余りが等しくなるような正の整数 $ k $ と有限次の多項式 $ g(x)\neq\ 0 $ を選択する。 2. その後、$ f(x) $ を上記の $ g(x) $ に置き換えて $ 2^k $ のスコアを得る。 ある多項式に対して、この操作を好きな回数行って得られるスコアの総和の最大値を多項式の **美しさ** と定めます。 数列 $ A=(A_0,\ldots,A_{N\ -\ 1}) $ と $ Q $ 個のクエリが与えられます。 $ i $ 番目のクエリでは整数 $ l_i,r_i $ が与えられるので、多項式 $ \displaystyle\ f(x)\ =\ \sum_{j=0}^{r_i\ -\ l_i}A_{j\ +\ l_i}x^{j} $ の **美しさ** を $ P $ で割った余りを求めてください。 ただし、操作における $ g(x) $ の係数は $ 998244353 $ 未満の非負整数に限ります。(13:10 追記)

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_{0} $ $ \ldots $ $ A_{N\ -\ 1} $ $ l_1 $ $ r_1 $ $ \vdots $ $ l_{Q} $ $ r_{Q} $

$ Q $ 行出力せよ。 各 $ i $ $ (1\leq\ i\ \leq\ Q) $ について、$ i $ 行目には $ i $ 番目のクエリの答えを出力せよ。

### 制約 - 入力は全て整数 - $ 2\leq\ N\ \leq\ 2000 $ - $ 1\leq\ Q\ \leq\ 2000 $ - $ 0\leq\ A_i $ - $ 0\leq\ l_i\