SOLVE

LATER

Vasya and Work

Problem

Editorial

Analytics

Vasya lives in Byteland, that is a small town where each house in the town can be represented using points on the Ox Axis. There are *N* houses in the town, enumerated from *1* to *N*, and the \(i^{th}\) house lies at point *i* on the \(x-axis\)

Now, exactly a single family lives in each house of the town, and every family has a **Food Type** and a **Sleep Type**. The food type of a family represents the type of food the family likes to eat, and can be represented using lowercase English alphabets from *a* to *z*. In addition, the sleep type of each family represents their sleeping habits, and can be of *2* types represented using *0* or *1*.

Now, there is a tradition in Byte land as per which any two families come-together and host a party for some other houses in the town. The party is considered **Special** if the two host families have either the same food type or the same sleep type, or both. Now, Vasya is a very curious girl, and she loves combinatorics too. She gives you some queries, where each query is of the form:

\(Query (L,R)\) : Find the number of ways any two different families living from point *L* to *R* inclusive can host a **Special** party. Two ways are considered different if at least one of the host families is different. As the answer can be rather large, print it **modulo** \(10^9+7\) .

She thinks that you are the ideal person to answer such queries, and wants you to help her out. Can you ?

**Input Format** :

The first line contains a single integer *N* denoting the number of families residing in byteland. The next line contains a String \(S1\) of length *N*, consisting of lowercase english alphabets, where the \(i^{th}\) character of the string represents the food type of the \(i^{th}\) family. The next line contains a binary String \(S2\) of length *N*, where the \(i^{th}\) character represents the sleep type of the \(i^{th}\) family.

The next line contains a single integer *q* denoting the number of queries Vasya presents to you. Each of the next *q* lines contains *2* space separated integers \(L_{i}\) and \(R_{i}\), denoting the parameters of the \(i^{th}\) query.

**Output Format** :

For each query, print the answer on a new line.

**Constraints** :

\( 1 \le N \le 10^5 \)

\( 1 \le q \le 10^5 \)

\( 1 \le L \le R \le N \)

\( S1 \subseteq ('a'-'z') \)

\( S2 \subseteq ('0'-'1') \)

Explanation

For the \(1^{st}\) query, the \(1^{st}\) and the \(2^{nd}\) families come together to host a party as they have the same sleep type. Similarily, for the \(2^{nd}\) query, the \(3^{rd}\) and the \(4^{th}\) families come together.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"5ce7ec6": "/pagelets/problems-hint/algorithm/vasya-and-work/", "35dc178": "/pagelets/show-submission/algorithm/vasya-and-work/", "0e9a288": "/pagelets/problem-author-tester/algorithm/vasya-and-work/", "6778984": "/pagelets/suggested-problems/algorithm/vasya-and-work/", "6ead8dd": "/pagelets/recommended-problems/algorithm/vasya-and-work/"}

realtime.hackerearth.com

80

5245d29e785e5e82ed226bc6279e38dd1f6cb9d3

58a29e5cae2309f04b28

/realtime/pusher/auth/