Childan is making up a legendary story and trying to sell his forgery — a necklace with a strong sense of "Wu" to the Kasouras. But Mr. Kasoura is challenging the truth of Childan's story. So he is going to ask a few questions about Childan's so-called "personal treasure" necklace.

This "personal treasure" is a multiset $S$ of $m$ "01-strings".

A "01-string" is a string that contains $n$ characters "0" and "1". For example, if $n=4$, strings "0110", "0000", and "1110" are "01-strings", but "00110" (there are $5$ characters, not $4$) and "zero" (unallowed characters) are not.

Note that the multiset $S$ can contain equal elements.

Frequently, Mr. Kasoura will provide a "01-string" $t$ and ask Childan how many strings $s$ are in the multiset $S$ such that the "Wu" value of the pair $(s, t)$ is not greater than $k$.

Mrs. Kasoura and Mr. Kasoura think that if $s_i = t_i$ ($1\leq i\leq n$) then the "Wu" value of the character pair equals to $w_i$, otherwise $0$. The "Wu" value of the "01-string" pair is the sum of the "Wu" values of every character pair. Note that the length of every "01-string" is equal to $n$.

For example, if $w=[4, 5, 3, 6]$, "Wu" of ("1001", "1100") is $7$ because these strings have equal characters only on the first and third positions, so $w_1+w_3=4+3=7$.

You need to help Childan to answer Mr. Kasoura's queries. That is to find the number of strings in the multiset $S$ such that the "Wu" value of the pair is not greater than $k$.