問題一覧 > 通常問題

No.1811 EQUIV Ten

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

問題文

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

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

  • ある非負整数 kk が存在し、⌊x2k⌋\displaystyle \left \lfloor \frac{x}{2^{k} } \right \rfloor を 1616 で割った余りが 1010 となる。

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

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

制約

  • 0≤N≤2×1050 \leq N \leq 2 \times 10^{5}

  • NN は整数

入力

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

NN

  • 11 行目には NN が与えられる

出力

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

サンプル

サンプル1
入力
7
出力
28

27=1282^{7}=128 未満の非負整数 xx のうち、条件を満たす xx は次の 2828 個です。

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,12210, 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=107x = 107 のとき、k=2k = 2 とすれば ⌊10722⌋=26\displaystyle \left \lfloor \frac{107}{2^{2} } \right \rfloor = 26 となり、これを 1616 で割った余りは 1010 となります。

サンプル2
入力
3
出力
0

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

サンプル3
入力
100
出力
247636996

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

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