Reg2013-E.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define dprint(v) cerr << #v"=" << v << endl
#define forr(i, a, b) for(int i=(a); i<(b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforn(i, n) for(int i=(n)-1; i>=0; i--)
#define forall(it,v) for(typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
typedef long long ll;
#define ii pair<int, int>
#define mkp make_pair
#define fst first
#define snd second
#define pb push_back
#include <sstream>
#define M 1000000007
#define A 20
#define B 152
#define C 11
#define N 70
ll ways[N][N];
ll dp[A][B][C];
int t,n;
string s;	
ll cant[10], scant[10], len, len1, len2, sum;
	
ll w (ll i, ll j)
{
	if (i > 60) return 0;
	if (i < 0) return 0;
	if (j < 0) return 0;
	if (i < j) return 0;
	return ways[i][j];
}	
	
ll mo (ll v, ll m)
{
	return ((v % m) + m) %m;	
}	

int main() {
#ifndef ONLINE_JUDGE
	freopen("e.in", "r", stdin);
#endif
	forn(i,N){
		ways[i][0] = 1; ways[i][i] = 1;
		forr(j,1,i)
			ways[i][j] = (ways[i-1][j] + ways[i-1][j-1]) % M;	
	}
	while (cin >> s){
		len = s.length();
		len1 = (len + 1) /2; len2 = len / 2; 
		sum = 0;
		
		forn (i, 10)
			cant[i] = 0;
			
		forn (i, len){
			cant[s[i]-'0']++;
			sum += s[i] - '0';
		}
		scant[0] = cant[0];
		forr (i,1, 10)
			scant[i] = scant[i-1] + cant[i]; 
		
		forn (i, A) forn (j, B) forn (k, C)
			dp[i][j][k] = 0;
		dp[0][0][0] = 1;
		
		
		forn (i,10) forn (j, 51) forn (k, C) forn (it, (int)cant[i]+1)
		{
			if (i != 0)
				dp[i+1][j+it][(k+i*it)%11] += (((dp[i][j][k] * w(len1-j,it)) % M) * w (len2-scant[i-1]+j, (int)cant[i]- it))% M;			
			else 
				dp[i+1][j+it][(k+i*it)%11] += (((dp[i][j][k] * w(len1-j-1,it)) % M) * w (len2+j, (int)cant[i]- it))% M;
			dp[i+1][j+it][(k+i*it)%11] %= M;
		}
		
		sum %= 11;
		if (sum % 2)
			sum = (sum + 11)/2;
		else
			sum /= 2;
			
		cout << dp[10][len1][sum] << endl;

		
			
			
		}

	
  return 0;

}