Jovsi is still a strong boy. Since he was little, he has loved machine guns and often liked to imitate them, but for some reason, he didn't shout trtrtrt or bambambam, but acacacacac.

Mr. Malnar is not impressed by Jovsi's strength and is exclusively interested in his ability to solve problems. So, one day, he gave him a stick on which $n$ letters are written from the left end to the right end. Mr. Malnar considers symmetric sticks to be very beautiful, which is why he is particularly interested in palindromic pairs. These are ordered pairs of natural numbers $(l, r)$, where $1 \le l \le r \le n$, such that the word obtained by looking only at the letters from the $l$-th to the $r$-th position is a palindrome. Recall that a palindrome is a word that reads the same from left to right as it does from right to left.

Mr. Malnar then decided to give Jovsi a challenge. The challenge consists of a natural number $k$ and a sequence of $k$ palindromic pairs $(l_i, r_i)$ for which $l_1 < l_2 < \dots < l_k$ and $r_1 > r_2 > \dots > r_k$ hold.

Jovsi must be prepared for any situation, so he is interested in how many different challenges he can receive from Mr. Malnar. Help Jovsi and print the number of different challenges, modulo $998244353$.

Input

The single line contains a word consisting of lowercase English letters, representing the sequence of letters written on Mr. Malnar's stick. The word will consist of at most one million characters.

Output

In the single line, print the remainder when the number of different challenges is divided by $998244353$.

Examples

Input 1

anadanaokoabanana

Output 1

65

Input 2

acacacacac

Output 2

242

Input 3

ananas

Output 3

18