---{"category_name":"easy","problem_code":"BNYHOP","problem_name":"Bunny Hops","problemComponents":{"constraints":"- $1 \\le T \\le 10$\n- $1 \\le N \\le 10^5$\n- $1 \\le A_i \\le 10^9$ for each valid $i$\n- $A_1, A_2, \\ldots, A_N$ are pairwise distinct\n- the graph described on the input is a directed tree\n- the sum of $N$ over all test cases does not exceed $3 \\cdot 10^5$\n","constraintsState":true,"subtasks":"**Subtask #1 (20 points):** the tree is a straight line --- there is a single path starting at town $1$ and passing through all towns\n\n**Subtask #2 (20 points):**\n- $N \\le 10^3$\n- the sum of $N$ over all test cases does not exceed $10^4$\n\n**Subtask #3 (60 points):** original constraints\n","subtasksState":true,"inputFormat":"- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- The first line of each test case contains a single integer $N$.\n- The second line contains $N-1$ space-separated integers $P_1, P_2, \\ldots, P_{N-1}$.\n- The third line contains $N$ space-separated integers $A_1, A_2, \\ldots, A_N$.\n","inputFormatState":true,"outputFormat":"For each test case, print a single line containing one integer --- the number of valid sequences of visited towns modulo $10^9 + 7$.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n3\n1 1\n10 15 5\n5\n1 1 3 3\n50 10 20 40 30\n9\n1 1 2 2 2 2 7 7\n1 2 3 4 5 6 7 8 9","output":"3\n8\n28","explanation":"**Example case 1:** The possible hops for Bugs Bunny are from town $1$ to town $3$ and from town $2$ to town $1$. Therefore, the $3$ possible sequences of visited towns are $(2,1,3)$, $(2,1)$ and $(1,3)$. ","isDeleted":false}}},"video_editorial_url":"https://youtu.be/COX88JMknSs","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"hemanthram","problem_tester":"","date_added":"25-08-2021","tags":{"0":"easy","1":"eulerian","2":"fenwick","3":"hemanthram","4":"ltime99"},"problem_difficulty_level":"Easy-Medium","best_tag":"Fenwick Tree","editorial_url":"https://discuss.codechef.com/problems/BNYHOP","time":{"view_start_date":1630170002,"submit_start_date":1630170002,"visible_start_date":1630170002,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=BNYHOP","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Mandarin](https://www.codechef.com/download/translated/LTIME99/mandarin/BNYHOP.pdf), [Bengali](https://www.codechef.com/download/translated/LTIME99/bengali/BNYHOP.pdf), [Russian](https://www.codechef.com/download/translated/LTIME99/russian/BNYHOP.pdf), and [Vietnamese](https://www.codechef.com/download/translated/LTIME99/vietnamese/BNYHOP.pdf) as well.Bugs Bunny is very smart, but he keeps constantly worrying about the future and is always anxious. Therefore, he keeps hopping between towns without standing still.The place where Bugs Bunny lives has $N$ towns (numbered $1$ through $N$) with one-way roads connecting them in such a way that they form an arborescence (a tree with all paths directed from the root), rooted at town $1$. Therefore, each town except the root has exactly one incoming road; for each $i$ ($1 \le i \le N-1$), there is a road from town $P_i$ to town $i+1$. Each town has a distinct rating associated with it; for each valid $i$, the $i$-th town has rating $A_i$.From a town $i$, Bugs Bunny is allowed to hop to town $j$ (without visiting any other towns in between), if the following conditions are satisfied:- there is a path between towns $i$ and $j$, i.e. a path from town $i$ to town $j$ or from town $j$ to town $i$- town $j$ has a lower rating than town $i$, i.e. $A_j \lt A_i$This way, Bugs Bunny can visit a sequence of towns by hopping, starting anywhere and stopping whenever he chooses. Clearly, he cannot keep hopping forever, so the number of such sequences is finite.Tell Bugs Bunny the number of sequences of two or more towns which can be formed by hopping, given that he can start at any town and stop at any town. Since this number can be very large, calculate it modulo $10^9+7$.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>