5749d4c594 2012-07-09        kinaba: #include <iostream>
5749d4c594 2012-07-09        kinaba: #include <sstream>
5749d4c594 2012-07-09        kinaba: #include <iomanip>
5749d4c594 2012-07-09        kinaba: #include <vector>
5749d4c594 2012-07-09        kinaba: #include <string>
5749d4c594 2012-07-09        kinaba: #include <map>
5749d4c594 2012-07-09        kinaba: #include <set>
5749d4c594 2012-07-09        kinaba: #include <algorithm>
5749d4c594 2012-07-09        kinaba: #include <numeric>
5749d4c594 2012-07-09        kinaba: #include <iterator>
5749d4c594 2012-07-09        kinaba: #include <functional>
5749d4c594 2012-07-09        kinaba: #include <complex>
5749d4c594 2012-07-09        kinaba: #include <queue>
5749d4c594 2012-07-09        kinaba: #include <stack>
5749d4c594 2012-07-09        kinaba: #include <cmath>
5749d4c594 2012-07-09        kinaba: #include <cassert>
5749d4c594 2012-07-09        kinaba: using namespace std;
5749d4c594 2012-07-09        kinaba: typedef long long LL;
5749d4c594 2012-07-09        kinaba: typedef long double LD;
5749d4c594 2012-07-09        kinaba: typedef complex<LD> CMP;
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: static const int MODVAL = 1000000007;
5749d4c594 2012-07-09        kinaba: struct mint
5749d4c594 2012-07-09        kinaba: {
5749d4c594 2012-07-09        kinaba: 	int val;
5749d4c594 2012-07-09        kinaba: 	mint():val(0){}
5749d4c594 2012-07-09        kinaba: 	mint(int    x):val(x%MODVAL) {}
5749d4c594 2012-07-09        kinaba: 	mint(size_t x):val(x%MODVAL) {}
5749d4c594 2012-07-09        kinaba: 	mint(LL     x):val(x%MODVAL) {}
5749d4c594 2012-07-09        kinaba: };
5749d4c594 2012-07-09        kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
5749d4c594 2012-07-09        kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
5749d4c594 2012-07-09        kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
5749d4c594 2012-07-09        kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
5749d4c594 2012-07-09        kinaba: mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
5749d4c594 2012-07-09        kinaba: mint operator+(mint x, mint y) { return x+=y; }
5749d4c594 2012-07-09        kinaba: mint operator-(mint x, mint y) { return x-=y; }
5749d4c594 2012-07-09        kinaba: mint operator*(mint x, mint y) { return x*=y; }
5749d4c594 2012-07-09        kinaba: mint operator/(mint x, mint y) { return x/=y; }
5749d4c594 2012-07-09        kinaba: vector<mint> FAC_(1,1);
5749d4c594 2012-07-09        kinaba: mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
5749d4c594 2012-07-09        kinaba: vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed.
5749d4c594 2012-07-09        kinaba: mint C(LL n, LL k) {
5749d4c594 2012-07-09        kinaba: 	while( CP_.size() <= n ) {
5749d4c594 2012-07-09        kinaba: 		int nn = CP_.size();
5749d4c594 2012-07-09        kinaba: 		CP_.push_back(vector<mint>(nn+1,1));
5749d4c594 2012-07-09        kinaba: 		for(int kk=1; kk<nn; ++kk)
5749d4c594 2012-07-09        kinaba: 			CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
5749d4c594 2012-07-09        kinaba: 	}
5749d4c594 2012-07-09        kinaba: 	return k<0 || n<k ? 0 : CP_[n][k];
5749d4c594 2012-07-09        kinaba: }
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: template<typename T>
5749d4c594 2012-07-09        kinaba: struct DP3
5749d4c594 2012-07-09        kinaba: {
5749d4c594 2012-07-09        kinaba: 	int N1, N2, N3;
5749d4c594 2012-07-09        kinaba: 	vector<T> data;
5749d4c594 2012-07-09        kinaba: 	DP3(int N1, int N2, int N3, const T& t = T())
5749d4c594 2012-07-09        kinaba: 		: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
5749d4c594 2012-07-09        kinaba: 	T& operator()(int i1, int i2, int i3)
5749d4c594 2012-07-09        kinaba: 		{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
5749d4c594 2012-07-09        kinaba: 	void swap(DP3& rhs)
5749d4c594 2012-07-09        kinaba: 		{ data.swap(rhs.data); }
5749d4c594 2012-07-09        kinaba: };
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: class ElevenMultiples { public:
5749d4c594 2012-07-09        kinaba: 	// (10^p)%11
5749d4c594 2012-07-09        kinaba: 	int rem11(int p)
5749d4c594 2012-07-09        kinaba: 	{
5749d4c594 2012-07-09        kinaba: 		return p%2==0 ? 1 : 10;
5749d4c594 2012-07-09        kinaba: 	}
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: 	int countMultiples(vector <string> pieces)
5749d4c594 2012-07-09        kinaba: 	{
5749d4c594 2012-07-09        kinaba: 		vector<int> es, os;
5749d4c594 2012-07-09        kinaba: 		for(int i=0; i<pieces.size(); ++i) {
5749d4c594 2012-07-09        kinaba: 			int r = 0;
5749d4c594 2012-07-09        kinaba: 			for(int k=0; k<pieces[i].size(); ++k)
5749d4c594 2012-07-09        kinaba: 				r = (r + (pieces[i][k]-'0')*rem11(k)) % 11;
5749d4c594 2012-07-09        kinaba: 			(pieces.size()%2==0 ? es : os).push_back(r);
5749d4c594 2012-07-09        kinaba: 		}
5749d4c594 2012-07-09        kinaba: 		return solve(es, os).val;
5749d4c594 2012-07-09        kinaba: 	}
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: 	mint solve(const vector<int>& es, const vector<int>& os)
5749d4c594 2012-07-09        kinaba: 	{
5749d4c594 2012-07-09        kinaba: 		DP3<mint> dpE(es.size(), 11, es.size()+1);
5749d4c594 2012-07-09        kinaba: 		int rE = accumulate(es.begin(), es.end(), 0) % 11;
5749d4c594 2012-07-09        kinaba: 		for(int i=0; i<es.size(); ++i)
5749d4c594 2012-07-09        kinaba: 		for(int r=0; r<11; ++r)
5749d4c594 2012-07-09        kinaba: 		for(int n=0; n<=es.size(); ++n)
5749d4c594 2012-07-09        kinaba: 		{
5749d4c594 2012-07-09        kinaba: 			int v = es[i];
5749d4c594 2012-07-09        kinaba: 			if(i==0) {
5749d4c594 2012-07-09        kinaba: 				if(r==0 && n==0 || r==v && n==1)
5749d4c594 2012-07-09        kinaba: 					dpE(i,r,n) = 1;
5749d4c594 2012-07-09        kinaba: 			} else {
5749d4c594 2012-07-09        kinaba: 				if(n>0)
5749d4c594 2012-07-09        kinaba: 					dpE(i,r,n) = dpE(i-1,r,n) + dpE(i-1, (r-v+11)%11, n-1);
5749d4c594 2012-07-09        kinaba: 				else
5749d4c594 2012-07-09        kinaba: 					dpE(i,r,n) = dpE(i-1,r,n);
5749d4c594 2012-07-09        kinaba: 			}
5749d4c594 2012-07-09        kinaba: 		}
5749d4c594 2012-07-09        kinaba: 		DP3<mint> dpO(os.size(), 11, os.size()+1);
5749d4c594 2012-07-09        kinaba: 		int rO = accumulate(os.begin(), os.end(), 0) % 11;
5749d4c594 2012-07-09        kinaba: 		for(int i=0; i<os.size(); ++i)
5749d4c594 2012-07-09        kinaba: 		for(int r=0; r<11; ++r)
5749d4c594 2012-07-09        kinaba: 		for(int n=0; n<=os.size(); ++n)
5749d4c594 2012-07-09        kinaba: 		{
5749d4c594 2012-07-09        kinaba: 			int v = os[i];
5749d4c594 2012-07-09        kinaba: 			if(i==0) {
5749d4c594 2012-07-09        kinaba: 				if(r==0 && n==0 || r==v && n==1)
5749d4c594 2012-07-09        kinaba: 					dpO(i,r,n) = 1;
5749d4c594 2012-07-09        kinaba: 			} else {
5749d4c594 2012-07-09        kinaba: 				if(n>0)
5749d4c594 2012-07-09        kinaba: 					dpO(i,r,n) = dpO(i-1,r,n) + dpO(i-1, (r-v+11)%11, n-1);
5749d4c594 2012-07-09        kinaba: 				else
5749d4c594 2012-07-09        kinaba: 					dpO(i,r,n) = dpO(i-1,r,n);
5749d4c594 2012-07-09        kinaba: 			}
5749d4c594 2012-07-09        kinaba: 		}
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: 		mint total = 0;
5749d4c594 2012-07-09        kinaba: 		for(int re=0; re<11; ++re)
5749d4c594 2012-07-09        kinaba: 		for(int ne=0; ne<=es.size(); ++ne)
5749d4c594 2012-07-09        kinaba: 		for(int ro=0; ro<11; ++ro)
5749d4c594 2012-07-09        kinaba: 		for(int no=0; no<=os.size(); ++no)
5749d4c594 2012-07-09        kinaba: 		{
5749d4c594 2012-07-09        kinaba: 			int re2 = (rE - re + 11)*10%11;
5749d4c594 2012-07-09        kinaba: 			int ne2 = es.size() - ne;
5749d4c594 2012-07-09        kinaba: 			int ro2 = (rO - ro + 11)*10%11;
5749d4c594 2012-07-09        kinaba: 			int no2 = os.size() - no;
5749d4c594 2012-07-09        kinaba: 			if((re + re2 + ro + ro2)%11 == 0)
5749d4c594 2012-07-09        kinaba: 			if( ne2+no2==0 || no>0 )
5749d4c594 2012-07-09        kinaba: 			if(no==no2 || no==no2+1) {
5749d4c594 2012-07-09        kinaba: 				mint choice = (es.empty() ? re==0?1:0 : dpE(es.size()-1, re, ne))
5749d4c594 2012-07-09        kinaba: 					* (os.empty() ? ro==0?1:0 : dpO(os.size()-1, ro, no));
5749d4c594 2012-07-09        kinaba: 				total += choice * cnt(ne, ne2, no, no2);
5749d4c594 2012-07-09        kinaba: 			}
5749d4c594 2012-07-09        kinaba: 		}
5749d4c594 2012-07-09        kinaba: 		return total;
5749d4c594 2012-07-09        kinaba: 	}
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: 	mint cnt(int ne, int ne2, int no, int no2)
5749d4c594 2012-07-09        kinaba: 	{
5749d4c594 2012-07-09        kinaba: 		mint x = FAC(no) * FAC(no2);
5749d4c594 2012-07-09        kinaba: 		int nec = (no==no2 ? no+1 : no);
5749d4c594 2012-07-09        kinaba: 		int ne2c = no;
5749d4c594 2012-07-09        kinaba: 		return x * dist(nec, ne) * dist(ne2c, ne2);
5749d4c594 2012-07-09        kinaba: 	}
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: 	mint dist(int n, int k)
5749d4c594 2012-07-09        kinaba: 	{
5749d4c594 2012-07-09        kinaba: 		return FAC(n) * C(n+k-1, k-1);
5749d4c594 2012-07-09        kinaba: 	}
5749d4c594 2012-07-09        kinaba: };
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: // BEGIN CUT HERE
5749d4c594 2012-07-09        kinaba: #include <ctime>
5749d4c594 2012-07-09        kinaba: double start_time; string timer()
5749d4c594 2012-07-09        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
5749d4c594 2012-07-09        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
5749d4c594 2012-07-09        kinaba:  { os << "{ ";
5749d4c594 2012-07-09        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
5749d4c594 2012-07-09        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
5749d4c594 2012-07-09        kinaba: void verify_case(const int& Expected, const int& Received) {
5749d4c594 2012-07-09        kinaba:  bool ok = (Expected == Received);
5749d4c594 2012-07-09        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
5749d4c594 2012-07-09        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
5749d4c594 2012-07-09        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
5749d4c594 2012-07-09        kinaba: #define END	 verify_case(_, ElevenMultiples().countMultiples(pieces));}
5749d4c594 2012-07-09        kinaba: int main(){
5749d4c594 2012-07-09        kinaba: 
5749d4c594 2012-07-09        kinaba: CASE(0)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = {"58", "2012", "123"};
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = 2;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: CASE(1)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = {"1", "1111", "1", "11"};
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = 24;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: CASE(2)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = {"43925486943738659795389387498953274"};
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = 1;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: CASE(3)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = {"983", "4654", "98", "3269", "861", "30981"};
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = 96;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: CASE(4)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = {"193", "8819", "40676", "97625892", "5719", "45515667", "32598836", "70559374", "38756", "724",
5749d4c594 2012-07-09        kinaba: "93391", "942068", "506", "901150", "874", "895567", "7560480", "7427691", "799450", "85127"};
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = 537147821;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: CASE(5)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = {"687045939630", "997856158148599044", "2014910234712225061", "9658113323175370226", "1584118137",
5749d4c594 2012-07-09        kinaba: "67925153345598920", "6960366756", "863413844386808834", "799302243562410012", "44481835751",
5749d4c594 2012-07-09        kinaba: "8004606814733183", "19623906615609", "23859998326058162", "461385591582", "9261878982390119",
5749d4c594 2012-07-09        kinaba: "1569373294276", "318106951168934", "65389049931", "12791173342", "507877942026",
5749d4c594 2012-07-09        kinaba: "3947173045690", "472425746178910", "524552931853595", "40771812249667850232", "563988469071932",
5749d4c594 2012-07-09        kinaba: "28147819070", "797007158858587", "5716177008624223", "387565700495309324", "4716621063133318"}
5749d4c594 2012-07-09        kinaba: ;
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = 814880650;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: /*
5749d4c594 2012-07-09        kinaba: CASE(6)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = ;
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = ;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: CASE(7)
5749d4c594 2012-07-09        kinaba: 	string pieces_[] = ;
5749d4c594 2012-07-09        kinaba: 	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
5749d4c594 2012-07-09        kinaba: 	int _ = ;
5749d4c594 2012-07-09        kinaba: END
5749d4c594 2012-07-09        kinaba: */
5749d4c594 2012-07-09        kinaba: }
5749d4c594 2012-07-09        kinaba: // END CUT HERE