题目描述

把字符串切成若干个非空连续子串，要求每段都是回文串。求合法切分方案数。

输入格式

一行一个仅含小写字母的字符串。

输出格式

输出合法切分方案数。

样例

aab

2

数据规模与约定

$1\le |s|\le25$，答案在 long long 范围内。