#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
static const unsigned MODVAL = 1000000009;
class Mountains { public:
int countPlacements(vector <int> heights, vector <string> visibility)
{
int W = visibility[0].size();
int N = visibility.size();
memo.resize(N);
vector<int> view(W, 0);
return rec(W, view, heights.size()-1, heights, visibility);
}
vector< map<vector<int>,int> > memo;
int rec(int W, const vector<int>& view, int i, vector<int>& H, const vector<string>& V)
{
if(i < 0)
return 1;
if(memo[i].count(view))
return memo[i][view];
int mustL=0, mustR=W-1;
int mustNotL=W, mustNotR=-1;
for(int x=0; x<W; ++x)
{
int LLL = x - (H[i]-view[x]-1);
int RRR = x + (H[i]-view[x]-1);
if(V[i][x] == 'X') {
if( H[i] <= view[x] )
return 0;
mustL = max(mustL, LLL);
mustR = min(mustR, RRR);
} else {
// if( H[i] > view[x] ) {
// mustNotL = min(mustNotL, LLL);
// mustNotR = max(mustNotR, RRR);
// }
}
}
LL result = 0;
for(int c=mustL; c<=mustR; ++c) if(c<mustNotL || mustNotR<c)
{
bool good = true;
for(int x=0; x<W && good; ++x) {
int my_h = H[i] - abs(x-c);
if((V[i][x]=='X') != (view[x] < my_h))
good = false;
}
if( good ) {
vector<int> view2(W);
for(int x=0; x<W; ++x) {
int my_h = H[i] - abs(x-c);
view2[x] = max(my_h, view[x]);
}
result += rec(W, view2, i-1, H, V);
}
}
return memo[i][view] = int(result % MODVAL);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, Mountains().countPlacements(heights, visibility));}
int main(){
CASE(0)
int heights_[] = {2, 3, 2};
vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
string visibility_[] = {"------",
"XXXX--",
"---XXX"};
vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
int _ = 4;
END
CASE(1)
int heights_[] = {4, 3, 4};
vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
string visibility_[] = {"XXXXX--------",
"----------XXX",
"----XXXXXXX--"};
vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
int _ = 4;
END
CASE(2)
int heights_[] = {13, 2, 3, 2};
vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
string visibility_[] = {"XXXXXXXXX",
"-XXX-----",
"----XXXXX",
"-----XXX-"};
vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
int _ = 9;
END
CASE(3)
int heights_[] = {8, 2, 9, 3, 10};
vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
string visibility_[] = {"X------",
"-------",
"------X",
"-------",
"XXXXXXX"};
vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
int _ = 98;
END
CASE(4)
int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50};
vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
string visibility_[] = {"-------------------",
"-------------------",
"-------------------",
"-------------------",
"-------------------",
"-------------------",
"-------------------",
"------------XXXXXXX",
"XXXXXXX------------",
"XXXXXXXXXXXXXXXXXXX"}
;
vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
int _ = 973726691;
END
CASE(5)
int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50};
vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
string visibility_[] = {"-------------------------------------------------",
"-------------------------------------------------",
"-------------------------------------------------",
"-------------------------------------------------",
"-------------------------------------------------",
"-------------------------------------------------",
"-------------------------------------------------",
"------------XXXXXXX------------------------------",
"XXXXXXX------------------------------------------",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
;
vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
int _ = -1;
END
}
// END CUT HERE