Statement

Lorenzo devised an innovative yet incorrect algorithm to count the number of inversions is a pair (i, j) such that 0 < i < j < N - 1 and A_i > A_j. for any given permutation of N elements. Full of optimism, he computed this number for a permutation P_0, …, P_N - 1 simply as the sum \frac12 \sum_i = 0^N - 1 | P_i - i |. Unfortunately his formula has some flaws and the algorithm fails to consistently produce the correct output. Lorenzo is now wondering how often his algorithm yields the wrong answer: help him by counting the number of permutations for which his algorithm fails in computing the number of inversions! Since the answer might be quite large, you are asked to print it modulo 10^9 + 7.