Transfiguring Trees

All submissions for this problem are available.
Hermione has come home for the holidays after a grueling first year at Hogwarts. She then picks up a Muggle book on "Graph Theory" and starts reading about rooted Kary trees: Trees that are rooted and in which each node has at most K children. Since Transfiguration is her favorite subject at Hogwarts, she excitedly starts inventing a spell to Transfigure some such trees into others.
After a while, she has succeeded in her spell. However, she notices something strange about the transfigured tree. Suppose she started with the tree T, and transfigured it into tree T'. Then, she found that the preorder traversal of T was the same as the preorder traversal of T', and that the postorder traversal of T was also the same as the postorder traversal of T'.
She then realizes that her spell is capable of transfiguring tree T into another tree T' only if the preorder and postorder traversals of both are the same. She thus wonders, given a particular permutation of nodes P1 and another permutation of nodes P2, along with the value of K, how many rooted Kary trees T are there that the preorder traversal of T is P1, and the postorder traversal of T is P2.
We give the explicit pseudocode of the preorder and postorder traversals of rooted Kary trees:
class node
int label;
node children[K];
//children[i] is "null" if the i'th child is not present
void preorder(node subroot)
output subroot.label;
for(int i = 0; i < K; i++)
if(subroot.children[i] != null)
preorder(subroot.children[i]);
void postorder(node subroot)
for(int i = 0; i < K; i++)
if(subroot.children[i] != null)
postorder(subroot.children[i]);
output subroot.label;
Two rooted Kary trees T1 and T2 are considered different if there is some node n, such that the children[] array of node n is different in T1 and in T2.
Some examples of differences: K=2.1 : (1.children = [2, 3]) / \ 2 3
is different from1 : (1.children = [3, 2]) / \ 3 2
Also, K=2.1 : (1.children = [null, 2]) \ 2
is different from1 : (1.children = [2, null]) / 2
is different from2 \ 1 : (1.children = [null, null], 2.children = [null, 1])
Input
The first line contains T, the number of testcases.
Each testcase, begins with a line consisting of two integers N and K, N is the number of nodes of the tree, and K is the maximum number of children of each node.
This is followed by a line containing a permutation of 1 to N, the supposed preorder traversal.
This is followed by another line containing a permutation of 1 to N, the supposed postorder traversal.
Output
For each testcase, output the possible number of rooted Kary trees having the first permutation as its preorder traversal and the second permutation as its postorder traversal. Since the answer can be large, output the answer modulo 1000000007 (10^{9} + 7).
Constraints
 1 ≤ T ≤ 5
 2 ≤ N ≤ 10^{5}
 1 ≤ K < N
 Both lines will contain permutations of 1 to N
Example
Input: 4 2 2 1 2 2 1 4 2 1 2 3 4 2 3 4 1 3 2 2 1 3 1 3 2 4 3 1 3 2 4 2 1 3 4 Output: 2 0 1 0
Explanation
The first case has two possibilities:
1 / 2
and1 \ 2
The second case gives us a tree where the root 1 has 2, 3 and 4 as its children. Since K = 2, this violates the condition that each node has atmost K children.
The fourth case is impossible for any tree to have the given preorder and postorder traversals.
Author:  pragrame 
Tester:  tuananh93 
Editorial  http://discuss.codechef.com/problems/TRANSFIG 
Tags  cook35, medium, pragrame, tree 
Date Added:  7062013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 