Maurice Tutor
$15/per page/Negotiable
q1
Chef likes strings a lot but moreover he likes good strings. Chef calls a string str a good string if str starts and ends at different characters. For eg : strings such as abab , baccba , abc are all good strings whereas strings like aba, baab , baacaab are not good at all .
Today, Chef has a special string P consisting of lower case letters "c" , "h" , "e" and "f" only. Chef wants to make some queries about his string P.
Each of chef's query has the following form a b L R. For a given query, Chef wants to count the number of good strings which starts at letter a and ends at letter b such that starting index Si and ending index Ei of a chosen substring satisfies L i i .
NOTE
Two substrings P1 and P2 are considered to be different if either S1 != S2 or E1 != E2 where S1,E1 and S2,E2 are the starting and ending index of string P1 and string P2 respectively.
Chef is not able to accomplish this task efficiently. Can you help him ?
First line of the input contains a string P denoting the chef's special string. Next line of the input contains a single integer Q denoting the number of chef's queries. Next Q lines of the input contains four space separated parameters where the first two parameters are characters denoting a and b respectively and rest two are integers denoting L and R respectively.
For each chef's query, print the required answer.
Input checfcheff 5 c h 1 10 c f 1 10 e c 1 10 c f 1 5 c f 6 10 Output 4 8 2 2 2
Large test data set, Prefer to use faster input/output methods .
q2
Consider directed graph which has n + 2 layers numbered from left to right by integers from 0 up to n + 1. The leftmost (0) and the rightmost (n + 1) layers both contain only one vertex while every other layer contains exactly m vertices. Vertices are numbered independently in each layer by integers from 0 to m - 1. For each pair of vertices which are in the adjacent layers (i and i + 1 for any i (0 ), there exists an edge. The vertex which is in the layer with smaller number is the initial vertex for such edge and the other one is the terminal vertex.
Based on a graph as described above, Chef added k more edges. Each edge connects two vertices which are in the different layers, no matter the adjacent layers or not. Also, each edge is directed from left to right (as well as all previously existing edges).
Chef is interested in the number of ways to get from the leftmost layer to the rightmost one. Two paths are considered different if there is, at least, one edge which belongs to exactly one path. However, they are allowed to traverse the same set of vertices. In that case, there should be a multiple edge in the graph. It is also possible if some edge added by Chef connects two adjacent layers.
The first line of the input contains three space-separated integers: n, m and k.
k lines follow. Each of them describes one of the k additional edges and contains four space-separated integers edgei (where 0 i 3). First two integers are for the initial vertex and the other two - for the terminal one. Two integers each vertex is described by are the number of the layer (edge0 and edge2 respectively) and number of the vertex in its layer (edge1 and edge3 respectively).
Output a single integer: the number of ways to reach the last layer from the initial one modulo 109+7.
Input: 4 2 2 2 1 5 0 0 0 4 0 Output: 19
Consider the graph without 2 edges added by Chef. There are 16 ways to get from the layer #0 to the layer #5. Now recall added edges. There are 2 ways to get from the layer #0 to the layer #5 using the edge 2 1 5 0 (0, 0 -> 1, 0 -> 2, 1 -> 5, 0 and 0, 0 -> 1, 1 -> 2, 1 -> 5, 0) and also 1 way to do it using the edge 0 0 4 0 (0, 0 -> 4, 0 -> 5, 0). Note, that there is no path traversing both added edges.