coincombinations


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).


Submitting to 'coincombinations'


You're not logged in! Click here to login


Submitting to 'coincombinations'


You're not logged in! Click here to login


Submitting .cpp to 'coincombinations'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Classic Problem

Subtask Score
1 100
2 0