题目描述

克露丝卡尔酱听说大家都是经验丰富的信息竞赛老手，轻松暴力踩标算。为了让大家都体验一下暴力踩标算的乐趣，所以克露丝卡尔酱准备了一道简单的送温暖题：

给定一个 $n$ 个点的树，点 $i$ 的点权为 $a_i$，你需要从中选出一个连通块，使得它们的点权和模 $M$ 的余数最大。克露丝卡尔酱想知道这个点权和模 $M$ 的余数最大是多少。

输入格式

第一行两个正整数 $n$ $(1\leqslant n \leqslant 33)$ 和 $M$ $(2\leqslant M \leqslant 10^9)$。

为了方便输入，我们输入时假定以 $1$ 为根，但是请注意这是一棵无根树。

第二行有 $n - 1$ 个整数，第 $i$ 个整数表示第 $i + 1$ 个点的父节点 $f_{i + 1}$ $(1\leqslant f_{i+1} < i+1)$。

第三行有 $n$ 个整数，$a_1, \cdots, a_n$ $(0 \leqslant a_i < M)$ 表示每个点的点权。

输出格式

共一个整数表示答案。

6 10
1 2 3 4 5
7 7 7 7 7 7

8

提示

这棵树是一条链 1 - 2 - 3 - 4 - 5 - 6。最优解为选择一条长度为 4 的链（例如 1 - 2 - 3 - 4 或者 2 - 3 - 4 - 5 等等），此时答案为 $4 \times 7 \equiv 8\pmod {10}$。