your name in my na*e

2 secs 1024 MB
ir_1st_vil

問題文


文字列 が与えられます。各 について、 から 文字目を取り除いた文字列 の(連続とは限らない)部分列として が現れる回数を で割った余りを求めてください。

制約


  • は英小文字からなる

入力



出力


行出力してください。
行目には の(連続とは限らない)部分列として が現れる回数を で割った余りを出力し、最後に改行してください。

入力例1

aaba
aa
出力例1

1
1
3
1

文字目が取り除かれた場合は 文字目からなる部分列を数えるので答えは です。
文字目が取り除かれた場合は 文字目からなる部分列、 文字目からなる部分列、 文字目からなる部分列を数えるので答えは です。

入力例2

bcabbacdbdcaccbdabdb
abc
出力例2

14
14
3
10
10
11
12
14
8
14
10
14
10
10
14
14
14
14
14
14
入力例3

atcodergrandcontest
toketa
出力例3

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Submit


Go (1.14)