問題一覧 > 通常問題

No.685 Logical Operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : Pulmn / テスター : はむこ
5 ProblemId : 1783 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-04-30 20:03:48

問題文

非負整数 N が与えられます。0≤x≤y≤N と x AND y<x XOR y<x OR y が成り立つ (x,y) の個数を 109+7=1,000,000,007 で割った時の余りを求めてください。
なお、AND,XOR,OR はそれぞれビットごとの 論理積,排他的論理和,論理和 を表します。

入力

N

0≤N≤1018

出力

条件を満たす (x,y) の個数を 1,000,000,007 で割った時の余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
10
出力
16

条件を満たす (x,y) として、(3,5),(7,9) などがあります。
(x,y)=(3,5) のとき、(x AND y,x XOR y,x OR y)=(1,6,7)
(x,y)=(7,9) のとき、(x AND y,x XOR y,x OR y)=(1,14,15)

サンプル2
入力
0
出力
0

N は非負整数であることに注意してください。

サンプル3
入力
1000
出力
308344

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