### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

This problem can be solved using dynamic programming. The idea is based on a quite usual algorithm of checking if string **S** is a subsequence of some other string **T**: take the first character of **S** and find its first occurrence in **T** (say, **T**_{i}); take the second character of **S** and find its first occurrence in **T after** position i; take the third character of **S**… and so on, until there are no more characters in **S** (then **S** is indeed a subsequence of **T**) or there is no occurrence of the next character of **S** in **T** after the required position (then **S** is not a subsequence of **T)**. Each string of length **N** which is a subsequence of the string given in the input will be implicitly searched for using this algorithm.

Let the given string be **S**. Let **f _{i}, j** be the number of distinct strings of length

**i-j**such that if we search for each of them in

**S**, we’ll stop our search at position

**i**in

**S**(basically,

**j**stands for the number of skipped characters in

**S**). If we find an efficient way to calculate

**f**for all

_{i}, j**i ≤ N+K**and

**j ≤ K**, we’ll be able to find the answer easily as the sum of all

**f**such that

_{i}, j**i-j = N**.

A simple way to do this works in O(**NKM**), where **M** = 26 (the size of the alphabet). Set **f**_{0,0} = 1. Then, for each **i** and **j** try every possible next character (a…z) of the searched string and add **f _{i,j}, to f_{p,j} +(p-i-1)**, where

**p**is the position of the next occurrence of this character in

**S**after position

**i**. The position of the next occurrence of character

**c**in

**S**after position

**i**,

**next**, can be easily precalculated in O(

_{i,c}**NM)**time beforehand. However, this approach is too slow to get accepted.

To solve the problem in O(**NK**), we need to reverse our DP. From the above paragraph it can be inferred that **f**_{i,j} is equal to the sum of **f**_{p,j}-(**i-p-1**) for all **p** such that **t ≤ p < i**, where **t** is the largest integer smaller than i such that **S**_{i} = **S**_{t}. To find this sum quickly, an auxiliary DP **g**_{i,j} is needed such that **g**_{i,j} = **g**_{i}-1, **j**-1 + **f**_{i,j} (basically, all **g**_{i,j} represent partial sums on the “diagonals” of **f _{i,j})**. Then

**f**can be calculated in O(1) as

_{i,j}**f**

_{i,j}=

**g**

_{i}-

**1, j - g**

_{t}-

**1, j-(i-t)**. To understand why this is so, draw a rectangular matrix representing

**f**

_{i,j}and find out which elements of f sum up to each

**g**

_{i,j}, then note that the difference of those two elements of

**g**is actually a plain sum of all required elements of

**f**.

That’s all for the solution. Don’t forget that all calculations should be done modulo 1009419529. Also note that modulo operator (% in C++ and Java, mod in Pascal) is much slower than addition and subtraction, so it’s not recommended to use it when it’s possible not to use it. For reference of a solution without any modulo operations at all, see problem setter’s or problem tester’s (a single modulo at the end) solution.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.