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()