Маленький Слоник очень любит перестановки целых чисел от 1 до n. Но больше всего он любит их сортировать. Чтобы отсортировать перестановку Маленький Слоник несколько раз меняет некоторые элементы местами. В результате должна получиться перестановка 1, 2, 3, ..., n.

В этот раз у Маленького Слоника есть перестановка p₁, p₂, ..., p_n. Его программа-сортировка должна выполнить ровно m шагов, на i-ом из которых она меняет местами элементы, расположенные в данный момент на a_i-той и b_i-той позициях. Так случилось, что программа-сортировка Маленького Слоника сломалась, и теперь на каждом шагу она равновероятно может либо не сделать ничего, либо поменять требуемые элементы местами.

Теперь Маленький Слоник даже не надеется, что программа отсортирует перестановку, но все-таки ему интересно, насколько близка будет полученная в результате выполнения программы перестановка к отсортированной. Для этого помогите Маленькому Слонику найти математическое ожидание количества инверсий перестановки после выполнения всех шагов программы.

Пару целых чисел i, j (1 ≤ i < j ≤ n) назовем инверсией в перестановке p₁, p₂, ..., p_n, если выполняется неравенство p_i > p_j.