小红的陡峭值（五）（easy）
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题为《G.小红的陡峭值（五）》的简单版本，两题的唯一区别在于本题 n 的范围更小。

\hspace{15pt}小红定义一个数组的陡峭值为：每两个相邻的元素，差值的绝对值之和。例如，数组 \{2,3,1\} 的陡峭值是 |2-3|+|3-1|=3。
\hspace{15pt}现在小红拿到了一个由 n 个整数组成的数组 \{a_1,a_2,\dots,a_n\}，然后蒙眼打乱了数组。她希望你求出该数组陡峭值的期望。请将答案对 (10^9+7) 取模后输出。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(2 \leqq n \leqq \pmb{18}\right) 代表数组中的元素个数。 
\hspace{15pt}第二行输入 n 个两两不同的整数 a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^9\right) 代表数组中的元素。

输出描述:

\hspace{15pt}可以证明答案可以表示为一个不可约分数 \tfrac{p}{q}，为了避免精度问题，请直接输出整数 \left(p \times q^{-1} \bmod M\right) 作为答案，其中 M = (10^9+7)，q^{-1} 是满足 q\times q^{-1} \equiv 1 \pmod{M} 的整数。
\hspace{15pt}更具体地，你需要找到一个整数 x \in [0, M) 满足 x \times q 对 M 取模等于 p，您可以查看样例解释得到更具体的说明。
示例1

输入

复制 
3
1 2 3

输出

复制 
666666674

说明

\hspace{15pt}在这个样例中，一共有 3! = 6 种可能的排列方式，其中，有 \tfrac{1}{3} 的概率得到陡峭值为 2 的数组，有 \tfrac{2}{3} 的概率得到陡峭值为 3 的数组，所以答案是 \tfrac{8}{3}。
\hspace{15pt}我们能够找到，666\,666\,674 \times 3 = 2\,000\,000\,022，对 10^9+7 取模后恰好等于分子 8，所以 666\,666\,674 是需要输出的答案。