B.cpp

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll MOD = 1e9 + 9;
ll d[10];

int main()
{
	ll n = 0, i, j, F = 1, f;
	char ch;

	while(cin>>ch)
	{
		if(ch >= '0' && ch <= '9')
		{
			n++;
			d[ch-'0']++;
		}
	}

	for(i = 2; i <= n; i++)
	{
		F *= i;
		F %= MOD;
	}


	for(i = 0; i < 10; i++)
	{
		f = 1;
		for(j = 2; j <= d[i]; j++)
		{
			f *= j; f %= MOD;
		}

		F /= f;
	}

	cout<<F<<endl;

	return 0;
}