「あれ、私の大学、何の略だっけ……？」
shogo314君は自分の所属する大学の名前を思い出そうとしていますが、どうしても「NAIST」という略称しか思い出せません。手元には、大学に関連しそうな英小文字のみからなる長い文字列が書かれたメモがあります。もしかしたら、この文字列の中に正式名称が隠れているかもしれません。
英子文字からなる文字列 $S$ が与えられます。
文字列 $T$ が 良い文字列 であるとは次のすべての条件を満たすことをいいます。
naist は $T$ の部分列として現れる。良い文字列の種類数を求めてください。 ただし、文字列 $T$ が $S$ 内の複数箇所に出現する場合でも、$1$ 種類として数えてください。
なお、答えは符号付き $64$ ビット整数に収まることが保証されます。
部分文字列とは
文字列 $B$ が文字列 $A$ の部分文字列であるとは、$A$ の連続した部分を取り出して得られる文字列が $B$ と一致することをいいます。
例えば、ai は naist の部分文字列ですが、as は naist の部分文字列ではありません。
部分列とは
文字列 $B$ が文字列 $A$ の部分列であるとは、$A$ から $0$ 個以上の文字を順序を保って取り出して連結した文字列が $B$ と一致することをいいます。
例えば、as は naist の部分列ですが、ta は naist の部分列ではありません。
入力は以下の形式で標準入力から与えられます。
$S$
答えを $1$ 行に出力してください。
naistnaist
10
naist, naistn, tnaist, naistna, stnaist, naistnai, istnaist, naistnais, aistnaist, naistnaist
の $10$ 種類あります。
narainstituteofscienceandtechnology
28