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
import numpy as np


def main():
    n = int(input())
    t = []
    for i in range(n):
        t.append(input())
    t3 = np.zeros(shape=(n, n), dtype=int)

    BIG_NUMBER = 10**9 + 7

    for i in range(n):
        for j in range(n):
            s = t[i] + t[j]
            lol = len(s)
            x = s.find("L") + 1
            count = 0

            if x:
                left = np.zeros(lol)
                right = np.zeros(lol)
                left[1] = 1
                right[1] = 1
                for index in range(x, lol):
                    if s[index] == "L":
                        left[1:] = left[:-1]
                        left[0] = 0
                        right += left % BIG_NUMBER
                    elif s[index] == "P":
                        right[:-1] = right[1:]
                        count += right[0] % BIG_NUMBER
                        count %= BIG_NUMBER
                        left += right % BIG_NUMBER
                        right[0] = 0

            t3[i][j] = count

    for row in t3:
        print(*row)


if __name__ == '__main__':
    main()