In a country called STI Countries (STI stands for Super Toxicity Inc.), there is one day dedicated for the people to do everything they want. This day is called FREE DAY. Of course they must keep their activites not to violate the law. For example, everything that lead to criminality is forbidden because it violates the law.

The president of STI Countries is very excited to FREE DAY. For him, being a president made him as the busiest man in the world, so holiday is almost impossible for him, even Sunday. But, FREE DAY gives him a chance to feel freedom from all of his duty as the president.

For this FREE DAY, president and his family want to make a party. This party is called Cake Walk Party. As it namesake, this party will have relation with cakes. So, president needs a talented baker for the best cakes he want. Then, the president called Brembo, the best baker in the country. Called by the president, the baker will make sure the cakes he made would impress the president. The president will order T cakes, with every of them is different type. To make a cake, Brembo needs M package of ingredients. The type of a cake will be represented by a number that is N. After doing some experiments, he finds a good formula to make the ingredients of cake with type N. He called this F(N).

He writes the fomula F(N) as F(N) = F(1) + F(2) + F(3) + F(4) + ..... + F(N-1) with F(1) = M.

Normally, the cake with type N, will be priced C(N) in dollars, where C(N) = M + N + F(N). But, because today is a special day plus he is doing job for the president, the way of pricing a cake is different than before. He makes rules as the following :

• From C(N), find all special factor of C(N).
• Because Brembo is not good at explaining, Brembo defines special factor of a number with examples. For example 24, the special factors are 2³ and 3. For 15, special factors are 3 and 5. And so on.

• Then, the price of the cake will be taken from factor with the highest value. So, from the example above, 24 will be priced 3 instead.
• So far, 15 will be priced 5 instead.

Considering the results of C(N) can be very large, he does C(N) mod 1000000007 for every C(N) he calculates, then factorize it. As the assisstant of Brembo, you need to calculate the total cost that president must pay for the T cakes he orders. Because this task will be exhausting, you build a program to make the calculation faster.

Input

The first line of input consist of two integers, T and M separated by space. T represents the number of cake that The President will order and M represents the package of ingredients. (1 <= T <= 100 and 1 <= M <= 1000000)

The next T lines, contains one integer Ni, representing the type number of cakes. ( 1 <= N <= 1000000)

Output

Print the total cost that The President must pay using the following format : "The President needs to pay (total) dollar(s)" without quotes.

Please, take a look to example.

Example

Input:
3 11
2
3
4

Output:
The President needs to pay 65 dollar(s)