No.685 Logical Operations

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

1 ProblemId : 1783 / 出題時の順位表

問題文

非負整数 $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

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

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