Suffix array

ID 38134. Balanced Subsets

Farmer John's pasture can be represented as a huge 2D grid of cells labeled with ordered pairs (i,j) for all 1≤i≤N, 1≤j≤N (1≤N≤150). Some of these slots contain grass.
A non-empty subset of lattice cells is called "balanced" if the following conditions are met:

All subset cells contain grass.
The subset is 4-connected. In other words, there is a path from any cell in the subset to any other cell in the subset such that two consecutive cells of the path are horizontally or vertically adjacent.
If cells (x₁,y) (x₂,y) (x₁≤x₂) is part of the subset, then all cells (x,y) with x₁≤x≤x₂ are also part of the subset.
If cells (x,y₁) and (x,y₂) (y₁≤y₂ ) is part of the subset, then all cells (x,y) with y₁≤y≤y₂ are also part of the subset.
Count the number of balanced subsets modulo 10⁹+7.

Input: 
The first line contains the number N.
Each of the subsequent N lines contains a string of N characters. The j-th character of string i from the top is equal to G if cell (i,j) contains grass or character . otherwise.

Output: 
Number of balanced subsets modulo 10⁹+7.
 

Examples

ID 38511. Journey along the line

Let's say that the sequence of strings t₁ , ..., t_k is a journey of length k if for all i > 1 t<sub>i< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.

Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.

Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .

Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .

The second line contains the string s , consisting of n lowercase English letters.

Imprint
Print one number — the longest travel length in string s .

Note
In the first example, the longest string traversal is { abcd , bc , c } .

In the second example, { bb , b } would be appropriate.</sub>

Examples

ID 38645. Optimal subset of rows - 2

Today at the lesson Petya learned about non-suffix codes. A set of strings is called a non-suffix code if
- All rows in the set are distinct
- There is no pair of distinct strings such that one string is a suffix of the other
The string s is called the prefix of the string t if the length of the string s is not greater than the length of t, and also for any i, the i-th character of the string s matches the i-th character of the string t. For example, ab prefixes ab and abc, but does not prefix a and ac.
Petya decided to come up with something new and introduced a new concept — k-suffix code. This code he called a set of lines, such that:
- All rows in the set are distinct
- For any two distinct strings, the longest common prefix has length at most k
The greatest common prefix of two strings s and t is the longest string that is the prefix of both strings.
Now, given the set of strings s1, s2, ..., sn and the number k, Petya wants to find in this set a k-suffix-free code consisting of the maximum possible number of strings. Help him — find this code.
Input
The first line contains two numbers n and k — the number of rows in the set and the maximum length of the common prefix respectively (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100).
The i-th of the next n lines contains a string of lowercase Latin letters si — i-th word from the set (1 ≤ |si| ≤ 100).
It is guaranteed that the total length of all strings in the set does not exceed 10⁶.
Imprint
On the first line print the number m - the maximum possible number of lines in the k-suffix-free code. In the i-th of the next m lines print the i-th element of this code. Code elements can be displayed in any order.
If there are multiple answers with maximum m, any one is allowed.