Frog Segmentation Happiness Sum

There are two sequences a and b each of length n that consist only of characters 0 and 1. They can be thought of as two rows (or columns) of frogs. We define a segmentation scheme as a partition of the indices [1,n] into contiguous segments with identical start–end points in both sequences. Formally, if a segmentation scheme divides the indices into k segments \([l_1,r_1], [l_2,r_2], \dots, [l_k,r_k]\) then we must have:

• l1 = 1 and rk = n
• For every \(1 \le i < k\), \(r_i + 1 = l_{i+1}\).

For a segment \([l,r]\), define its "tidiness" value as

[ T(l,r) = \sum_{i=l}^r [a_i \neq b_i], ]

where \([P]\) is \(1\) if the proposition \(P\) is true and \(0\) otherwise.

Next, define for sequence a:

[ A(l,r) = \text{number of } 01 \text{ type subsequences in } a \text{ over indices } [l,r], ]

and for sequence b:

[ B(l,r) = \text{number of } 10 \text{ type subsequences in } b \text{ over indices } [l,r]. ]

A subsequence of type xy is defined by choosing two indices \(i < j\) (not necessarily consecutive) such that the first number is \(x\) and the second is \(y\).

Then the happiness value of a segment is defined as

[ W(l,r) = T(l,r) \times \Big( A(l,r) + B(l,r) \Big). ]

The overall happiness of a segmentation scheme is the sum of \(W(l_i,r_i)\) over its segments. You are to compute the sum of the happiness values over all possible segmentation schemes modulo \(10^9+7\).

Important: Two segmentation schemes are considered different if they have a different number of segments or there exists an index \(i\) such that \([l_i,r_i]\) differs.

---

Formal Problem Statement

Given two sequences a and b each of length n, compute

[ S = \sum_{\text{segmentation scheme}} ; \sum_{\text{segment } [l,r] \text{ in scheme}} ; W(l,r) \mod (10^9+7). ]

Note that each segmentation scheme is formed by choosing where to place cuts between adjacent positions. In particular, consider the boundaries between indices. There are \(n-1\) potential boundaries. A segment \([l,r]\) appears in a segmentation scheme if and only if:

• For every \(l < r\), none of the boundaries between \(l\) and \(r\) (i.e. indices \(l, l+1, \dots, r-1\)) have a cut.
• If \(l > 1\), then there is a cut between \(l-1\) and \(l\).
• If \(r < n\), then there is a cut between \(r\) and \(r+1\).

If the number of fixed boundaries for segment \([l,r]\) is \(F = (r - l) + [l>1] + [r<n]\) then the number of segmentation schemes in which this segment appears is \(2^{(n-1)-F}\). Using this observation, you can sum the contribution of each possible segment \([l,r]\):

[ S = \sum_{1 \le l \le r \le n} 2^{(n-1) - \Big((r-l) + [l>1] + [r<n]\Big)} \times \Big(T(l,r) \times (A(l,r)+B(l,r))\Big) \mod (10^9+7). ]

Your task is to compute \(S\).

inputFormat

The first line contains an integer n representing the length of the sequences.

The second line contains a binary string of length n representing sequence a.

The third line contains a binary string of length n representing sequence b.

outputFormat

Output a single integer, the sum of happiness values over all segmentation schemes modulo \(10^9+7\).

sample

2
01
10

4