infoarena

//salvam divizorii lui b
for(i=1;i<=k;i++)
	if(!(k%i)) //am asit un divizor al lui k
		d[++nr]=i; //salvam divizorul :P

//prelucram matricea c[][]...
for(i=1;i<=nr;i++)
	for(j=1;j<=nr&&d[j]<=9;j++)
		c[i][j]=d[i]/d[j];

//initializam pt a=1
for(i=1;i<=nr&&d[i]<=9;i++)
	m[1][d[i]]=1; //pt a=1, exista o singura posibilitate pt divizorii lui b mai mici ca 10

for(i=2;i<=n;i++) //calculam pentru fiecare a in parte
	{
	for(j=1;j<=nr;j++) //luam pe rand toate produsele care sunt divizibile cu k
		{
		m[i%2][d[j]]=0; //golim...am ajuns pt prima data pt i-ul asta :P
		for(p=1;p<=nr&&d[p]<=9;p++)
			if(!(d[j]%d[p])) // al j-lea divizor al lui k, este multiplu al celui de-al p-lea divizor
				m[i%2][d[j]]=m[i%2][d[j]]+m[(i-1)%2][c[j][p]]; //la psoibilitatiile gasite pana acum, se adauga si posibilitatile pt al p-lea divizor
		}
	if(i%1000) //din 1000 in 1000...facem modulo :P....ca sa economism timp :))
		for(j=1;j<=nr;j++)
			m[i%2][d[j]]%=modulo;
	}

//afisem numarul e posibilitati
printf("%d",m[n%2][k]%modulo);

cat = X / MOD;
rez = X - MOD * cat;