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++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"6c0ac0f": "/pagelets/recommended-problems/algorithm/vasya-and-work/", "6c0abe3": "/pagelets/problem-author-tester/algorithm/vasya-and-work/", "6c0ab97": "/pagelets/show-submission/algorithm/vasya-and-work/", "6c0abfa": "/pagelets/problems-hint/algorithm/vasya-and-work/", "6c0abb6": "/pagelets/suggested-problems/algorithm/vasya-and-work/"}

{}

realtime.hackerearth.com

80

5245d29e785e5e82ed226bc6279e38dd1f6cb9d3

58a29e5cae2309f04b28

/realtime/pusher/auth/