Unique Palindromic Substrings

You are given a string S and an integer N. Your task is to determine the total number of unique palindromic substrings of length exactly N that appear in S. Two substrings are considered different if their contents differ. Since the answer can be large, output it modulo \(10^9+7\).

A palindromic substring is a substring which reads the same backward as forward. For example, in the string "ababa" and N = 3, the palindromic substrings of length 3 are "aba" and "bab". Thus the answer is 2.

inputFormat

The input consists of two lines:

• The first line contains the string S.
• The second line contains the integer N.

It is guaranteed that 1 ≤ N ≤ |S|.

outputFormat

Output a single integer, the number of unique palindromic substrings of length exactly N in S modulo \(10^9+7\).

ababa
3

2