U575163 「菈菈」的斐波那契树

「菈菈」在「戴比路克星球」上种了一棵奇怪的树。 这棵树上长出了一些问题。 可是「菈菈」不会计算，只好向「梨斗」求助了。 「梨斗」见多识广，一眼就看出来了这是[水题](https://www.luogu.com.cn/problem/P5138)于是把它加强了并重新丢给「菈菈」。 「菈菈」：qwq

定义 $fibonacci$ 数列第 $i$ 项为 $fib(i)$，对于任意 $3\le i$，有 $fib(i)=fib(i−1)+fib(i−2)$，令 $fib(1)=fib(2)=1$。 再给出一个有根树 $T$，$T$ 一共有 $n$ 个节点，从 $1\sim n$ 编号，$1$ 号节点为根，每个点有一个权值，初始的时候都是 $0$，现在有 $2$ 种操作： - $0$ $x$ $k$ 更新操作，对于在 $x$ 的子树中的每一个节点(包括 $x$），如果它到 $x$ 的距离(即这个点到 $x$ 的唯一简单路径上经过的边数)为 $d$，那么将它的权值加上 $fib(k+d)$。 - $1$ $x$ $y$ 询问操作，询问 $x$ 到 $y$ 的简单路径上的所有点的权值之和(包括 $x$ 和 $y$)，将所求的权值和对 $1000000007$ 之后输出。

一行 $2$ 个整数 $n,m$。 一行 $n-1$ 个整数表示 $2\sim n$ 的父亲节点。 $m$ 行操作，按照题目描述。

对于每一个查询操作输出结果。

共 $10$ 个测试点 对于 $100\%$ 的数据，$1\le n,m\le 1.5\times 10^6$，$1\le k\le 10^{15}$ - 对于 $1$ 号测试点，满足 $1\le n,m,k\le 10^3$ - 对于 $2$ 号测试点，满足 $k=dep[x]$ - 对于 $3,4$ 号测试点，满足 $1\le n,m\le 10^3$ - 对于 $5,6$ 号测试点，满足 $1\le n,m\le 10^5$ - 对于 $7,8$ 号测试点，满足 $1\le n,m\le 3\times 10^5$ - 对于 $9,10$ 号测试点，满足 $1\le n,m\le 1.5\times 10^6$ 快读： ```cpp #define getc (cs==ct&&(ct=(cs=cb)+fread(cb,1,1