SOLVE
LATER
This is an incident from a distant parallel universe where Itachi and Sasuke, the two brothers, are loving brothers. The brothers had gone for a very difficult training. Now they are really tired after the long training and crave for some food. Luckily they found a shop on their way.
The food items in the shop has weird properties to make the customer learn the difference between Logical Product(\(Bitwise \space AND\)) and Arithmetic Product (\(\times\)) . Itachi being the elder brother already knows the difference and so he sends Sasuke to buy some food items from the shop and learn something new.
When Sasuke enters the shop, he notices that there is a set A comprised of N different food items to buy from. Each of the food item contains some of M different nutrients. Therefore each of the food item has two attributes associated: Price and Nutrition Value. The Nutrition Value is a binary string of length M denoting which of the M nutrients are present in the particular food item.
Sasuke is instructed to buy a subset \(S = {i_1,i_2,i_3...}\) of the A. The shopkeeper tells Sasuke the following rules of shopping:
Now to make his brother consider all the possibilities, Itachi asks him to calculate a function \(F(K) = \displaystyle\sum_{Nt(S)=K}^{S\subseteq A} Cost(S)\).
INPUT
The first line contains two integers N and M.
The following N lines describes all the food items of set X.
The first integer of each \(i^{th}\) denotes \(Price_i\).
The second string denotes its Nutrition Value. It is a M length binary string.
OUTPUT
Output \(M+1\) space separated integers denoting the values \(F(0)\space F(1)\space.. F(M)\).
Since the values can be quite large, print them \(mod\space 10^9+7\).
CONSTRAINTS
\( 1 ≤ N ≤ 10^5\)
\( 1 ≤ M ≤ 20\)
\( 1 ≤ Price_i ≤ 10^6\)
The 7 possible subsets are
F(0) = 10 + 30 = 40
F(1) = 5 + 15 = 20
F(2) = 2 + 6 = 8
F(3) = 3