시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
The company Lucky Stars, where Bill works as the President, has $N$ employees, enumerated from 1 to $N$ in order of their position in the company.
Bill have the employee ID 1. Any other employee, except for the President Bill, have exactly one direct supervisor. The direct supervisor of the employee $i$ is denoted as $P_i<i$. For each of $N$ employees the annual income of this employee is an integer $A_j$ between $0$ and $10^9+6$.
Once Bill decided to consult with a fortune-teller who is absolutely right about the future of the company and heard something like "someday, $K$ mistakes will be done, and Lucky Stars management became difficult."
Each mistake is caused by exactly 1 employee, and for $i=1,2, \ldots, N$ the probability that the mistake is caused by employee $i$ is $1/N$ (note that the mistakes are independent, i.e. it can happen that some employee caused several mistakes).
Bill held a meeting and decided to enforce the personal responsibility in case if fortune-teller was right. Bill wants to find one employee and let him pay a fine if $K$ types of mistakes were made by the Lucky Stars personnel at one day. The employee who pays the fine is determined according to the following rules.
Bill calculated the expected value $E_i$ of the fine paid by the employee number $i$ if the fortune-telling was correct, and represented it modulo $10^9+7$.
In other words, for $i=1,2,…,N$, the expected fine to be paid by employee number $i$ is expressed as $Y_i/X_i$ (where $X_i$ and $Y_i$ are relatively prime integers and $X_i$ is not divisible by $10^9+7$), then answer is $Y_i$ div $X_i$ modulo $10^9+7$.
Now, you have the information about structure of the company (i.e. the value of $P_i$ for each employee) and the values of $E_i$ of the expected value of fines, calculated by Bill.
Please determine whether all of the obtained information is likely to be correct, and if so, find the minimum possible Bill's annual salary.
The first line of the input contains two integers $N$ ($1 \le N \le 2 \cdot 10^5$) and $K$ ($1 \le K \le 10^9$, $K$ is odd).
The second line of the input contains $N-1$ integers $P_2$, $\ldots$, $P_N$ ($1 \le P_i \le i-1$) --- the number $P_i$ of the direct supervisor of the employee $i$. If $N=1$, the second line is empty.
The third line of the input contains $N$ integers $E_i$ --- the calculated expected fines for $i$-th employee ($0 \le E_i \le 10^9+6$).
If the calculation is definitely wrong, print $-1$. Otherwise print one integer --- the minimum possible annual salary of Bill.
2 1 1 2 1
4
1 1 2
2