Number of Strings Containing a Substring

Count length-L lowercase strings that contain the given word S as a contiguous substring, modulo 1,000,000,009.

Medium6Dynamic programmingString matchingNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

You are given a word $S$ made of lowercase letters. Count the strings of length $L$ that consist only of lowercase letters and contain $S$ as a substring.

A substring is a contiguous block of characters.

Input

The first line contains the length $L$ ( $1 \le L \le 100$ ).

The second line contains the word $S$ . It consists only of lowercase letters and its length is at most 100.

Output

Print the number of such strings modulo 1,000,000,009 on the first line.