题目描述

你在最近加冕成为了Z国的国王。Z国共有 $n$ 座城市。有 $n-1$ 条无向边将这些城市联通。换句话说，Z国的城市形成了一棵树。

最近你听到了风声，Y国想要进攻Z国的一条路径，以切断Z国城市之间的联系。为此，你决定派兵把守其中的一些城市，以阻挡Y国的攻击。

具体地，我们会收到 $q$ 次询问，每个询问给出树上的两个结点 $u,v$，代表国王听到了Y国要切断从 $u$ 到 $v$ 的路径的风声。你希望派出一些士兵驻扎在一些城市上，使得这些士兵满足如下两个条件：

1.士兵驻扎的城市需要是一个连通块，以防止被Y国逐个击破；

2.至少有一座$u-v$路径上的城市被士兵驻扎。请你针对每次询问回答这样驻扎士兵的方案数。方案数对 $998244353$ 取模

输入格式

第一行两个正整数 $n,q$ 表示城市数量和询问次数。

接下来一行 $n-1$ 个整数 $p_2,...,p_n$，其中 $p_i$ 表示 $i$ 号结点和 $p_i$ 结点存在连边。

接下来 $q$ 行每行两个整数 $u,v$，表示Y国可能切断 $u-v$ 的路径。

输出格式

输出 $q$ 行，每行一个正整数表示题目所求的方案数。

样例

3 2
1 1
2 3
1 2

6
5

解释 #1

当Y国进攻 $2-3$ 的路径时。我们有 $6$ 种驻扎方案，分别是：$\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{1,2,3\}$

5 3
1 1 2 2
4 5
2 4
2 3

14
13
15

样例 #2

当Y国进攻 $4-5$ 路径时，Z国派士兵驻扎 $\{1,2,4\}$ 是其中一种可行方案。

数据范围

对于$100\%$的数据，$1\le n,q\le 10^5,1\le u_i,v_i\le n,1\le p_i<i$，输入保证构成一棵树