import java.math.BigInteger;
public class VerySmoothDecompositions
{
public int solve(String[] digits)
{
// �Ƃ肠����BigInteger�ɂ���
String str = "";
for(String s : digits) str += s;
return solve(new BigInteger(str));
}
int solve(BigInteger v)
{
// �Ƃ肠�������ʂɑf������������
int[] ps = {2,3,5,7,11,13};
int[] fs = {0,0,0,0, 0, 0};
for(int i=0; i<ps.length; ++i)
for(BigInteger p=BigInteger.valueOf(ps[i]); v.remainder(p).equals(BigInteger.ZERO); v=v.divide(p))
fs[i]++;
if( !v.equals(BigInteger.ONE) )
return 0; // 17�ȏ�̑f�������������疳��
return solve(fs[0], fs[1], fs[2], fs[3]); // 11 �� 13 �͂��̂܂g�������Ȃ��̂Ŗ���
}
// �������炪�{��
int solve(int p2, int p3, int p5, int p7)
{
// dp23[a][b] = �u2��a�A3��b�A����Ƃ��ɉ��ʂ���邩�v
int P2 = p2+1;
int P3 = p3+1;
int[] dp23 = new int[P2*P3]; dp23[0] = 1; // 0��0�Ȃ�1�ʂ�
{
// - {2}�����\���������l�����ꍇ�̐�
// - {2,4}�����\���������l�����ꍇ�̐�
// - ...
// - {2,4,8,16,3,9,6,12} �����\�����l�����S���̏ꍇ�̐�
// ���A�\���X�V���Ȃ��珇�ɋ��߂Ă���
int[] k2 = {1,2,3,4,0,0,1,2};
int[] k3 = {0,0,0,0,1,2,1,1};
for(int i=0; i<k2.length; ++i)
// ��Ƃ��� {2,4,8,16,3,9} --> {2,4,8,16,3,9,6} �̍X�V���l����
for(int a2=k2[i]; a2<=p2; ++a2)
for(int a3=k3[i]; a3<=p3; ++a3) {
// �u2��a�A3��b����Ƃ��� {2,4,8,16,3,9,6} �̍����p�^�[�����v
// = �u2��a�A3��b����Ƃ��� {2,4,8,16,3,9} �̍����p�^�[�����v
// + �u2��a-1�A3��b-1����Ƃ��� {2,4,8,16,3,9,6} �̍����p�^�[�����v�v
dp23[a2*P3+a3] += dp23[(a2-k2[i])*P3+(a3-k3[i])];
dp23[a2*P3+a3] %= MODVAL;
}
}
// ����� 14 �����ꍇ�̐��𐔂���
int[] dp237 = dp23;
{
// 7�������ɂ���Ƃ����
// �u2��a�A3��b����Ƃ��� {2,4,8,16,3,9,6,12,14} �̍����p�^�[�����v
// = �u2��a�A3��b����Ƃ��� {2,4,8,16,3,9,6,12} �̍����p�^�[�����v
// + �u2��a-1�A3��b����Ƃ��� {2,4,8,16,3,9,6,12,14} �̍����p�^�[�����v�v
// ����...
for(int a2=1; a2<=p2; ++a2)
for(int a3=0; a3<=p3; ++a3) {
dp237[a2*P3+a3] += dp237[(a2-1)*P3+a3];
dp237[a2*P3+a3] %= MODVAL;
}
// 7��p7�����Ȃ��̂ŁA
// �u2��a�A3��b�A7����������Ƃ��� {2,4,8,16,3,9,6,12,14} �̍����p�^�[�����v
// = �u2��a�A3��b�A7����������Ƃ��� {2,4,8,16,3,9,6,12,14} �̍����p�^�[�����v
// - �u2��a-p7-1�A3��b�A7����������Ƃ��� {2,4,8,16,3,9,6,12,14} �̍����p�^�[�����v
// ����
for(int a2=p2; a2-p7-1>=0; --a2)
for(int a3=0; a3<=p3; ++a3) {
dp237[a2*P3+a3] += MODVAL - dp237[(a2-p7-1)*P3+a3];
dp237[a2*P3+a3] %= MODVAL;
}
}
// 10�̌���15�̌��͑S�T��
int sum = 0;
for(int n10=0; n10<=p2 && n10<=p5; ++n10)
for(int n15=0; n15<=p3 && n10+n15<=p5; ++n15) {
sum += dp237[(p2-n10)*P3+(p3-n15)];
sum %= MODVAL;
}
return sum;
}
static final int MODVAL = 1000000009;
}