校门外的树

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定 $n$ 棵树，第 $i$ 棵树的高度为 $h_i$。一个区间 $[u,v]$ 的幸运值定义为

若 $u=v$，空积的值为 $1$。

你需要回答 $q$ 个区间询问。每次输出对应幸运值对 $998244353$ 取模的结果。

输入格式

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$。

接下来 $q$ 行，每行包含两个整数 $u,v$，表示一个询问区间。

输出格式

对每个询问输出一行一个整数，表示答案。

样例输入 1

6 2
7 9 10 6 2 5
1 4
2 5

样例输出 1

6
24

数据范围

对于所有数据，$1\le n,q,h_i\le10^5$，$1\le u\le v\le n$。