#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 int MODVAL = 1000000007;
struct mint
{
int val;
mint():val(0){}
mint(int x):val(x%MODVAL) {}
mint(size_t x):val(x%MODVAL) {}
mint(LL x):val(x%MODVAL) {}
};
mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
mint operator+(mint x, mint y) { return x+=y; }
mint operator-(mint x, mint y) { return x-=y; }
mint operator*(mint x, mint y) { return x*=y; }
mint operator/(mint x, mint y) { return x/=y; }
vector<mint> FAC_(1,1);
mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed.
mint C(LL n, LL k) {
while( CP_.size() <= n ) {
int nn = CP_.size();
CP_.push_back(vector<mint>(nn+1,1));
for(int kk=1; kk<nn; ++kk)
CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
}
return k<0 || n<k ? 0 : CP_[n][k];
}
template<typename T>
struct DP3
{
int N1, N2, N3;
vector<T> data;
DP3(int N1, int N2, int N3, const T& t = T())
: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
T& operator()(int i1, int i2, int i3)
{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
void swap(DP3& rhs)
{ data.swap(rhs.data); }
};
class ElevenMultiples { public:
// (10^p)%11
int rem11(int p)
{
return p%2==0 ? 1 : 10;
}
int countMultiples(vector <string> pieces)
{
vector<int> es, os;
for(int i=0; i<pieces.size(); ++i) {
int r = 0;
for(int k=0; k<pieces[i].size(); ++k)
r = (r + (pieces[i][k]-'0')*rem11(k)) % 11;
(pieces.size()%2==0 ? es : os).push_back(r);
}
return solve(es, os).val;
}
mint solve(const vector<int>& es, const vector<int>& os)
{
DP3<mint> dpE(es.size(), 11, es.size()+1);
int rE = accumulate(es.begin(), es.end(), 0) % 11;
for(int i=0; i<es.size(); ++i)
for(int r=0; r<11; ++r)
for(int n=0; n<=es.size(); ++n)
{
int v = es[i];
if(i==0) {
if(r==0 && n==0 || r==v && n==1)
dpE(i,r,n) = 1;
} else {
if(n>0)
dpE(i,r,n) = dpE(i-1,r,n) + dpE(i-1, (r-v+11)%11, n-1);
else
dpE(i,r,n) = dpE(i-1,r,n);
}
}
DP3<mint> dpO(os.size(), 11, os.size()+1);
int rO = accumulate(os.begin(), os.end(), 0) % 11;
for(int i=0; i<os.size(); ++i)
for(int r=0; r<11; ++r)
for(int n=0; n<=os.size(); ++n)
{
int v = os[i];
if(i==0) {
if(r==0 && n==0 || r==v && n==1)
dpO(i,r,n) = 1;
} else {
if(n>0)
dpO(i,r,n) = dpO(i-1,r,n) + dpO(i-1, (r-v+11)%11, n-1);
else
dpO(i,r,n) = dpO(i-1,r,n);
}
}
mint total = 0;
for(int re=0; re<11; ++re)
for(int ne=0; ne<=es.size(); ++ne)
for(int ro=0; ro<11; ++ro)
for(int no=0; no<=os.size(); ++no)
{
int re2 = (rE - re + 11)*10%11;
int ne2 = es.size() - ne;
int ro2 = (rO - ro + 11)*10%11;
int no2 = os.size() - no;
if((re + re2 + ro + ro2)%11 == 0)
if( ne2+no2==0 || no>0 )
if(no==no2 || no==no2+1) {
mint choice = (es.empty() ? re==0?1:0 : dpE(es.size()-1, re, ne))
* (os.empty() ? ro==0?1:0 : dpO(os.size()-1, ro, no));
total += choice * cnt(ne, ne2, no, no2);
}
}
return total;
}
mint cnt(int ne, int ne2, int no, int no2)
{
mint x = FAC(no) * FAC(no2);
int nec = (no==no2 ? no+1 : no);
int ne2c = no;
return x * dist(nec, ne) * dist(ne2c, ne2);
}
mint dist(int n, int k)
{
return FAC(n) * C(n+k-1, k-1);
}
};
// 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(_, ElevenMultiples().countMultiples(pieces));}
int main(){
CASE(0)
string pieces_[] = {"58", "2012", "123"};
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = 2;
END
CASE(1)
string pieces_[] = {"1", "1111", "1", "11"};
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = 24;
END
CASE(2)
string pieces_[] = {"43925486943738659795389387498953274"};
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = 1;
END
CASE(3)
string pieces_[] = {"983", "4654", "98", "3269", "861", "30981"};
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = 96;
END
CASE(4)
string pieces_[] = {"193", "8819", "40676", "97625892", "5719", "45515667", "32598836", "70559374", "38756", "724",
"93391", "942068", "506", "901150", "874", "895567", "7560480", "7427691", "799450", "85127"};
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = 537147821;
END
CASE(5)
string pieces_[] = {"687045939630", "997856158148599044", "2014910234712225061", "9658113323175370226", "1584118137",
"67925153345598920", "6960366756", "863413844386808834", "799302243562410012", "44481835751",
"8004606814733183", "19623906615609", "23859998326058162", "461385591582", "9261878982390119",
"1569373294276", "318106951168934", "65389049931", "12791173342", "507877942026",
"3947173045690", "472425746178910", "524552931853595", "40771812249667850232", "563988469071932",
"28147819070", "797007158858587", "5716177008624223", "387565700495309324", "4716621063133318"}
;
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = 814880650;
END
/*
CASE(6)
string pieces_[] = ;
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = ;
END
CASE(7)
string pieces_[] = ;
vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
int _ = ;
END
*/
}
// END CUT HERE