409750: GYM103729 D Transition

Rarity is a Unicorn pony who is a famous fashion designer.

One day, she is designing an important uniform for Summer Sun Celebration, but the designs of floral patterns on it are always different from her intention. With hard endeavor, she comes up with a perfect idea and can't wait to test it on the uniform!

Now Rarity wants to change the initial pattern $$$a$$$ to the new idea $$$b$$$. A pattern can be regarded as a string consisting only of '0' or '1'. It's guaranteed that pattern $$$a$$$ and $$$b$$$ have the same length.

We define the $$$i$$$-th character of a string $$$s$$$ as $$$s_i$$$, and the length of $$$s$$$ as $$$|s|$$$.

She could do the following operations any times:

1. Choose two indices $$$i,j \ (1\le i<j\le |a|)$$$, then swap $$$a_i$$$ and $$$a_j$$$, which costs $$$j-i$$$ units of time.

2. Choose an index $$$i\ (1\le i\le |a|)$$$, then flip $$$a_i$$$ (i.e. change $$$a_i$$$ to $$$1$$$ if it's $$$0$$$ initially, vice versa), which costs $$$1$$$ unit of time.

It's easy for Rarity to find the minimum cost in changing $$$a$$$ to $$$b$$$, but how about the number of different legal operation sets (i.e. a set consists some operations) to get that in minimum cost?

We consider one operation set legal, if it has at least one operation order to change $$$a$$$ to $$$b$$$.

We consider two operation sets different, if and only if one operation exists in one set but not in another.

We consider two operations different, if and only if they choose different index set (i.e. different in size or element).

Since the answer can be quite large, print it modulo $$$10^9+7$$$.

The first line contains an integers $$$n\ (1\le n\le 3\times 10^5)$$$ - the length of string $$$a,b$$$.

The second line contains a string of length $$$n$$$ - represent as $$$a$$$.

The third line contains a string of length $$$n$$$ - represent as $$$b$$$.

Only a single integer - the number of different operation sets modulo $$$10^9+7$$$.

4
0111
1100

3

7
0101001
1010110

3

We will denote set $$$\{i,j\}$$$ as an operation $$$1$$$ that swaps $$$a_i$$$ and $$$a_j$$$, $$$\{i\}$$$ as an operation $$$2$$$ that flips $$$a_i$$$.

For the first test case, the minimum cost is $$$3$$$, and the possible operation set are $$$\{\{1,3\},\{4\}\}$$$, $$$\{\{1,2\},\{2,3\},\{4\}\}$$$ and $$$\{\{1\},\{3\},\{4\}\}$$$.

For the second test case, the minimum cost is $$$4$$$, and the possible operation set are $$$\{\{1,2\},\{3,4\},\{5\},\{6,7\}\}$$$, $$$\{\{1,2\},\{3\},\{4,5\},\{6,7\}\}$$$ and $$$\{\{1\},\{2,3\},\{4,5\},\{6,7\}\}$$$.