Маленький Слоник очень любит перестановки целых чисел от 1 до n. Но больше всего он любит их сортировать. Чтобы отсортировать перестановку Маленький Слоник несколько раз меняет некоторые элементы местами. В результате должна получиться перестановка 1, 2, 3, ..., n.
В этот раз у Маленького Слоника есть перестановка p1, p2, ..., pn. Его программа-сортировка должна выполнить ровно m шагов, на i-ом из которых она меняет местами элементы, расположенные в данный момент на ai-той и bi-той позициях. Так случилось, что программа-сортировка Маленького Слоника сломалась, и теперь на каждом шагу она равновероятно может либо не сделать ничего, либо поменять требуемые элементы местами.
Теперь Маленький Слоник даже не надеется, что программа отсортирует перестановку, но все-таки ему интересно, насколько близка будет полученная в результате выполнения программы перестановка к отсортированной. Для этого помогите Маленькому Слонику найти математическое ожидание количества инверсий перестановки после выполнения всех шагов программы.
Пару целых чисел i, j (1 ≤ i < j ≤ n) назовем инверсией в перестановке p1, p2, ..., pn, если выполняется неравенство pi > pj.