問題一覧 > 通常問題

No.1811 EQUIV Ten

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 : MasKoaTSMasKoaTS / テスター : 箱星箱星 👑 ygussanyygussany
12 ProblemId : 7005 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-28 18:40:41

問題文

非負整数 $N$ が与えられます。

$2^{N}$ 未満の非負整数 $x$ のうち、次の条件を満たすものはいくつありますか？

  • ある非負整数 $k$ が存在し、$\displaystyle \left \lfloor \frac{x}{2^{k} } \right \rfloor$ を $16$ で割った余りが $10$ となる。

    （$\lfloor a \rfloor$ は $a$ を超えない最大の整数を表す）

ただし、答えは非常に大きくなる可能性があるので、$10^{9}+7$ で割った余りを出力してください。

制約

  • $0 \leq N \leq 2 \times 10^{5}$

  • $N$ は整数

入力

入力は次の形式で与えられます。

$N$

  • $1$ 行目には $N$ が与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
7
出力
28

$2^{7}=128$ 未満の非負整数 $x$ のうち、条件を満たす $x$ は次の $28$ 個です。

$10, 20, 21, 26, 40, 41, 42, 43, 52, 53, 58, 74, 80, 81, 82, 83, 84, 85, 86, 87, 90, 104, 105, 106, 107, 116, 117, 122$

例えば $x = 107$ のとき、$k = 2$ とすれば $\displaystyle \left \lfloor \frac{107}{2^{2} } \right \rfloor = 26$ となり、これを $16$ で割った余りは $10$ となります。

サンプル2
入力
3
出力
0

条件を満たす $x$ は存在しません。

サンプル3
入力
100
出力
247636996

答えを $10^{9}+7$ で割った余りを出力してください。

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