1019 - ワープ装置

2018/12/29 20:55:30 問題文を修正しました

2019/8/27 9:19:16 MODの値が(10^8+7)になってました。正しくは(10^9+7)です。ごめんなさい><

問題文

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

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

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

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

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

課題

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

入力・出力

入力

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

N
s
t

1行目にワープ装置がある星の数N(2≦N≦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