numere19

/// numarul de numere de n cifre si prod cifrelor k
/// complexitate : O(n * nrdiv(k))
#include <cstdio>
#include <cstring>
#define MAX 9001
#define CONST 9973
#define INPUT "numere19.in"
#define OUTPUT "numere19.out"
using namespace std;
int N, K, ndiv;
int nrpos1[MAX], nrpos2[MAX], diviz[MAX];
FILE *f = fopen(INPUT, "r");
FILE *g = fopen(OUTPUT, "w");

int prim(int nr)
{
	if(nr %2 == 0) return 0;
	int i;
	for(i = 3; i*i <= nr; i += 2)
		if(nr%i == 0) return 0;
	return 1;
}

int main()
{
	fscanf(f, "%d %d", &N, &K);
	int ok = 1, i, j, p;
	for(i = 11; i <= K && ok; ++i)
		if(K % i == 0 && prim(i)) ok = 0;
	for(i = 1; i <= K; ++i)
		if(K%i == 0) diviz[++ndiv] = i;
	if(ok)
	{
		for(i = 1; i <= ndiv && diviz[i] <= 9 ; ++i)
			nrpos1[diviz[i]] = 1;
		for(i = 2; i <= N; ++i)
		{
			for(j = 1; j <= ndiv; ++j)
				nrpos2[diviz[j]] = 0;
			for(j = 1; j <= ndiv; ++j)
			{
				for(p = 1; p <= ndiv && diviz[p] <= 9; ++p)
					if(diviz[j] % diviz[p] == 0)
						nrpos2[diviz[j]] = (nrpos2[diviz[j]] + nrpos1[diviz[j]/diviz[p]]) % CONST;
			}
			for(j = 1;j <= ndiv; ++j)
				nrpos1[diviz[j]] = nrpos2[diviz[j]] % CONST;
		}
		fprintf(g, "%d\n", nrpos1[K]);
	}
	else fprintf(g, "0\n");
	return 0;
}