B. Requirements

Auditors are few, but papers to push around are many. For low level bulk processing, auditors employ secretaries. These secretaries are not very clever (this is why they're not auditors yet), but if a simple task is explained well, they can do it precisely and without asking needless questions (the famous motto for auditor's secretaries is "understanding is not required - only obedience"). One of the important tasks in such audits is to set up procedure manuals. Such a manual contains (among other things) a list of requirements. Once a process doesn't meet a requirement, the difference must be documented clearly.

http://www.clker.com/clipart-piles-of-paper.html

To make sure there are enough manuals available for describing all processes of a company, the custom is that auditors dictate all manuals to secretaries after the audit ends. The secretaries then merge all manuals with all other manuals. All possible combinations are kept, to be on the safe side; but since this merge produces new manuals in the system, they have to restart merging again, producing even more combinations. This goes on and on until the end of the working day. (Precisely until the end: since the labor union of secretaries is strong, they don't have to do any overtime.)

A merge of two manuals A and B will result in a new manual C, and is produced in three steps:

• take an empty sheet and label it as manual C
• copy all requirements of A to C
• append all requirements that are present in B but are not present in A to the end of C.

Secretaries are not just hard-working but are also very pedantic. For the two manuals mentioned above, they not only merge A and B into C, but also B and A into D.

Looking at all this, you realize what they did not: each requirement is just a 1-bit property of a manual (whether the manual has it or not), since the order of requirements does not really matter. Sooner or later, there are going to be ultimate manuals that will contain all requirements ever invented by the auditors. Since you know you will need to prepare for the ultimate manuals, the only question remains: how many of those will exist? If only a few, you may sneak in and shred them before anyone notices.

Input

After the end of the audit, there are N different requirements the auditors came up with, that occur in the first batch of manuals. The secretaries do the full merge on this batch (merging each with each other, collecting the new manuals in a separate bin not to be mixed into the current merge efforts). Having finished the merge, they take all the old and new manuals together, and start over again, merging everything with everything else. The secretaries have time for doing T full iterations until the end of the day (they don't do partial iterations, to avoid confusion).

After N and T, the input file contains 2^N integers. Integer no. i (numbering starts from 0) is the count of how many copies of manual i exist (copies are handled like separate manuals when merging, but have the same set of requirements in them). Manual no. i lists only those requirements where the binary digit of i is 1 (i.e. manual 0 contains no requirements, manual 1 contains only requirement #1, manual 2 contains only requirement #2 while manual 3 contains both requirements #1 and #2).

Output

A single integer, the number of ultimate manuals that will exist by the end of the day modulo 1000000007.

Example input

2 123
87 65 43 21

Example output

991654691