J. Party Game
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Fernando is an avid party game player, as they are a great way to liven up social gatherings and facilitate interaction among participants. Many party games involve alternating turns among several players, with each person taking their turn. Therefore, when people want to play a party game, they need to decide on the order of players, which is usually resolved through some playful method that generates a random outcome. Among these decision-making games, Fernando's favorite is the game of "even or odd".

However, the math enthusiasts among the group are never satisfied with this decision method. When they show up at parties (which is rare), they can't help but complain about the lack of fairness in various methods. Even though Fernando and his friends enjoy playing party games just for fun, they decided to listen to the mathematicians' suggestions to achieve a more uniform outcome. They defined some requirements for a method to be truly fair:

  • First player fairness: Every player has an equal chance of going first.
  • Position fairness: For every position, all players have the same chance of ending up there. Therefore, everyone has the same chance of being first, the same chance of being second, and so on.
  • Permutation fairness: All possible permutations of player orders have an equal chance of being chosen.

Note that it's possible for a method to uniformly determine each player's position, but not all permutations may have the same probability of occurring. One of the mathematicians' favorite methods of random selection is using dice, so they created sets of dice that satisfy some of these properties.

Each of the $$$N$$$ players receives a die identified by a letter of the alphabet, and each number from $$$1$$$ to $$$M$$$ appears on only one die. Thus, each player rolls their own die, and the order of the numbers rolled on the dice is used as the order of the players. The player with the highest-numbered die goes first, the one with the second-highest value goes second, and so on.

A set of dice is described by a string of $$$M$$$ letters, where each position assigns the value of the position index to one of the dice, and the dice are represented by the first $$$N$$$ letters of the lowercase Latin alphabet. For example, the set of dice dcbabccccbabcddddcbabccccbabcd satisfies the fairness property for 4 players:

Well... Fernando and I were also hoping that the dice would at least be of the same size. Apparently not, but anyway. Now, you're curious and want to know if a given set of dice satisfies both position fairness and permutation fairness. To determine that, you need to calculate the probability of each player obtaining each position and the probability of each permutation.

Input

The first line of input contains the integer $$$N$$$ $$$(1 \le N \le 7)$$$, the number of players and dice, and the integer $$$M$$$ $$$(N \le M \le 600)$$$, the number of values to be placed on the dice.

The second line of input contains the set of dice $$$D$$$ with $$$|D| = M$$$. The only allowed characters are the first $$$N$$$ lowercase Latin alphabet letters, and it is guaranteed that the letters appear at least once.

Output

Print $$$N$$$ lines, each describing player $$$i$$$ $$$(1 \le i \le N)$$$, the one who uses the die corresponding to the $$$i$$$-th letter of the Latin alphabet. The lines should consist of $$$N$$$ integers $$$P_{ij}$$$ $$$(1 \le j \le N)$$$, where $$$P_{ij}$$$ is the probability that player $$$i$$$ is in position $$$j$$$ modulo $$$10^9 + 7$$$.

Next, print on a line 'S' if the set of dice has permutation fairness, or 'N' if it doesn't. Finally, print on another line the product of the probabilities of obtaining a specific permutation out of all possible permutations modulo $$$10^9 + 7$$$.

To print a probability $$$\frac{p}{q}$$$, print $$$p \cdot q^{-1} \pmod{10^9+7}$$$. It is proven that $$$q^{-1}$$$ exists for any $$$q$$$ and is unique modulo $$$10^9+7$$$.

Examples
Input
4 30
dcbabccccbabcddddcbabccccbabcd
Output
250000002 250000002 250000002 250000002
250000002 250000002 250000002 250000002
250000002 250000002 250000002 250000002
250000002 250000002 250000002 250000002
S
440369483
Input
3 4
abca
Output
500000004 0 500000004
0 500000004 500000004
500000004 500000004 0
N
0
Note

In the first example, all players have the same probability of ending up in any position, which is $$$\frac{1}{4}$$$. Thus, the answer for all positions of all players is the same, $$$4^{-1} = 250000002 \pmod{10^9+7}$$$. All permutations have the same probability of $$$\frac{1}{24}$$$, and the product of the probabilities of all $$$24$$$ possible permutations is $$$\frac{1}{24^{24}}$$$, which is $$$24^{-24} = 440369483 \pmod{10^9+7}$$$.

In the second example, player $$$1$$$ using die a has a $$$\frac{1}{2}$$$ chance of being the first to play (by rolling a 4) and a $$$\frac{1}{2}$$$ chance of being the last to play (by rolling a 1). The other two players have dice with only one face, and their positions depend solely on player $$$1$$$'s die. Player $$$2$$$ with die b is either second or third, and player $$$3$$$ with die c is either first or second. Since there are only two possible permutations of player order, the product of the probabilities of all possible permutations is zero, and this is not a set of dice with permutation fairness.