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')$