Bamboo Pole Tying

On a beautiful afternoon, Xiao W and Xiao C are in a bamboo forest competing in the art of tying bamboo poles. In the forest there are infinitely many identical short bamboos, each consisting of ( n ) segments. Each segment is painted in one of 26 colors, represented by the lowercase letters from ( \underline{a} ) to ( \underline{z} ). Thus, if one writes down the colors of the segments (from bottom to top) of a bamboo, a string consisting of lowercase letters is obtained.

Xiao W starts with one short bamboo (with color string ( S )) as the current pole. He may extend his pole by taking another short bamboo (which has the same color string ( S )) and tying it on top. The process is as follows: he chooses a nonnegative integer ( k) (with ( 0 \le k \le n )) and aligns the bottom ( k ) segments of the new bamboo with the top ( k ) segments of the current pole, one by one. The remaining top part of the new bamboo (its segments from ( k+1 ) to ( n )) then extends the pole. However, Xiao W is very particular about aesthetics: if two segments are tied together, their colors must be identical. Note that since the bamboo cannot be flipped, the new bamboo is always used in its given orientation (from bottom to top).

For example, if ( S = \underline{aba} ) (so ( n=3 )), then one may tie two bamboos in the following ways:

1. With ( k=0 ) (no overlap): the resulting pole’s color is ( \underline{abaaba} ).
2. With ( k=1 ) (overlap one segment, since the top segment of the pole ( a ) matches the bottom segment ( a ) of the new bamboo): the resulting color becomes ( \underline{ababa} ).
3. With ( k=n=3 ) (full overlap): the pole remains ( \underline{aba} ).

It turns out that when extending a pole such as ( \underline{ababa} ) further by tying another bamboo on top, different choices of ( k ) can produce poles of different lengths.

Your task is: given a bamboo color string ( S ) (of length ( n )) and an integer ( w ) representing the maximum allowed total number of segments, count how many different pole lengths (in terms of number of segments) Xiao W can obtain, provided the pole’s length does not exceed ( w ). The pole’s length is defined as the total number of segments (from bottom to top). Note that if ( w < n ) (i.e. the allowed maximum is less than the length of a single bamboo), then no valid pole can be formed and the answer is 0.

Analysis

When tying a new bamboo to an existing pole, if you choose an overlap of ( k ) segments (where ( k ) satisfies that the top ( k ) segments of the current pole equal the first ( k ) segments of ( S )), the new pole will have its length increased by ( n-k ) segments.

Let the set of all valid overlaps (i.e. all ( k ) in ( [0, n] ) such that the prefix ( S[0:k] ) equals the suffix ( S[n-k:n] )) be ( B ). Then each tie contributes an extra length of ( d = n - k ) where ( k \in B ) and ( k < n ) (ignoring the trivial case ( k=n ) which leaves the pole unchanged). Notice that ( d = n ) is always available (taking ( k=0 )).

Hence, starting from an initial length of ( n ), every extension increases the pole length by some coin value ( d ) chosen from the coin set ( C = { n-k : k \in B,, k < n } ). The problem thus reduces to finding all values of ( t \ge 0 ) that can be expressed as a sum of these coin values such that ( n+t \le w ).

Let ( L = w - n ). Then we need to count the number of distinct ( t ) (from the coin change problem with coins from ( C )) with ( t \le L ).

A standard approach is to use dynamic programming to mark reachable sums. Note that if the coins have a common divisor greater than 1, only the multiples of that divisor can be reached. We handle that by normalizing the coins and the limit accordingly.

Below is an implementation in several languages.

inputFormat

The input consists of two lines:

1. An integer \( w \) representing the maximum allowed number of segments of the pole.
2. A string \( S \) of lowercase letters representing the colors of the segments of a short bamboo. Its length is \( n \).

Note: If \( w < n \), then no valid pole can be formed.

outputFormat

Output a single integer: the number of different pole lengths Xiao W can obtain (each length is the total number of segments), not exceeding \( w \).

sample

6
ab

3