The burglar has found himself a new place for his Thievery again. They can only enter this area through a special house called "root". Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place forms a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Input:
A line containing an integer T, the no. of Test Cases.
First Line of each test case contain an integer N, the no. of Nodes in the tree.
Next line containing N integers, the values on the nodes.where '-1' indicates a NULL node.
Output:
Output for each Test Case the maximum amount of money the thief can rob tonight modulo 10^9+7 in one Line.
Constraints:
1<= T <= 100
1<= N <= 5000
1<= A[i] <=10^9
In 1st test case:
3*
/ \
2 3
\ \
3* 1*
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
In 2nd test case:
3
/ \
4* 5*
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.