Siddharth spends all day and night setting TSSOJ problems.
He has mastered ~S~ different problem-writing techniques. Initially, his skill in every technique is ~1~.
Siddharth plans to write exactly ~N~ problems. For each problem, he may choose any one of the ~S~ techniques to use. However, he gets bored easily, so he will use technique ~i~ at most ~K_i~ times.
The quality of a problem is equal to Siddharth’s current skill in the chosen technique. After writing the problem, his skill in that technique doubles. His skills in all other techniques remain unchanged.
Siddharth wants to maximize the total quality of the ~N~ problems he writes.
Given ~S~, ~N~, and the limits ~K_1, K_2, \dots, K_S~, determine the maximum possible total quality. Maximize the true total first, then output it modulo ~10^9+7~.

Input

The first line contains integer ~S~ ~(1\le S \le 2 \cdot 10^5)~, representing the number of techniques Siddharth can use.
The second line contains integer ~N~ ~(1\le N \le 10^{18})~, representing the number of problems he will write.
The next ~S~ lines contain integers ~K_1, K_2, \dots, K_S~, where ~(1\le K_i\le 10^{18})~.
It is guaranteed that ~N\le K_1+K_2+\dots+K_S~. Note that this sum may not fit in a 64-bit integer.

Output

Output the maximum possible total quality, modulo ~10^9+7~.