Palindromic Partitions

Given a string s consisting of lowercase English letters, your task is to count the number of ways to partition the string into contiguous substrings such that each substring is a palindrome. Two partitions are considered different if they split the string at different positions.

The answer may be very large, so you must return the count modulo \(10^9 + 7\). A substring is a contiguous sequence of characters from the string and a palindrome is a string that reads the same forwards and backwards.

Example:

Input: aab
Output: 2
Explanation: There are two valid partitions: ["a", "a", "b"] and ["aa", "b"].

</p>

Please note: The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The input consists of a single line containing a non-empty string s (only lowercase English letters), which is the string to be partitioned.

outputFormat

Output a single integer: the number of ways to partition the string into palindromic substrings, taken modulo \(10^9+7\).

## sample

a

1