29497번 - Двоичный поиск 다국어

Двоичный поиск --- это алгоритм, который используется для поиска заданного элемента в отсортированном массиве. Рассмотрим следующий псевдокод двоичного поиска (<</>> означает деление нацело):

вход: a[0..n - 1], x

l = 0;
r = n;
while (l < r - 1) {
    m = (l + r) / 2;
    if (a[m] ≤ x) 
        l = m;
    else 
        r = m;
}
if (a[l] == x)
    return true;
else
    return false;

Иногда оказывается, что двоичный поиск находит вхождение некоторого элемента в массив даже если массив не отсортирован. Вам задано число $n$. Требуется найти количество пар $\langle a, x\rangle$, где $a$ представляет собой массив длины $n$, содержащий целые числа от 1 до $n$, а $x$ --- целое число от 1 до $n$, таких что приведенная процедура возвращает "true", если ее запустить на массиве $a$ и числе $x$ в качестве аргументов.

Входной файл содержит одно целое число $n$ ($1 \le n \le 1000$).

Выведите одно целое число --- ответ на поставленную задачу.