<reponame>mauromascarenhas/PGC_UFABC
{"output":"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":"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.","level":5,"name":"<NAME>","has_images":false,"description":"<NAME> is a Brazilian folklore legend, with an indigenous origin from Brazil northern region, mainly in the Amazon.\n\n\nAccording to legend, an Indian tapuia from the Amazon region got pregnant by a boto.\n\nTwins were born (a boy and a girl), who were actually snakes. The girl was named <NAME>, and the boy was baptized Norato. \n\n\nThe twins were left on the Tocantins River and grown up alone.\n\n\nSnake Norato was good, he saved who was drowning and helped the boatmen and fishermen in danger. Caninana was the opposite: she attacked people.\n\n\nNorato 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.\n\n\nNorato 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.\n\n\nThe 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.\n\n\nWhat 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.\n\n\nThe 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.\n\n\nIn 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.\n\n\nGiven 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.\n\n\nOne form is considered different from the other if the number of trips from the riverbank to the campfire is different for some soldier.","id":"2937","category":"Mathematics","statistics":{"level":"5 / 10","submissions":9,"solved":1,"ratio":"11.11%"}}