#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main(int argc, char *argv[])
{
	const int denominations[] = { 1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
	const int lenDenominations = sizeof(denominations)/sizeof(denominations[0]);
	const int target = 9000000;

	MP_INT (*table)[lenDenominations] = malloc(sizeof(MP_INT)*(target+1)*lenDenominations);
	for (int i = 0; i < lenDenominations; i++)
		mpz_init_set_si(&table[target][i], 1);

	for (int sumSoFar = target-1; sumSoFar >= 0; sumSoFar--)
	{
		for (int minDenomination = lenDenominations-1; minDenomination >= 0; minDenomination--)
		{
			mpz_init_set_si(&table[sumSoFar][minDenomination], 0);
			for (int i = minDenomination; i < lenDenominations; i++)
			{
				int newSumSoFar = sumSoFar + denominations[i];
				if (newSumSoFar <= target)
					mpz_add(&table[sumSoFar][minDenomination], &table[sumSoFar][minDenomination], &table[newSumSoFar][i]);
			}
		}
	}

	mpz_out_str(stdout, 10, &table[0][0]);
	fputc('\n', stdout);

	return 0;
}