在遥远的秘密营地里，伟大的先知 ftiasch 正在尝试构建一种能够通过单次提交解决任何 ICPC 问题的法术。

为了实现这一宏伟目标，他精心制作了一串包含 $n$ 个符文（或者简单来说，附魔符号）的字符串。符文共有 $m$ 种不同的类型，每种类型对应不同的元素。例如：火符文、水符文、光符文、暗符文、C++ 符文、萝莉符文等。通过激活字符串中的部分（可能为零个）符文并停用其余符文，可以锻造出一个法术。

解决世界上所有的 ICPC 问题绝非易事，即使有魔法的帮助也是如此！因此，ftiasch 想要估算他即将获得的法术的威力。

从本质上讲，任何法术的作用原理都是重新平衡世界中元素能量的流动。因此，如果法术中不存在某种元素的已激活符文，那么该法术将完全失效，威力为 $0$。

即使法术包含了所有类型的符文，其威力仍然会发生变化，而这正是精心制作的字符串发挥作用的地方。连续的已激活符文之间会形成魔法纽带，一段长度为 $l$ 的连续符文会产生 $g(l)$ 单位的威力，而法术的总威力是其所有连续段威力之和。经过大量涉及机器学习禁术的研究，ftiasch 最终得出了显式公式 $g(x) = 2x^3 + 3x^2 + 3x + 3$。

你可能在想，为什么 ftiasch 不直接激活字符串中的所有符文呢？原因很简单，ftiasch 做不到。更重要的是，那样做会使这个问题变得太简单。事实上，每个符文都以 $\frac{1}{2}$ 的概率独立激活，你需要计算该法术的期望威力。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 2 \times 10^5, 1 \le m \le 50$)，分别表示字符串的长度和符文的种类数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le m$)，描述了该字符串，$c_i$ 表示第 $i$ 个符文的类型。

输出格式

输出一个整数，表示 $E \times 2^n \pmod{10^9 + 7}$，其中 $E$ 是法术的期望威力。

样例

样例输入 1

3 2
1 2 2

样例输出 1

152

样例输入 2

4 3
1 2 1 2

样例输出 2

0

样例输入 3

6 3
1 2 3 3 2 1

样例输出 3

3627