Josephine was working one day at her money exchange booth when a customer walked up to her.
“Can you take these coins and give the same value to me in as many different ways as possible?”
Being quite blur and stupid, Josephine replied, “Isn’t there only one way?”
“No, there are definitely more ways to do it than one.”
Write a program to prove to Josephine that there is more than one way to make a value
with a set amount of coins.
Given n (1 ≤ n ≤ 50) coins, each of value n(i) (1 ≤ n(i) ≤ 10,000) and a
value v (1 ≤ v ≤ 10,000), calculate how many different ways you can make the
value v with the coins given, mod 13371337.
PROBLEM NAME: coincombinations
Line 1: The first line contains two integers, n and v, separated by a space.
Line 2...n: Each line contains one integer each, with the (i + 1)th line representing
the value of coin n(i).
Every coin has a unique value. The values of the coins might not necessarily be less
than the value v.
Line 1: A single integer which is the number of ways that the set of coins can make the
given value, mod 13371337.
4 can be made in exactly four ways with the given coins:
(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3).