### 问题描述

给定一个长度为 $n$ 的数组 $a$，小飞先随机选中其中任意个位置（不能为空），进行染色。

记 $i$ 为已被染色的某个位置，对于每个 $i$，将所有满足 $|i - j| \bmod k = 0$ 的 $j$ 位置也染色，至此染色结束，而本次染色方案的得分为已染色位置中最大的元素值。

请给出 $2^n - 1$ 种染色方案的得分之和，由于这个结果可能很大，输出得分之和对 $1e9 + 7$ 取模的结果。

输入格式

第一行两个整数 $k,n$。

第二行 $n$ 个整数，表示数组元素值。

输出格式

输出一个整数，表示得分之和对 $1e9 + 7$ 取模的结果。

样例输入

2 5
1 2 3 4 5

样例输出

152

评测数据规模

对于 $100$% 的评测数据，$1 \leq k \leq n \leq 10^5$，$1 \leq a_i \leq 10^5$。