Secret Passage

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S zero or more times:

• Remove the two characters at the beginning of S, erase one of them, and reinsert the other somewhere in S. This operation can be applied only when S has two or more characters.

Constraints

• 1 \leq |S| \leq 300
• S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of strings, modulo 998244353, that can result from applying the operation on S zero or more times.

Examples

Input

0001

Output

8

Input

110001

Output

24

Input

11101111011111000000000110000001111100011111000000001111111110000000111111111

Output

697354558

inputFormat

Input

Input is given from Standard Input in the following format:

S

outputFormat

Output

Print the number of strings, modulo 998244353, that can result from applying the operation on S zero or more times.

Examples

Input

0001

Output

8

Input

110001

Output

24

Input

11101111011111000000000110000001111100011111000000001111111110000000111111111

Output

697354558

样例

110001

24