5719: Hamming Triples
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
E. Hamming Triples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Little Chris is having a nightmare. Even in dreams all he thinks about is math.
Chris dreams about m binary strings of length n, indexed with numbers from 1 to m. The most horrifying part is that the bits of each string are ordered in either ascending or descending order. For example, Chris could be dreaming about the following 4 strings of length 5:
The Hamming distance H(a,b) between two strings a and b of length n is the number of positions at which the corresponding symbols are different.
Chris thinks that each three strings with different indices constitute a single triple. Chris's delusion is that he will wake up only if he counts the number of such string triples a, b, c that the sum H(a,b)+H(b,c)+H(c,a) is maximal among all the string triples constructed from the dreamed strings.
Help Chris wake up from this nightmare!
Chris dreams about m binary strings of length n, indexed with numbers from 1 to m. The most horrifying part is that the bits of each string are ordered in either ascending or descending order. For example, Chris could be dreaming about the following 4 strings of length 5:
The Hamming distance H(a,b) between two strings a and b of length n is the number of positions at which the corresponding symbols are different.
Chris thinks that each three strings with different indices constitute a single triple. Chris's delusion is that he will wake up only if he counts the number of such string triples a, b, c that the sum H(a,b)+H(b,c)+H(c,a) is maximal among all the string triples constructed from the dreamed strings.
Help Chris wake up from this nightmare!
Input
The first line of input contains two space-separated integers n and m (1≤n≤109; 3≤m≤105), the length and the number of strings. The next m lines contain the desc
Output
Output a single integer, the number of such string triples among the given that the sum of the Hamming distances between the strings of the triple is maximal.
Examples
Input
5 4 0 3 0 5 1 4 1 5
Output
3
Input
10 4 1 5 0 5 0 5 1 5
Output
4
输入样例 复制
输出样例 复制