给定一棵有根有向树，所有边均从根节点出发指向叶子节点。每条边的长度均为 2 的幂。树的根节点编号为 1。

我们定义两个相互依赖的概念：从顶点 $v$ 出发的“旅行”（trip）和到达顶点 $v$ 的“旅程”（journey）。

到达顶点 $v$ 的“旅程”总是从其父节点 $p$ 开始（这意味着到达根节点的旅程可能永远不会发生），包含以下三个步骤：

1. 遍历 $p$ 到 $v$ 的边。
2. 进行一次从 $v$ 出发的“旅行”。
3. 从顶点 $v$ 瞬间移动回顶点 $p$，不经过任何边。

从顶点 $v$ 出发的“旅行”包含以下过程：

1. 对 $v$ 的所有子节点（如果有）分别进行一次“旅程”。
2. 如果 $v$ 至少有一个子节点，则再对 $v$ 的某个子节点额外进行一次“旅程”。

注意，任何“旅行”或“旅程”的起点和终点总是同一个顶点。

“旅行”的长度是指在旅行过程中所有经过边的总长度（包含重复经过的边）。

求从根节点出发的“旅行”的最大长度。请将结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示树的顶点数。

接下来的 $n - 1$ 行描述了这棵树。第 $i$ 行包含两个整数 $p_i$ 和 $c_i$ ($1 \le p_i \le i, 0 \le c_i \le 10^{18}$)，描述了一条连接顶点 $p_i$ 和 $i + 1$ 的边，其长度为 $2^{c_i}$。

输出格式

输出一个整数，表示从根节点出发的“旅行”的最大长度对 $998\,244\,353$ 取模的结果。

样例

输入 1

7
1 1
2 1
1 4
2 2
1 2
5 0

输出 1

52

输入 2

3
1 28
1 1000000000000000000

输出 2

752834992