Farmer Nhoj đã nhốt Bessie trên một cây có gốc gồm \(N\) (\(2\le N\le 2\cdot 10^5\)) đỉnh, trong đó đỉnh \(1\) là gốc. Trong sợ hãi và cô độc, mỗi giây Bessie thực hiện bước di chuyển sau:

• Nếu đỉnh hiện tại của Bessie không có con, cô sẽ di chuyển đến một tổ tiên được chọn ngẫu nhiên của đỉnh hiện tại (không tính chính đỉnh đó).
• Nếu không, Bessie sẽ di chuyển đến một đỉnh con được chọn ngẫu nhiên của đỉnh hiện tại.

Ban đầu, Bessie ở đỉnh \(x\), và lối thoát duy nhất của cô nằm tại đỉnh \(y\) (\(1\le x,y\le N\)). Với \(Q\) (\(1\le Q\le 2\cdot 10^5\)) truy vấn độc lập gồm \(x\) và \(y\), hãy tính kỳ vọng số giây để Bessie đến đỉnh \(y\) lần đầu tiên nếu cô bắt đầu tại đỉnh \(x\), theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa \(N-1\) số nguyên \(p_2,\ldots,p_N\) mô tả cây (\(1\le p_i<i\)). Với mỗi \(2\le i\le N\), có một cạnh nối đỉnh \(i\) và đỉnh \(p_i\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), biểu diễn các đỉnh của truy vấn đó.

Dữ liệu ra

Với mỗi truy vấn, in ra kỳ vọng số giây để Bessie đến đỉnh \(y\) lần đầu tiên khi bắt đầu tại đỉnh \(x\), theo modulo \(10^9+7\).

Ví dụ

5 5
1 2 2 1
1 1
2 1
3 1
4 1
5 1

0
4
3
3
1

5 5
1 2 2 1
1 1
1 2
1 3
1 4
1 5

0
3
500000011
500000011
6

13 10
1 2 2 4 3 1 5 6 4 7 8 10
1 12
10 6
5 12
1 13
13 10
6 4
7 12
3 1
12 8
2 1

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

Phân nhóm

• Các test 4–8: Với mọi truy vấn, \(y=1\).
• Các test 9–13: Với mọi truy vấn, \(x=1\).
• Các test 14–18: Với mỗi \(2\le i\le N\), \(p_i\) được chọn ngẫu nhiên đều trong đoạn \([1,i-1]\).
• Các test 19–23: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Platinum Division — bài gốc tiếng Anh “Dynamic Instability”. Tác giả: Avnith Vijayram. https://usaco.org/index.php?page=viewproblem2&cpid=1574