Transporter

Time Limit : 1 sec, Memory Limit : 262144 KB

ワープ装置

西暦30xx年、ある星を訪れた探検隊は、謎の超文明が作ったワープ装置を発見した。ワープ装置の入り口を通ると、出口がどんなに遠く離れたところにあっても瞬時に移動できる。この技術を解明すれば、人類は宇宙の果てまで旅することができるのだ!

調査を始めた科学者チームは、ワープ装置の出入り口が存在するすべての星を特定した。星には、$1$から$N$までの番号が振られており、それぞれの星にはワープ装置の入り口と出口が一つずつある。入り口と出口には、それぞれ一つずつ文字が記されている。

ワープ装置の間の移動の仕組みは以下のようなものである。

  • 文字aが書かれている入り口から入ると、文字aが書かれた出口のどれかに移動できる。
  • 星iにある入り口から入ると、i<jを満たす星jにある出口だけから出ることができる。

ある星に置かれたワープ装置の出口から出た後、同じ星にあるワープ装置の入り口から入ることを繰り返していけば、ワープ装置を乗り継いで遠くの星までたどり着くことができる。人類は星$1$を起点として星$N$に探検隊を派遣することにした。星$N$に到達できる可能性を見積もるために、星$1$から出発したときに星$N$に到達できる行き方が何通りあるか計算することになった。

星の情報が与えられたとき、星$1$から星$N$まで行く方法が何通りあるか求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$s$
$t$

1行目にワープ装置がある星の数$N$ ($2 \leq N \leq 100,000$)が与えられる。2行目に、$1$から$N$までの星にあるワープ装置の入り口に書かれた文字を表す長さ$N$の文字列$s$が与えられる。3行目に、$1$から$N$までの星にあるワープ装置の出口に書かれた文字を表す長さ$N$の文字列$t$が与えられる。ただし、$s$と$t$に現れる文字はすべて英小文字であり、$s$の$i$番目の文字が星$i$にあるワープ装置の入り口に書かれた文字、$t$の$i$番目の文字が星$i$にあるワープ装置の出口に書かれた文字を表す。

出力

星$1$から星$N$まで到達する方法が何通りあるかを表す数を$1,000,000,007$で割った余りを1行に出力する。

入出力例

入力例1

6
abbaba
baabab

出力例1

5

入力例2

25
neihsokcpuziafoytisrevinu
universityofaizupckoshien

出力例2

4