小红拿到了一个数组，她想知道该数组所有子序列的逆序对数量之和是多少？ 定义一个数组的子序列是，数组中取若干元素（可以不连续）按原数组顺序形成的新数组。

输入描述:

第一行输入一个正整数，代表数组的大小。第二行输入个正整数，代表数组的元素。

输出描述:

一个整数，代表所有子序列的数量之和。由于答案过大 ，请对取模。