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
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <iostream>
using namespace std;
using ll=long long;
const int C=605, M=1000000007;

string half_dribble[C];
ll tmp_dribble[C][C];
ll right_sided_L[C][C], right_sided_P[C][C];
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int n;
	cin >> n;
	for (int i=0; i<n; i++) cin >> half_dribble[i];

	// wzynacz prawość -> 2 tablice
	for (int i=0; i<n; i++){
		int ln = half_dribble[i].size();
		tmp_dribble[ln][0] = 1;

		for (int point = ln-1; point >= 0; point--){
			int antipoint = ln-point;
			char element = half_dribble[i][point];
			for (int next_point = point+1; next_point <= ln; next_point++){
				char next_element = '0';
				if (next_point != ln)  next_element = half_dribble[i][next_point];

				for (int height = 0; height <= antipoint+1; height++){
					if (element == 'P' && height > 0) tmp_dribble[point][height] = (tmp_dribble[point][height] + tmp_dribble[next_point][height-1])%M;
					else if (element == 'L') tmp_dribble[point][height] = (tmp_dribble[point][height] + tmp_dribble[next_point][height+1])%M;
				}

				if (element == next_element) break;
			}
		}

		
		for (int point=0; point<ln; point++){
			char element = half_dribble[i][point];
			for (int height = 0; height <= ln; height++){
				if (element == 'L') right_sided_L[i][height] = (right_sided_L[i][height] + tmp_dribble[point][height])%M;
				else right_sided_P[i][height] = (right_sided_P[i][height] + tmp_dribble[point][height])%M;
			}
		}

		for (int point = 0; point <= ln; point++){
			for (int height = 0; height <= ln; height++) tmp_dribble[point][height] = 0;
		}
	}

	for (int i=0; i<n; i++){
		int ln = half_dribble[i].size();
		tmp_dribble[0][0] = 1;

		for (int point = 1; point <= ln; point++){
			char element = half_dribble[i][point-1];

			for (int next_point = point-1; next_point >= 0; next_point--){
				char next_element = '0';
			        if (next_point != 0) next_element = half_dribble[i][next_point-1];

				for (int height = 0; height <= point+1; height++){
					if (element == 'L' && height > 0) tmp_dribble[point][height] = (tmp_dribble[point][height] + tmp_dribble[next_point][height-1])%M;
					else if (element == 'P') tmp_dribble[point][height] = (tmp_dribble[point][height] + tmp_dribble[next_point][height+1])%M;
				}

				if (element == next_element) break;
			}
		}


		ll start_res = 0;
		for (int point = 1; point <= ln; point++) start_res += tmp_dribble[point][0];
		for (int other_dribble = 0; other_dribble < n; other_dribble++){
			ll res = 0;
			for (int point = ln; point >= 0; point--){
				if (point == ln) {
					for (int height = 0; height <= ln; height++) res = (res + (right_sided_P[other_dribble][height] + right_sided_L[other_dribble][height])*tmp_dribble[point][height])%M;
				}
				else if (half_dribble[i][ln-1] == 'L'){
					for (int height = 0; height <= ln; height++) res = (res + right_sided_P[other_dribble][height]*tmp_dribble[point][height])%M;
				}
				else{
					for (int height = 0; height <= ln; height++){
					       	res = (res + right_sided_L[other_dribble][height]*tmp_dribble[point][height])%M;
					}
				}
				if (point != ln && point > 0 && half_dribble[i][point-1] != half_dribble[i][ln-1]) break;
			}
			std::cout << (start_res + res)%M << " ";
		}
		std::cout <<std::endl;

		for (int point = 0; point <= ln; point++){
			for (int height = 0; height <= ln; height++) tmp_dribble[point][height] = 0;
		}
	}

return 0;}