Двоичный поиск --- это алгоритм, который используется для поиска заданного элемента в отсортированном массиве. Рассмотрим следующий псевдокод двоичного поиска ("\textbf{/}" означает деление нацело): \textbf{вход: a\[0..n-1\], x} \textbf{l=0;} \textbf{r=n;} \textbf{while ( l < r-1 ) \{} \textbf{m=(l+r)/2;} \textbf{if(a\[m\]<=x)} \textbf{l=m;} \textbf{else} \textbf{r=m;} \textbf{\}} \textbf{if(a\[l\]==x)} \textbf{return true;} \textbf{else} \textbf{return false;} Иногда оказывается, что двоичный поиск находит вхождение некоторого элемента в массив даже если массив не отсортирован. Вам задано число \textbf{n}. Требуется найти количество пар <\textbf{a}, \textbf{x}>, где \textbf{a} представляет собой массив длины \textbf{n}, содержащий целые числа от \textbf{1} до \textbf{n}, а \textbf{x} ---целое число от \textbf{1} до \textbf{n}, таких что приведенная процедура возвращает "\textbf{true}", если её запустить на массиве \textbf{a} и числе \textbf{x} в качестве аргументов. \InputFile Входной файл содержит одно целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}). \OutputFile Выведите одно целое число --- ответ на поставленную задачу.