問題一覧 > 通常問題

No.685 Logical Operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 41
作問者 : PulmnPulmn / テスター : はむこはむこ
4 ProblemId : 1783 / 出題時の順位表
問題文最終更新日: 2018-04-30 20:03:48

問題文

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

入力

$N$

$0\le N\le 10^{18}$

出力

条件を満たす $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。