No.685 Logical Operations
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 :
Pulmn
/ テスター :
はむこ
タグ : / 解いたユーザー数 52
作問者 :
Pulmn
/ テスター :
はむこ
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。