1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def combinations(array, tuple_length, prev_array=[]):
    if len(prev_array) == tuple_length:
        return [prev_array]
    combs = []
    for i, val in enumerate(array):
        prev_array_extended = prev_array.copy()
        prev_array_extended.append(val)
        combs += combinations(array[i+1:], tuple_length, prev_array_extended)
    return combs

def fantasticSubStrings(s):
    fantastic = 0
    for length in range(len(s)):
        combs = combinations(s, length+1)
        for i in range(len(combs)):
            combs[i] = tuple(combs[i])
        comb_set = set(combs)
        for i in comb_set:
            if isFantastic(i): fantastic += 1
    return fantastic % (1000000007)

def isLeftSkew(s):
    leftSkew = 0
    for i in s: leftSkew += (1 if i == 'L' else -1)
    return leftSkew >= 0

def isBalanced(s):
    leftSkew = 0
    for i in s: leftSkew += (1 if i == 'L' else -1)
    return leftSkew == 0

def isFantastic(s):
    if len(s) % 2 == 1: return False #nie będzie zbalansowany!
    for i in range(1,len(s),1):
        if not isLeftSkew(s[:i]):
            return False
    return isBalanced(s)

n = int(input())
s = [0,]*n
for i in range(n):
    s[i] = input()

for i in range(n):
    for j in range(n):
        print(fantasticSubStrings(s[i]+s[j]), end=" ")
    print()