Mary's Partitions

(file name: mary.pl)

Mary schedules the room reservations and wants to use partitions for the various workshops. A partition of an integer N is a set of positive integers which sum to N, typically written in descending order. For example:

10 = 4+3+2+1

A partition is M-ary if each term in the partition is a power of M. For example, the 3-ary partitions of 9 are:

9
3+3+3
3+3+1+1+1
3+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1

Write a program to find the number of M-ary partitions of an integer N.

Input format

An input file for LP systems contains the following fact for the form mary(M,N) containing the base of powers, M, (3 <= M <= 100) and the integer, N, (3 <= N <= 10000), for which the number of M-ary partitions is to be found..

Output format

The output should contain exactly one fact of the form solution(S), where S is the number of M-ary partitions of an integer N.

Examples:
mary(3, 9). solution(5).
mary(3, 47). solution(63).
mary(5, 123). solution(75).
mary(7, 4321). solution(144236).