Count Distinct Palindromic Substrings

Given a string S, determine the number of distinct non-empty palindromic substrings contained within it. A palindrome is a sequence of characters that reads the same forwards and backwards. For example, the string "ababa" contains the palindromic substrings "a", "b", "aba", "bab", and "ababa". Since the answer can be large, report it modulo \(10^9+7\).

Note: A substring is a contiguous sequence of characters within a string.

inputFormat

The input is provided from stdin as a single line containing the string S. The string may be empty or consist of lowercase English letters.

outputFormat

Output the number of distinct non-empty palindromic substrings contained in the string S, modulo \(10^9+7\), to stdout.

ababa

5