Still Light

一列に並んだ 個の電球があり、マスには左から順番に の番号がついています。 最初は全ての電球の明かりがついていません。

あなたは 種類の操作を好きな順に好きな回数だけ行って電球の明かりをつけたり消したりできます。 種類目の操作は以下の通りです。

• 連続する 個の電球を選び、明かりがついている電球の明かりを消し、ついていない電球の明かりをつける。

明かりのついている電球の集合としてありうるものは何通り得られますか。答えを で割ったあまりを出力してください。

入力はすべて整数である。

N M
x_1 x_2 ... x_M

明かりのついている電球の集合としてありうるものの場合の数を で割ったあまりを出力してください。

4 1
3

4

明かりのついている電球の集合としてあり得るものは の 通りがあり得ます。

100000 3
21 57 3

134565347