There are some kawaii lolita dresses going to be on sale, but Umiki don't have enough money. So she has to do some part-time jobs to earn some money to buy some of them. We assume that each lolita dress has the same value and each time she doing a part-time job can earn the same money that can be paid to buy exactly one dress. The part time job and lolita dress go chronologically, so you will get a sequence S only include 0 and 1 Umiki doesn't have enough energy to do all the part-time job and she doesn't want any money left in the end, so she must select some of them to do or to buy. And also Umiki likes buy!
There are some kawaii lolita dresses going to be on sale, but Umiki don't have enough money. So she has to do some part-time jobs to earn some money to buy some of them. We assume that each lolita dress has the same value and each time she doing a part-time job can earn the same money that can be paid to buy exactly one dress. The part time job and lolita dress go chronologically, so you will get a sequence S only include 0 and 1 (0 means you can get a part time job that day,1 means a lolita dress will be on sale that day, and you won't get that dress again if you don't buy it exactly that day) Umiki doesn't have enough energy to do all the part-time job and she doesn't want any money left in the end, so she must select some of them to do or to buy. And also Umiki likes buy! buy!! b-----u----y!!! So, she wants to get enough money and then go buying without any work, which means she wants to only work at the first half of time and only buying at the last half of time. Now Umiki wants to find the number of methods to work and buy such that they are in line with her wishes (which means the first half of the subsequences are all 0 and the last half of the subsequences are all 1). Note that a subsequence of S is a string that can be obtained from S by deleting some of its elements. Two subsequences are considered distinct if different sets of elements are deleted. Because the answer can be very large and Umiki can't count huge numbers, she asks you to find the answer modulo 109 + 710^9 + 7109 + 7.
