Bob carefully plans to arrange all the candies in his bag, but to his dismay, all of the candy instantly falls out onto the floor! After picking up the candy, he prepares for Halloween by laying them on the table in a line to count. He counts a total of ~N~ candies. Furthermore, Bob has a preferred order ~S~ of eating candy, where each candy in ~S~ is distinct.

Bob will only pick candies to eat from left to right or from right to left without backtracking. Additionally, since he's a picky eater, Bob will only eat all candies in ~S~, and in the stated order. Eating a subsequence of candies from left to right versus right to left is only considered different if the index of at least one candy being eaten is different.

Please compute the number of ways Bob can eat candies.

Input Specification

The first line of input will contain an integer ~N~, representing the number of candies in his bag.

In the following two lines of input, each type of candy will be represented by a unique lowercase character.

The second line of input will contain a string of length ~N~ representing the order of candies on the table.

The third line of input will contain another string ~S~ of candies, representing his desired order of consuming candies.

Output Specification

The one and only line of output will contain an integer ~M~, representing the number of ways Bob can eat candies in his preferred order in mod ~10^9+7~.

Constraints

~1 \leq N \leq 10^6~

Subtask 1 [10%]

~N, |S| \leq 5~

Subtask 2 [90%]

No additional constraints.

Sample Input 1

3
aba
ab

Sample Output 1

2

Sample Explanation 1

Bob can either eat the leftmost two candies moving right, or rightmost two candies moving left.

Sample Input 2

56
aabababbbbbababababbaaababababbabbabaaabababbbabaaababab
ab

Sample Output 2

783

Sample Input 3

10
abcdabcdab
a

Sample Output 3

3