問題一覧 > 通常問題

No.1426 Got a Covered OR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 61
作問者 : 👑 koboshikoboshi / テスター : nok0nok0
9 ProblemId : 5286 / 出題時の順位表
問題文最終更新日: 2021-03-06 05:50:12

ストーリー

古代ユキコ王国では長さ $N$ の正の整数列 $A_1,A_2,\ldots,A_N$ が神聖な数列として扱われていたと言い伝えられています。また、王国には石碑が $N$ 枚あり、$i$ 番目の石碑には $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \ \cdots \ \mathrm{OR} \ A_i$ の値が刻まれていたと言い伝えられています。しかし王国の滅亡とともに、神聖な数列 $A_1,A_2,\ldots,A_N$ が何であったかという情報は失われてしまいました。

調査員の小星さんは $N$ 枚の石碑のうち一部を発見しました。$i$ 番目の石碑には値 $B_i$ が刻まれていました。$B_i=-1$ のとき、$i$ 番目の石碑が発見されなかったことを表します。$B_N\ne -1$ (すなわち、$N$ 番目の石碑は発見されたこと) が保証されます。

小星さんは神聖な数列 $A_1,A_2,\ldots,A_N$ としてあり得るものが何通りあるかを求めようとしましたが、できませんでした。そこで、あなたに以下の問題を解くことを依頼しました。

問題文

次の条件をみたす正の整数列 $A_1,A_2,\ldots,A_N$ が何通りあるかを求めてください。

  • $B_i\ne -1$ をみたす $i \ (i=1,2,\ldots,N)$ に対し、$B_i$ は $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \ \cdots \ \mathrm{OR} \ A_i$ と等しい。

ただし答えは非常に大きくなる場合があるので、$10^9+7$ で割った余りを求めてください。答えは有限であることが保証されます。

$a \ \mathrm{OR} \ b$ は $a$ と $b$ のビットごとの論理和を表します。

入力

$N$
$B_1$ $B_2$ $\ldots$ $B_N$
  • 入力はすべて整数
  • $1\le N\le 10^5$
  • $1\le B_i\lt 2^{30}$ または $B_i=-1$
  • $B_N\ne -1$

出力

正の整数列 $A_1,A_2,\ldots,A_N$ としてあり得るものが何通りあるかを求めて、$10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
3
1 -1 3
出力
8

$(A_1,A_2,A_3)=(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(1,3,1),(1,3,2),(1,3,3)$ の $8$ 通りです。

サンプル2
入力
5
5 -1 -1 -1 4
出力
0

存在しない場合もあります。

サンプル3
入力
7
-1 -1 -1 -1 -1 -1 7777777
出力
281468948

$10^9+7$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。