Compatible Sequences

All submissions for this problem are available.
Appu recently went trekking with her friends. During the trek, she saw a strange kind of tree in the middle of the forest. It can be described as follows 
A Binary Search Tree, is a nodebased binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
To insert a given node in Binary Search Tree, we first compare it with root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree. Once a leaf node is found, the new node is added as a child of the leaf node.
Intrigued by the tree, Appu decided to solve a problem concerning it.
The Binary Search Tree she saw is of size n rooted at R, which contains all numbers in the range [1,n] (Both inclusive).
Help Appu find the different number of permutations of first n natural numbers which are compatible with given Binary Search Tree.
A permutation is said to be compatible with given BST if it constructs the same BST when nodes are inserted to an empty BST according to the permutation ordering.
Input
The first line of the input contains an integer n denoting the size of the array.The second line of the input contains an integer R denoting the root of the Binary Search Tree.Next n1 lines contain 2 space saperated integers u, v denoting the edge (u>v) of the tree.
Output
Output a single integer corresponding to the number of different ways of constructing the given Binary Search Tree (modulo 10^{9}+7).
Constraints
 1 ≤ n ≤ 100000
 1 ≤ R ≤ n
 1 ≤ u ≤ n
 1 ≤ v ≤ n
Example
Input: 3 2 2 1 2 3 Output: 2
Explanation
If the elements are added to an empty BST in the order according to the permutations [2,1,3] and [2,3,1],they construct the given Binary Search Tree.Author:  vinod10 
Tags  vinod10 
Date Added:  16102017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions