問題一覧 > 通常問題

No.1811 EQUIV Ten

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 93
作問者 : MasKoaTS / テスター : 👑 箱星 ygussany
お気に入りにしたユーザー ProblemId : 7005 / 自分の提出
問題文最終更新日: 2024-11-28 18:40:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 327 (順位表) の他の問題:

Problem Statement

You are given a non-negative integer $N$.

How many non-negative integers $x$ less than $2^{N}$ satisfy the following condition?

  • There exists a non-negative integer $k$ such that the remainder when $\displaystyle \left \lfloor \frac{x}{2^{k} } \right \rfloor$ is divided by $16$ is $10$.

    (Here, $\lfloor a \rfloor$ denotes the largest integer not exceeding $a$.)

Since the answer can be very large, output the remainder when it is divided by $10^{9}+7$.

Constraints

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

  • $N$ is an integer.

Input

The input is given in the following format.

$N$

  • $N$ is given on line $1$.

Output

Output the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
7
Output
28

Among the non-negative integers $x$ less than $2^{7}=128$, the values of $x$ satisfying the condition are the following $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$

For example, when $x = 107$, taking $k = 2$ gives $\displaystyle \left \lfloor \frac{107}{2^{2} } \right \rfloor = 26$, and the remainder when this is divided by $16$ is $10$.

Sample 2
Input
3
Output
0

There is no $x$ satisfying the condition.

Sample 3
Input
100
Output
247636996

Output the remainder when the answer is divided by $10^{9}+7$.

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