Двійковий пошук --- це алгоритм, який використовується для пошуку заданого елементу у відсортваному масиві. Розглянемо наступний псевдокод двійкового пошуку ("\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 Виведіть одне ціле число --- відповідь на поставлену задачу.