The annual Colobus Monkey Conference is underway! Representatives from each tribe have gathered to discuss threats, spread gossip, and grandstand among peers. Before proceedings start getting heated, a banquet must be prepared for each representative to feast on. The banquet consists of ~m~ different types of fruit, and since they are all spoiled politicians, each monkey will only consume certain fruits and refuse the others.

This information is represented as a binary string of length ~m~ for each monkey:

• 1 means the monkey will eat the fruit at that position
• 0 means the monkey refuses the fruit at that position

The head chef must choose a non-empty menu, consisting of any subset of the ~m~ fruits. A menu is valid if every monkey can eat at least one fruit from the menu. The chef needs to find out how many valid menus are possible.

Input

The first line consists of two integers ~n~ and ~m~ (~1 \leq n \leq 10^5~, ~1 \leq m \leq 20~), the number of monkey representatives and the number of different types of fruit.

The next ~n~ lines each contain a binary string of length ~m~, describing the fruits that each monkey is willing to eat. In the ~i~-th line, the ~j~-th character is ~1~ if the ~i~-th monkey will eat fruit ~j~, and ~0~ if the monkey refuses it.

Output

Output a single integer representing the number of valid menus.

Example

Input 1

3 3
110
101
011

Output 1

4

The valid menus are ~011~, ~101~, ~110~, and ~111~.

Input 2

3 4
1000
0100
0010

Output 2

2

Input 3

3 4
0111
1011
1101

Output 3

12