P17654 [IO 2025 #1] 浆果收藏

大黄蜂决定完成采集苔藓浆果的任务。为了不让自己感到无聊，她决定给每颗浆果评定美丽值。浆果的美丽值取决于它的种类，种类用一个非负整数表示。 大黄蜂有一个包含 $n$ 个数 $a_i$ 的数组。数组下标从 $0$ 开始。当她找到一颗种类为 $x$ 的浆果时，其美丽值按以下方式计算： 1. 将 $x$ 的二进制表示写成 $n$ 位：$\overline{b_{n-1}b_{n-2}\ldots b_0}$，其中 $b_0$ 是最低位。 2. 将所有满足 $b_i=1$ 的 $a_i$ 相乘。若没有满足条件的下标，则乘积为 $1$。 3. 将所得值记为 $f(x)=\prod_{i=0}^{n-1}a_i^{b_i}$，称为这颗浆果的**美丽值**。 一共有 $q$ 个可以找到苔藓浆果的地点。在第 $i$ 个地点，种类从 $l_i$ 到 $r_i$（包含端点）的每种浆果各有一颗。 请帮助大黄蜂求出每个地点中浆果美丽值的总和，也就是对每个 $i$ 计算 $\sum_{j=l_i}^{r_i}f(j)$。答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

第一行包含一个整数 $n$，表示用于评定浆果美丽值的数组 $a$ 的长度，$1\le n\le60$。 第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$，表示计算美丽值时使用的乘数，$1\le a_i

输出 $q$ 行，每行一个整数。第 $i$ 行应为第 $i$ 个地点所有浆果美丽值的总和对 $998\,244\,353$ 取模后的结果。