The Secret Service have adopted a new communication system. This system uses blocks of varying length and type. Each block can only contain a word with the exact same length as it. Spaces and punctuation are ignored. Currently, the Secret Service has blocks of length up to and including ~N~ at their disposal. A message is composed of some number of blocks concatenated together. The length of a message is the sum of the lengths of the blocks which compose the message.

A message can contain a phrase if and only if a contiguous subsequence of blocks in that message has the same lengths as the words in the phrase and in the same order. For example, the message created by concatenating blocks of length ~3, 2, 6, 7~ in that order can contain the phrase Secret Service but the message created by concatenating blocks of length ~3, 2, 7, 6~ or ~3, 6, 2, 7~ cannot.

Blocks may appear any number of times within a message. Two messages are considered distinct if they have a different number of blocks, or if the ~i^{th}~ block of one message has either a different length or different type from the other message ~(1 \le i \le \text{number of blocks in each message})~.

The Secret Service currently has ~W~ operations which they communicate about using these messages. The ~i^{th}~ of these ~W~ operations is named ~n_i~ and is referred to as Operation ~n_i~ if it appears in a message. In addition to these ~W~ operations, there is always the possibility of an unnamed operation, which is dubbed Anonymous Operation if it appears in a message.

The Secret Service considers a message classified if it could contain the phrase Operation ~n_i~ ~(1 \le i \le W)~ or Anonymous Operation in it. The head of the Secret Service has enlisted you to find out how many classified messages with a length of exactly ~L~ there are given the blocks at their disposal. Since this number may be very large, output it modulo ~1\,000\,000\,007~ ~(10^9+7)~.

Input Specification

The first line will contain two space separated integers ~N~ ~(1 \le N \le 20)~ and ~L~ ~(1 \le L \le 10^{18})~.
The next ~N~ lines will each contain one integer ~t_i~ ~(1 \le t_i \le 10^6)~ which represents the number of types of blocks with length ~i~ that the Secret Service has.
The ~N+2^{th}~ line will contain one integer, ~W~ ~(1 \le W \le 100)~.
The next ~W~ lines will each contain a single string, ~n_i~ ~(1 \le |n_i| \le 20)~.

For ~40\%~ of points, ~L \le 10\,000~.

Output Specification

Output a single integer, the number of classified messages modulo ~1\,000\,000\,007~ ~(10^9+7)~.

Sample Input

20 38
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
Crossroads

Sample Output

8

Explanation for Sample Output

The ~8~ classified messages are formed by concatenating blocks of the following lengths in this order:

• ~9, 9, 10, 10~
• ~9, 10, 9, 10~
• ~9, 10, 10, 9~
• ~10, 9, 9, 10~
• ~10, 9, 10, 9~
• ~10, 10, 9, 9~
• ~9, 9, 20~
• ~20, 9, 9~