题目描述

输入一个长度为n的字符串S($n \le 5000$，可同时含有大小写字母)，统计出它的所有划分的个数，其中满足每个划分后的各部分都是回文串。

输入

第一行，一个整数n

第二行，一个长度为n字符串S

输出

一行，所有划分的总数，对998244353取模

样例

input

5

ABCBC

output

3

解释

以下三种

A B C B C

A BCB C

A B CBC