No.895 MESE

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 90
作問者 : fuppy_kyoprofuppy_kyopro / テスター : e869120e869120
6 ProblemId : 3387 / 出題時の順位表
問題文最終更新日: 2019-09-15 14:30:45

問題文

三つの正の整数$a, b, c$が与えられます。以下の条件を満たす全ての三つの正の整数の組$(x, y, z)$について、$z$の総和を求めてください。
ただし、答えは非常に大きくなる可能性があるため$10^9+7$で割ったあまりを出力してください。

  • $x, y, z$を二進数で表記した時に1であるような桁の個数はそれぞれ$a, b, c$個である。
  • $x > y > z$をみたす。
  • $(x~or~y~or~z) = 2^{a + b + c} - 1$をみたす。
ここで、$or$はビットごとの論理和を表します。

入力

$a\ b\ c$

  • $1 ≤ a, b, c ≤ 10^5$
  • $a, b, c$は全て整数である。

出力

条件を満たす全ての$(x, y, z)$の組での$z$の総和を$10^9+7$で割ったあまりを一行に出力してください。
最後に改行を出力してください。

サンプル

サンプル1
入力
2 2 1
出力
17

条件を満たす$(x, y, z)$の組は二進数表記で
(11000, 00110, 00001), (11000, 00101, 00010), (10100, 01010, 00001), (10100, 01001, 00010),
(10010, 01100, 00001), (10010, 01001, 00100), (10001, 01100, 00010), (10001, 01010, 00100)
の$8$組です。
求める$z$の総和は$1+2+1+2+1+4+2+4=17$となります。

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

条件を満たす$(x, y, z)$の組は$(4, 2, 1)$の一つのみです。

サンプル3
入力
100 100 100
出力
208072283

$10^9+7$で割ったあまりを出力することに気をつけてください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。