AT_agc013_e [AGC013E] Placing Squares

[problemUrl]: https://atcoder.jp/contests/agc013/tasks/agc013_e joisinoお姉ちゃんは、長さ $ N $ の棒を持っています。 この棒には $ M $ 個の印がついています。 $ i $ 個目の印は、棒の左端から距離 $ X_i $ の位置についています。 joisinoお姉ちゃんは、この棒の上にいくつかの正方形を置くことにしました。 正方形を置くにあたって、以下のような条件があります。 - 辺の長さが整数の正方形しか置いてはならない。 - 全ての正方形は、底辺が棒と接するように置かなくてはならない。 - 正方形は、棒の上に敷き詰められている必要がある。 つまり、正方形が棒からはみ出したり、上に正方形が乗っていないような棒の部分が存在したりしてはならない。 - 棒の印がついている部分の真上は、$ 2 $ つの正方形の境目であってはならない。 条件を満たす配置とそうでない配置の例 ある正方形の配置の美しさとは、置かれている正方形の面積をすべて**掛け合わせた**値です。 joisinoお姉ちゃんは、上の条件を満たすような正方形の配置全てについて、その美しさを求め、その総和を知りたくなりました。 あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作ることです。 なお、答えは非常に大きくなることがあるので、$ 10^9+7 $ で割った余りを出力してください。

N/A

N/A

### 制約 - 入力は全て整数である - $ 1\ \leq\ N\ \leq\ 10^9 $ - $ 0\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ X_1\