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 X-Y plane. For any given subsequence of the string, if a person starts from a certain point in the X-Y plane, he will end at some point in the X-Y 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 X-Y plane and the coordinates of ending point in the X-Y 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.
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.
For each query, output the answer for that query in a new line.
- 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
ExplanationThree subsequences of original string S "LRRU" , "RU", "RU" will result in the desired ending point if we start from the given starting point.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY|
Fetching successful submissions