You are given a string s. A "palindromic partition" splits s into one or more contiguous, non-overlapping pieces (covering the whole string in order) such that every piece is itself a palindrome. Two partitions are considered different if they split the string at different positions. Count the number of distinct palindromic partitions of s, modulo 1000000007.
Input format
Line 1: the string s.
s contains only lowercase English letters.
Output format
A single integer: the number of ways to partition s into contiguous palindromic pieces, modulo 1000000007.
Constraints
- 1 <= |s| <= 18