## 24 hour archive: Problem

###
** 3573
- Buying Candies III** ** 3573 - Buying Candies III** ** 3573 - Buying Candies III**

#### Description

John would like to go the shop for some candies. The local grocery has exactly N types of candies and almost an infinite amount of candies of each type. These candies have a cylindrical shape, each has a radius of 10 units and a given length. The weight of the candies is equal to its length.

John has a knapsack that can carry M units of weight. On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.

The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.

He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

John has a knapsack that can carry M units of weight. On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.

The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.

He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

John would like to go the shop for some candies. The local grocery has exactly N types of candies and almost an infinite amount of candies of each type. These candies have a cylindrical shape, each has a radius of 10 units and a given length. The weight of the candies is equal to its length.

John has a knapsack that can carry M units of weight. On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.

The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.

He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

John has a knapsack that can carry M units of weight. On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.

The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.

He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

John would like to go the shop for some candies. The local grocery has exactly N types of candies and almost an infinite amount of candies of each type. These candies have a cylindrical shape, each has a radius of 10 units and a given length. The weight of the candies is equal to its length.

John has a knapsack that can carry M units of weight. On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.

The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.

He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

John has a knapsack that can carry M units of weight. On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.

The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.

He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

#### Input specification

The first line contains three integers N, M and K denoting the number of
different candies in the local grocery, the weight that the knapsack
can carry and the length of the hole.

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

The first line contains three integers N, M and K denoting the number of
different candies in the local grocery, the weight that the knapsack
can carry and the length of the hole.

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

The first line contains three integers N, M and K denoting the number of
different candies in the local grocery, the weight that the knapsack
can carry and the length of the hole.

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

#### Output specification

Print the number of different ways that John can buy the candies and its total weight is exactly equal to M.

As the result is a very large value, you must modulate 1000000007.

As the result is a very large value, you must modulate 1000000007.

Print the number of different ways that John can buy the candies and its total weight is exactly equal to M.

As the result is a very large value, you must modulate 1000000007.

As the result is a very large value, you must modulate 1000000007.

The following N lines contains one integer Ai denoting the weight of each candy.

(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

#### Sample input

`3 10 0`

4

3

7

#### Sample output

`2`

#### Hint(s)

Input:

3 10 4

4

3

7

Ouput

1

in the first example we can buy the following convination

3 3 4

3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3

the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall

3 10 4

4

3

7

Ouput

1

in the first example we can buy the following convination

3 3 4

3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3

the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall

Input:

3 10 4

4

3

7

Ouput

1

in the first example we can buy the following convination

3 3 4

3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3

the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall

3 10 4

4

3

7

Ouput

1

in the first example we can buy the following convination

3 3 4

3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3

the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall

Input:

3 10 4

4

3

7

Ouput

1

in the first example we can buy the following convination

3 3 4

3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3

the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall

3 10 4

4

3

7

Ouput

1

in the first example we can buy the following convination

3 3 4

3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3

the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall