바이테시의 드리블링

바이테시는 전 세계에서 축구 드리블을 가장 잘하는 선수로 널리 알려져 있다. 다가오는 월드컵을 위해 그는 $n$개의 드리블 목록을 준비했다. 각 드리블은 'L'과 'P'로 이루어진 문자열로 표현되며, 선수가 왼발과 오른발 중 어느 쪽으로 공을 터치하는지 그 순서를 나타낸다.

드리블에서 왼발 터치 횟수와 오른발 터치 횟수가 정확히 같으면 그 드리블은 균형 잡힌 드리블이다. 드리블의 모든 접두사에서 왼발 터치 횟수가 오른발 터치 횟수보다 적지 않으면 그 드리블은 왼쪽 우세 드리블이다. 왼발잡이인 바이테시는 균형 잡히고 왼쪽 우세인 드리블을 환상적이라고 본다.

월드컵에는 최고의 선수들이 모이므로, 바이테시는 $n$개로는 부족하다고 판단했다. 그는 간단한 방법으로 개수를 $n^2$개로 늘린다. 목록에서 두 드리블을 고르는 모든 쌍(같은 드리블을 두 번 골라도 된다)에 대해, 두 문자열을 이어 붙인 새 드리블을 만든다. 먼저 첫 번째 드리블의 동작을 수행하고 이어서 두 번째 드리블의 동작을 수행한다.

경기 중에는 공 터치를 잊기 쉬우므로, 바이테시가 최종적으로 수행하는 드리블은 계획한 드리블의 비어 있지 않은 부분 수열이다. 즉 계획한 문자열에서 일부 문자(하나도 지우지 않아도 되지만 전부 지울 수는 없다)를 지운 결과이며, 남은 문자의 순서는 바뀌지 않는다.

최종 드리블이 환상적일 수도 있고, 그러면 바이테시는 매우 기뻐한다. 새 목록의 각 드리블에 대해, 그가 실수로 수행할 수 있는 환상적인 드리블이 몇 가지인지 알고 싶다. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구하면 된다.

주의: 바이테시가 관심을 갖는 것은 원래 드리블의 부분 수열로 얻을 수 있는 서로 다른 환상적인 드리블의 개수이며, 원래 드리블에서 문자를 지우는 방법의 수가 아니다.

첫 줄에 자연수 $n$ ($1 \le n \le 600$)이 주어진다. 바이테시가 준비한 드리블의 개수이다. 이어지는 $n$개의 줄에는 각각 비어 있지 않은 'L'과 'P'로 이루어진 문자열이 한 줄에 하나씩 주어진다. 어떤 문자열도 길이가 600을 넘지 않는다.

$n$개의 줄을 출력한다. $i$번째 줄에는 정확히 $n$개의 정수를 출력하며, $j$번째 정수는 원래 목록의 $i$번째 드리블과 $j$번째 드리블을 이어 붙인 드리블을 시도할 때 수행될 수 있는 환상적인 드리블의 개수를 $10^9 + 7$로 나눈 나머지이다.

예시 설명: 셋째 드리블과 넷째 드리블을 이어 붙인 경우를 보자. 이 드리블은 'LLPP'이며, 환상적인 부분 수열이 2개 있다.

• 'LP': 'LLPP'의 부분 수열로 4가지 방법으로 고를 수 있지만, 결과에는 한 번만 센다.
• 'LLPP' 자체.

둘째 드리블과 첫째 드리블을 이어 붙인 경우도 보자. 이 드리블은 'PPLPLLPLPP'이며, 환상적인 부분 수열이 8개 있다: 'LP', 'LLPP', 'LPLP', 'LLLPPP', 'LPLLPP', 'LPLPLP', 'LLPLPP', 'LPLLPLPP'.