Маленькому Крису снится кошмар. Даже во снах все его мысли — только о математике.
Крису снятся m двоичных строк длины n, пронумерованных от 1 до m. Самое страшное то, что биты каждой из этих строк упорядочены либо по возрастанию, либо по убыванию. Например, Крис может видеть во сне следующие 4 строки длины 5:
Расстояние Хемминга H(a, b) между двумя строками a и b длины n — это количество позиций, на которых соответствующие символы в этих строках отличаются.
Крис считает, что любые три строки с различными номерами образуют тройку. Он убедил себя в том, что проснется, только если посчитает количество таких троек строк a, b, c, что сумма H(a, b) + H(b, c) + H(c, a) максимальна среди всех троек строк из приснившихся ему строк.
Помогите Крису проснуться от кошмара! Посчитайте для него это количество.