問題一覧 > 通常問題

No.1785 Inequality Signs

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 64
作問者 : 8UqsVg4r / テスター : NatsubiSogan
お気に入りにしたユーザー ProblemId : 7404 / 自分の提出
問題文最終更新日: 2021-12-13 23:58:03
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
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

For a sequence of inequality signs $I=(\mathrm{ieq}_1, \mathrm{ieq}_2, \cdots, \mathrm{ieq}_{N-1})$ of length $N-1$, where each sign is either $<,\leq$, define its score as follows.

  • The number of integer sequences $A=(A_1,A_2,\dots,A_N)$ satisfying $$ 1 \leq A_1 \ \mathrm{ieq}_1 \ A_2 \ \mathrm{ieq}_2 \ A_3 \ \cdots \ A_{N-1} \ \mathrm{ieq}_{N-1} \ A_N \leq K $$ .

There are $2^{N-1}$ possible sequences $I$. Compute the score for all of them, and output the sum of the scores modulo $10^9+7$.

Input

$N\ K$
  • All input values are integers.
  • $2 \leq N \leq 2 \times 10^5$
  • $2 \leq K \leq 5 \times 10^8$

Output

Output the answer modulo $10^9+7$ on $1$ line.

Print a newline at the end.

Sample

Sample 1
Input
3 2
Output
6
  • When $\mathrm{ieq}_1$ is $<$ and $\mathrm{ieq}_2$ is $<$: no $A$ satisfies the condition.
  • When $\mathrm{ieq}_1$ is $\leq$ and $\mathrm{ieq}_2$ is $<$: only $A=(1,1,2)$ satisfies the condition.
  • When $\mathrm{ieq}_1$ is $<$ and $\mathrm{ieq}_2$ is $\leq$: only $A=(1,2,2)$ satisfies the condition.
  • When $\mathrm{ieq}_1$ is $\leq$ and $\mathrm{ieq}_2$ is $\leq$: the $4$ sequences $A=(1,1,1),\ (1,1,2),\ (1,2,2),\ (2,2,2)$ satisfy the condition.

The sum of these, $6$, is the value to output.

Sample 2
Input
31415 92653
Output
386985440

Note that you must output the computed sum modulo $10^9+7$.

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