Chef And Fibonacci Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef likes to play with trees a lot. This time, he has a rooted tree T consisting of N nodes labelled uniquely with the integers from {1, … N}. The node labelled 1 is the root of the tree. Each node in the given tree T stores a nonnegative integer, initially all of which are zeros. Chef wants to perform 2 types of operations over the tree accurately and efficiently.
 U X K: Update the subtree rooted at node X such that the the root X will have F_{K} (the K^{th} Fibonacci number) added to it, all its children will have F_{k+1} (the (K+1)^{th} Fibonacci number) added to them, and so on. More formally, any node in the subtree rooted at X will have (K+D)^{th} fibonacci number added to them, where D is the distance of the node from X.
 Q X: Report the value stored at the node X.
Since the answer to each query can be very large, output it modulo 10^{9} + 7.
NOTE:
F_{K} denotes the K^{th} Fibonacci number, and the series is generated as follows:
 F_{K} = 1, if K ≤ 2 .
 F_{K} = F_{K1} + F_{K2}, otherwise.
To know more about Fibonacci numbers, click here.
Input:
First line of input contains two integer N and M denoting the number of nodes in the tree T, and the number of queries to be processed, respectively. Next N1 lines of input contain an integer each, where the integer in the i^{th} line denotes the parent of the (i+1)^{th} node. Each of the next M lines contains one of the 2 types of queries mentioned above.
Output:
For each operation of type Q, output the required answer modulo 10^{9} + 7.
Constraints:
 1 ≤ N, M, K ≤ 10^{5}
 1 ≤ U, V, X ≤ N
Example
Input
5 10 1 1 3 3 Q 3 U 1 2 Q 2 Q 3 Q 4 Q 5 U 3 1 Q 3 Q 4 Q 5 Output0 2 2 3 3 3 4 4Explanation
Author:  ma5termind 
Tester:  antoniuk1 
Editorial  http://discuss.codechef.com/problems/CFTREE 
Tags  cook66, datastructure, graph, ma5termind, medium, sqrtdecomp 
Date Added:  2122015 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions