No.462 6日知らずのコンピュータ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 61
作問者 : tatuyan_edsontatuyan_edson / テスター : はむこはむこ

3 ProblemId : 1389 / 出題時の順位表

問題文

1日2日と指折り数えるとき、吝嗇家は握った手を開くのが惜しくて、6日目を数えられないそうです。このことから俗に、吝嗇家のことを「6日知らず」と言ったというお話が現代にも落語などで伝わっています。

新しく出来たコンピュータは\(N\)ビットを用いた2進数で非負整数を表します。
例えば、\(N=5\)の場合、\(14\)は\(01110\)ですし、\(22\)は\(10110\)です。

このコンピュータは「6日知らず」で、数を順に表していく時、いずれか1ビットずつ立てていって表すのですが、一度1にしたビットを\(0\)に戻すことを嫌います。このため、このコンピュータが表せる数は、\(0\)から始まり\(2^N-1\)で終わる、\(N+1\)項の非負整数列となります。例えば、\(N=4\)の場合、\(0,2,3,11,15\)という数列が表せる数列の一例です。一方、同じ\(N=4\)であっても、\(0,1,3,12,15\)という数列は表せません。

今、この「6日知らず」のコンピュータを使って\(k\)個の非負整数\(a_1,a_2,\cdots,a_k\)を表したいとします。\(a_1\)〜\(a_k\)のすべてを含み、「6日知らず」のコンピュータで表せるような\(N+1\)項の非負整数列は一体何通りあるか求めるプログラムを作成してください。但し、\(k=0\)の場合は、全ての数列が条件を満たします。答えはとても大きくなることがあるので、\(10^9+7\)で割った剰余を出力してください。なお、表すことが出来ない場合は\(0\)通りとします。

入力

\(N\) \(k\)
\(a_1\) \(a_2\) ... \(a_k\)

1行目には、整数で\(N\)と\(k\)が半角空白を区切りとして与えられます。\(1 \le N \le 60 \)、\( 0 \le k \le N+1 \)
2行目には、半角空白を区切りとして\(k\)個の非負整数が与えられ、これが順に\(a_1,a_2,\cdots,a_k\)を表します。この値はいずれも0以上\(2^N-1\)以下であり、同じ値が複数含まれることはありません。

\(k=0\)である入力の場合、2行目の入力がない点に注意してください。

出力

出力は1行のみで、「6日知らず」のコンピュータで表せるような\(N+1\)項の非負整数列は一体何通りあるか、\(10^9+7\)で割った剰余を整数値で出力してください。

サンプル

サンプル1
入力
4 2
2 11
出力
2

\(0,2,3,11,15\)と\(0,2,10,11,15\)の2通りの数列が考えられます。

サンプル2
入力
10 3
5 1 3
出力
0

\(5,1,3\)のすべてを含んでいて、6日知らずのコンピュータで表せるような数列は存在しません。

サンプル3
入力
3 0
出力
6

\(k=0\)なので、表せる全ての数列を考えます。
\(0,1,3,7\)
\(0,1,5,7\)
\(0,2,3,7\)
\(0,2,6,7\)
\(0,4,5,7\)
\(0,4,6,7\)
の、全6通りが存在します。

提出ページヘ