hackercupai/hackercup huggingface dataset:
Charlotte is a very successful Olympic skier. All the sponsor deals she landed
during her career has made her very rich, so she has decided to retire from
skiing. Charlotte has just bought an entire mountain, and is planning to build
a ski resort there. The mountain has **N** interesting points, numbered 0, 1,
..., **N**-1. Point 0 is the top of the mountain. Point **i** is further down
the mountain than point **j** if **i** > **j**.

For each point **a** > 0, she has decided on a different point **b**, which
has the following property: All paths from the top of the mountain to point
**a** have to go through point **b**, and there is no point **c**, such that
**b** < **c** < **a** and all paths from the top of the mountain to point
**a** go through point **c**. A path can never go up the mountain.

You have been given the task to plan where the slopes go. You can add slopes
directly between any two different interesting points. How many ways can you
lay out the slopes for her resort, while satisfying the conditions above?

Two ways of laying out the slopes, **X** and **Y**, are different if there
exists two interesting points **a** and **b**, such that the slope between
**a** and **b** exists in **X** or **Y**, but not in the other.

You can assume that the skiers will be able to get to a lift from any point,
so you don't have to worry about getting them all the way down for every path.
You have to be able to reach all interesting points from the top.

### Input

The first line of the input consists of a single integer **T**, the number of
test cases.
Each test case starts with a line containing the integer **N**.
The next line of each test case contains **N**-1 integers, **A1**, **A2**,
..., **AN-1**, where **Ai** is the lowest interesting point that all paths to
point **i** has to pass through.

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the number of ways you can lay out the slopes given the
constraints in the input, modulo 1,000,000,007

### Constraints

1 ≤ ** T ** ≤ 20
2 ≤ **N** ≤ 5000
**Ai** < **i** for each of **A1**, **A2**, ..., **AN-1**

### Examples

The first example has to have the following slopes:

0 -> 1
0 -> 2
1 -> 3

In addition, we can choose whether or not to add the slope

1 -> 2

The total will be 2; one for adding the slope and one for not adding it.