흥미로운 할로윈 축하 방식

매년 마이어스 가족이 할로윈을 같은 방식으로 축하하면 금방 지루해진다. 그래서 할로윈이 지루하지 않도록 축하 방식을 다양하게 바꾸고 싶어진다.

할로윈을 축하하는 방식은 확실히 알려진 것만 $26$가지이며, $i$번째 방식은 라틴 알파벳의 $i$번째 글자($\mathtt{a}$부터 $\mathtt{z}$까지)로 나타낼 수 있다. 마이어스 가족은 오랫동안 할로윈을 축하해 왔고, 매년 어떤 방식으로 축하했는지 기록해 두었다.

가족은 연도들의 부분수열(반드시 연속하지 않아도 됨) 중에서 흥미로운 것이 몇 개인지 알고 싶어 한다. 흥미로운 축하 방식의 수열은 정확히 $26$개이며, 다음과 같이 정의된다.

• $\mathtt{seq}\_1 =$ <<a>>
• $\mathtt{seq}\_{i+1} = \mathtt{seq}\_i + \text{<<}c\_{i+1}\text{>>} + \mathtt{seq}\_i$. 여기서 $c\_{i+1}$은 라틴 알파벳의 $(i+1)$번째 글자이다.

처음 세 개의 흥미로운 수열은 <<a>>, <<aba>>, <<abacaba>>이다.

문자열 $s$가 주어지며, $s$의 $i$번째 문자는 $i$번째 해의 축하 방식이다. $s$의 부분수열 중 흥미로운 수열인 것의 개수를 구하라. 개수가 매우 클 수 있으므로 $998244353$으로 나눈 나머지를 구한다. 부분수열은 주어진 문자열에서 일부(0개일 수도 있음) 문자를 지워 얻은 문자열이다.

한 줄에 문자열 $s$ $(1 \leqslant |s| \leqslant 5000)$가 주어진다.

이 문자열의 부분수열 중 $\mathtt{seq}\_i$ 형태인 것의 개수를 $998244353$으로 나눈 나머지로 출력한다.

문자열 <<abacaba>>에서는 <<a>> 부분수열 $4$개, <<aba>> 부분수열 $6$개, <<abacaba>> 부분수열 $1$개를 고를 수 있다.