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
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>

using namespace std;

const long long MOD = 1e9 + 7;

void normalL(int k, vector<long long>& v){
	for(int i = k+1; i < 2*k + 1; i++){
		v[i] = (v[i-k] + v[i+1]) % MOD;
	}
}

void normalP(int k, vector<long long>& v){
	v[0] = 0;
	for(int i = k; i >= 1; i--){
		v[i] = (v[i-1] + v[i + k]) % MOD;
	}
}

void reverseL(int k, vector<long long>& v){
	vector<long long> copy(2*k + 2);
	copy[0] = v[0];
	for(int i = 1; i < k+1; i++){
		copy[i] = (v[i] + v[i+k]) % MOD;
	}
	copy[k+1] = 0;
	for(int i = k+2; i < 2*k + 1; i++){
		copy[i] = v[i-1];
	}
	copy[2*k+1] = (v[2*k] + v[2*k + 1]) % MOD;
	for(int i =0; i < 2*k + 2; i++)v[i] = copy[i];
}

void reverseP(int k, vector<long long>& v){
	vector<long long> copy(2*k + 2);
	for(int i = 0; i < k; i++){
		copy[i] = v[i+1];
	}
	copy[k] = 0;
	for(int i = k+1; i < 2*k + 1; i++){
		copy[i] = (v[i-k] + v[i]) % MOD;
	}
	copy[2*k + 1] = v[2*k + 1];
	for(int i= 0; i < 2*k + 2; i++)v[i] = copy[i];
}

long long dotProd(int k, vector<long long>& a, vector<long long>& b){
	long long res = 0;
	for(int i= 0; i < 2*k + 2; i++){
		res += a[i] * b[i];
		res %= MOD;
	}
	return res;
}


string XD(int a){
	if(a == 0){
		return "L";
	}else{
		return "P";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	int n; cin>>n;
	vector<string> v(n);
	for(int i= 0; i < n; i++)cin>>v[i];
	/*for(int i= 0; i < n; i++){
		v[i] = "";
		for(int j= 0; j < 600; j++)v[i] += XD(rand() % 2);
	}*/
	int k = 0;
	for(int i= 0; i < n; i++)k = max(k, (int)v[i].length());
	//cout<<k<<" ";
	vector<long long> normalBeg(2*k + 2, 0);
	normalBeg[2*k + 1] = 1;
	vector<long long> revBeg(2*k + 2, 0);
	revBeg[k] = 1;
	vector<vector<long long>> normal(n, normalBeg);
	vector<vector<long long>> rev(n, revBeg);
	for(int i= 0; i < n; i++){
		for(int j= 0; j < v[i].length(); j++){
			if(v[i][j] == 'L'){
				normalL(k, normal[i]);
			}else{
				normalP(k, normal[i]);
			}
		}
		for(int j= v[i].length() - 1; j >= 0; j--){
			if(v[i][j] == 'L'){
				reverseL(k, rev[i]);
			}else{
				reverseP(k, rev[i]);
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j= 0; j < n; j++){
			cout<<dotProd(k, normal[i], rev[j])<<" ";
		}
		cout<<"\n";
	}
	return 0;
}