g6-07503. 向下路径·方案计数

题目描述

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。一条向下路径指：从某个结点出发，每次走到它的一个孩子，可以走 $0$ 步或若干步，路径上至少包含一个结点。

求不同向下路径的条数，答案对 $1 0^{9} + 7$ 取模。（两条路径不同，当且仅当它们的起点不同，或某个位置走向了不同的孩子。）

第一行一个整数 $n$ 。

第二行 $n - 1$ 个整数 $f_{2}, f_{3}, \dots, f_{n}$ ，其中 $f_{i}$ 表示结点 $i$ 的父亲，保证 $f_{i} < i$ （ $n = 1$ 时该行为空）。

一行一个整数，表示路径条数对 $1 0^{9} + 7$ 取模的结果。

输入：

3
1 2

输出：

链 $1 - 2 - 3$ ： $1$ 、 $2$ 、 $3$ 三条单点路径，加上 $1 - 2$ 、 $2 - 3$ 、 $1 - 2 - 3$ 三条，共 $6$ 条。

输入：

4
1 1 1

输出：

星形： $4$ 条单点路径，加上 $1 - 2$ 、 $1 - 3$ 、 $1 - 4$ 三条，共 $7$ 条。