出题人的妹子送了出题人一个手环，这个手环上有 n 个珠子，每个珠子上有一个数。 有一天，出题人和妹子分手了，想把这个手环从两个珠子间切开，并按顺时针顺序展开成一条链。 可以发现，这条链一共有 n 种可能性。求这 n 种可能性的逆序对数之积模 1000000007。

输入描述:

第一行一个数 n，表示珠子个数。接下来一行 n 个数，以顺时针顺序给出每个珠子上的整数

输出描述:

一个数，表示答案。

备注:

n=200000，-10^9=珠子上的整数=10^9。