Snake Norato
By Francisco Elio Parente Arcos Filho, Universidade do Estado do Amazonas 
Brazil
By Francisco Elio Parente Arcos Filho, Universidade do Estado do Amazonas Brazil
Snake Norato is a Brazilian folklore legend, with an indigenous origin from Brazil northern region, mainly in the Amazon.
According to legend, an Indian tapuia from the Amazon region got pregnant by a boto.
Twins were born (a boy and a girl), who were actually snakes. The girl was named Maria Caninana, and the boy was baptized Norato.
The twins were left on the Tocantins River and grown up alone.
Snake Norato was good, he saved who was drowning and helped the boatmen and fishermen in danger. Caninana was the opposite: she attacked people.
Norato used to visit his mother and attend the city dances, because he loved to dance. In these days he would come out of the water, leave the huge snake skin on the bank, and turn into a man. Late in the evening, he would put on snake skin and return to the river.
Norato wanted to be disenchanted, to become a real man and he gave the recipe to break the enchant to several friends, but none of them had the courage to go to the end. Finally, a soldier was able to disenchant him.
The legend ends by telling that Cobra Norato's skin was burned and that the Honorato boy lived for many years in Pará, where he was loved by all.
What the legend doesn't tell is that the soldier and his battalion companions had to do a huge job to divide the snake's huge skin leather into parts and take it to another place where it would not cause a fire in the Wood.
The length of the leather was divided into varied pieces. The sizes of the pieces were according to the fixed length that each soldier carried in a trip to the fire.
In addition, the battalion was such that a stronger soldier could always take, in a single trip, exactly multiple times the size that a weaker soldier could, but no fraction more or less. And there was a soldier who always carried pieces of size one.
Given the length of the snake and the sizes each soldier can carry, determine the number of ways that the soldiers may have taken the snake's leather up to the fire.
One form is considered different from the other if the number of trips from the riverbank to the campfire is different for some soldier.
The first line of input contains N (1 ≤ N ≤ 40) being the quantity of soldiers. The next line contains N distincts integers Ti (1 ≤ Ti ≤ 1018) representing the size in meters of the piece that each soldier carries per trip. The third line of a test case contains an integer C (1 ≤ C ≤ 1018) representing the snake's length in meters.
The output consists of one line containing an integer representing the number of ways to carry Snake Norato's leather from the margin to the burning area. Since this number can be very large, print only the rest of your division by 109+7.
| Input Samples | Output Samples |
|
3 6 1 3 10 |
6 |
|
4 1 5 10 20 20 |
10 |
|
2 4 1 3 |
1 |