A new game is introduced. This game involves a perfect square number of players. Now, say n ∗ n players participate in the game. These players have a unique number each which ranges from 1 to n ∗ n both inclusive. The number is printed in the front and back of their T-Shirts. These n ∗ n players arrange themselves such that the boundary formed by the whole set of players looks like an oval. The game involves 2 balls. One ball is given to player in the first line and one ball to player in the last line. Both the balls are passed towards the other corner as follows :
BALL 2: 2/3 Set of players probably carrying the ball 4 1,3 1,2 2 1 Each player in the carrying set 4 1 3 1 2 2 1 Next Line 1,3 2,6,7 2,6,7 4(Reversed) 5,8 1,3 4 Corresponding RESULT set of players that the ball can be passed to. 1,3 PASSED NILL REVERSE 2 PASSED NILL HALT NILL REVERSE 1 PASSED NILL HALT Given the number n, the arrangement of n∗n players and the player number p , return the probability that the player numbered p holds atleast one ball at atleast one point of time during the course of the game. Input The first line in the input file contains no. of test cases (< 30) Each test case is separated by an empty line. Each test case satisfies the following conditions: Value of n(first line) ranges from 2 to 20 both inclusive. Arrangement is represented by 2 ∗ n − 1 lines; Lines 1 to n have space separated list of i integers where i is the line number; Lines n + 1 to 2 ∗ n − i integers in space separated manner. Each integer in arrangement lies between 1 and n ∗ n inclusive. Each integer occurs only once in arrangement (Unique). The player number (line following the arrangement) lies between 1 and n ∗ n both inclusive. Output The output should contain one line for every test case. Each line in the output must be an integer, the floor value of ((The required probability (that player p holds at least one ball at least one point of time) ∗10∧9) with no leading zeros. If probability is p, output floor (p ∗ 10∧9). For case 1: probability is 0.166666666666666. Note: The picture on the right illustrates the fisrt sample case. Sample Input 4 3 9 58 267 13 4 6 3 9 58
3/3 267 13 4 3 2 1 23 4 2 4 15 14 13 16 10 12 11 7 2 4 195 68 3 7 Sample Output 166666666 583333333 500000000 291666666