New update is available. Click here to update.

Topics

Icarus is given a binary search tree consisting of ‘N’ nodes. He have to find the different number of permutations of the tree nodes modulo 10^9+7. Where a permutation of a tree is an arrangement of nodes in the original tree such that the structure remains same but there exists at least one position in the permutation whose value is different from original tree.

Output the number of distinct permutations modulo 10^9+7.

Detailed explanation

```
1 <= T <= 10
1 <= N <= 10^5
It is guaranteed that the given input is a binary search tree.
Time Limit: 1 sec
```

```
2
4
1 -1 2 3 4 -1 -1 -1 -1
3
1 2 -1 -1 3 -1 -1
```

```
1
0
```

```
For test case 1 we have,
The input tree:
```

```
The different permutations are :
[1, -1, 2, 4, 3, -1, -1, -1, -1]
Hence the answer is 1 % (10^9+7) = 1.
For test case 2 we have,
The input tree :
```

```
No other permutations exists for this tree.
Hence the answer is 0 % (10^9+7) = 0.
So, we output 1(true).
```

```
2
3
1 2 -1 3 -1 -1 -1
3
1 2 -1 3 -1 -1 -1
```

```
0
0
```