Under construction

Still being built. Things may change

Red Black Tree

Time limit4sMemory limit512 MB

Summary
Count antichains of a rooted tree (no chosen node is an ancestor of another) with exactly k red nodes, for each k from 0 to m, modulo 1e9+7.
Level

Medium7 of 10

Topics
Dynamic programming, Tree
Solved
No attempts yet

Problem

You are given a rooted tree with nn nodes, numbered 11 to nn. The root is node 11. Exactly mm of the nodes are red, and the rest are black.

Choose a subset of nodes such that no chosen node is an ancestor of another chosen node. For example, if AA is the parent of BB and BB is the parent of CC, then at most one of AA, BB, and CC can be in the subset. You want exactly kk of the chosen nodes to be red.

For each k=0,…,mk = 0, \ldots, m, count the subsets that contain exactly kk red nodes and satisfy the condition above.

Input

The first line contains two integers nn and mm (1≤n≤2×1051 \le n \le 2 \times 10^5, 0≤m≤min⁡(103,n)0 \le m \le \min(10^3, n)). Each of the next n−1n-1 lines contains one integer pp, the parent of node 22, then node 33, and so on. Each of the next mm lines contains one integer rr, the number of a red node. No value of rr repeats.

Output

Print m+1m+1 lines. Line k+1k+1 contains the number of valid subsets with exactly kk red nodes, modulo 109+710^9 + 7.

Examples3

  1. Example 1

    Input
    4 1
    1
    1
    1
    3
    
    Expected output
    5
    4
    
  2. Example 2

    Input
    4 4
    1
    1
    1
    1
    2
    3
    4
    
    Expected output
    1
    4
    3
    1
    0
    
  3. Example 3

    Input
    14 4
    1
    2
    1
    2
    3
    4
    5
    5
    13
    8
    10
    4
    4
    8
    3
    12
    13
    
    Expected output
    100
    169
    90
    16
    0