Войтек только что выиграл олимпиаду по математике в Байтландии! Приз восхитителен - отличная книга под названием 'Карточные фокусы для чайников.' 'Отлично!' он подумал, 'Наконец-то я смогу воспользоваться запылившейся колодой карт, которая без дела лежит у меня на столе!'
Первая глава книги это 'Как перемешать \(k\) карт в любом порядке, который вы хотите.' Формально это список из \(n\) детерминированных методов перемешать \(k\) карт. Более формально, \(i\)-й метод может быть описан перестановкой \((P_{i,1}, P_{i,2}, \dots, P_{i,k})\) целых чисел от \(1\) до \(k\). Если мы упорядочим карты в колоде от \(1\) до \(k\) сверху вниз, тогда \(P_{i,j}\) обозначает номер \(j\)-й карты сверху колоды после перемешивания.
Войтек хочет научиться только некоторым фокусам сегодня. Он выберет два целых числа \(l, r\) (\(1 \le l \le r \le n\)), и запомнит все фокусы от \(l\)-го до \(r\)-го, включительно. Затем он возьмет отсортированную колоду из \(k\) карт и будет применять случайные запомненные фокусы, пока ему не станет скучно. Он все еще любит математику, и поэтому заинтересовался: а сколько различных колод он может получить?
Войтек все еще не выбрал \(l\) и \(r\), но ему очень любопытно. Так он определил \(f(l, r)\) как количество различных колод которое он может получить, если выучит все фокусы от \(l\)-го до \(r\)-го, включительно. Чему равно
\(\)\sum_{l=1}^n \sum_{r=l}^n f(l, r)?\(\)
Примечание
Рассмотрим первый пример:
- Первый фокус меняет две верхние карты.
- Второй фокус берет карту снизу колоды и кладет ее наверх.
- Третий фокус меняет две нижние карты.
Первый и третий фокусы сами по себе позволяют получить только две колоды (либо две карты поменяны местами, либо нет). Таким образом, \(f(1, 1) = f(3, 3) = 2\).
Второй фокус позволяет совершать циклические сдвиги, таким образом \(f(2,2)=3\).
Оказывается, что два первых и два последних фокуса позволяют получить все возможные перестановки колоды Войтека. Таким образом \(f(1,2) = f(2,3) = f(1,3) = 3! = 6\).