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.
POINTS: 100
PROBLEM NAME: coincombinations
INPUT FORMAT:
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).
INPUT DETAILS:
Every coin has a unique value. The values of the coins might not necessarily be less
than the value v.
SAMPLE INPUT:
3 4
1
2
3
OUTPUT FORMAT:
Line 1: A single integer which is the number of ways that the set of coins can make the
given value, mod 13371337.
OUTPUT:
4
OUTPUT DETAILS:
4 can be made in exactly four ways with the given coins:
(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3).