西暦30xx年、ある星を訪れた探検隊は、謎の超文明が作ったワープ装置を発見した。ワープ装置の入り口を通ると、出口がどんなに遠く離れたところにあっても瞬時に移動できる。この技術を解明すれば、人類は宇宙の果てまで旅することができるのだ!
調査を始めた科学者チームは、ワープ装置の出入り口が存在するすべての星を特定した。星には、$1$から$N$までの番号が振られており、それぞれの星にはワープ装置の入り口と出口が一つずつある。入り口と出口には、それぞれ一つずつ文字が記されている。
ワープ装置の間の移動の仕組みは以下のようなものである。
ある星に置かれたワープ装置の出口から出た後、同じ星にあるワープ装置の入り口から入ることを繰り返していけば、ワープ装置を乗り継いで遠くの星までたどり着くことができる。人類は星$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行に出力する。
6 abbaba baabab
5
25 neihsokcpuziafoytisrevinu universityofaizupckoshien
4