Walter and Sklyer

All submissions for this problem are available.
Walter and Skyler are fighting with each other as Skyler has been hiding her smoking habits from Walter. Now to prevent more fighting, Skyler's sister has given both of them a problem to solve. Skyler is good at coding. But Walter who knows only about making meth asks for your help.
In the given problem you are given an input string S consisting of characters 'L' , 'R' , 'U' and 'D' meaning left, right, up and down respectively in the XY plane. For any given subsequence of the string, if a person starts from a certain point in the XY plane, he will end at some point in the XY plane if he follows the directions given in the subsequence.
For example, for string S="LLRUDD" if we start from (1,1) and use a subsequence of string S "LUDD" we will end up at (0,0).
Now you will be given Q queries. For each query you will be given the coordinates of starting point in XY plane and the coordinates of ending point in the XY plane ( It is guaranteed that the starting and ending points are different ) .
For each query, you need to print the number of ways of choosing a subsequence from the original string S such that if one starts at the given starting point he will end at the given ending point.
Since the answer is large, print it modulo 10^9 + 7.
Input
The first line of input contains the string S. In the next line you are given the number of queries Q. In each of the next Q lines, you are given 4 space separated integers X1,Y1, X2,Y2  the x and y coordinates of starting and ending point respectively.
Output
For each query, output the answer for that query in a new line.
Constraints
 1 ≤ Length of String S ≤ 400000
 1 ≤ Q ≤ 100000
 0 ≤ X1,Y1,X2,Y2 ≤ 10^9
Input: LRRUD 1 0 0 1 1 Output: 3
Explanation
Three subsequences of original string S "LRRU" , "RU", "RU" will result in the desired ending point if we start from the given starting point.Author:  abhi_1595 
Tags  abhi_1595 
Date Added:  1092017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions