問題一覧 > 通常問題

No.1785 Inequality Signs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 61
作問者 : 8UqsVg4r8UqsVg4r / テスター : NatsubiSoganNatsubiSogan
7 ProblemId : 7404 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-13 23:58:03

問題文

$<,\leq$ のいずれかからなる長さ $N-1$ の不等号列 $I=(\mathrm{ieq}_1, \mathrm{ieq}_2, \cdots, \mathrm{ieq}_{N-1})$ に対して、スコア を以下のように定義します。

  • 整数列 $A=(A_1,A_2,\dots,A_N)$ であって、 $$ 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 $$ を満たすものの数。

列 $I$ として考えられるものは $2^{N-1}$ 通りありますが、それらすべてについて スコア を求め、その総和を $10^9+7$ で割ったあまりを出力してください。

入力

$N\ K$
  • 入力はすべて整数
  • $2 \leq N \leq 2 \times 10^5$
  • $2 \leq K \leq 5 \times 10^8$

出力

求めた答えを $10^9+7$ で割ったあまりを $1$ 行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 2
出力
6
  • $\mathrm{ieq}_1$ が $<$ で $\mathrm{ieq}_2$ が $<$ のとき：条件を満たす $A$ は存在しません。
  • $\mathrm{ieq}_1$ が $\leq$ で $\mathrm{ieq}_2$ が $<$ のとき：$A=(1,1,2)$ のみが条件を満たします。
  • $\mathrm{ieq}_1$ が $<$ で $\mathrm{ieq}_2$ が $\leq$ のとき：$A=(1,2,2)$ のみが条件を満たします。
  • $\mathrm{ieq}_1$ が $\leq$ で $\mathrm{ieq}_2$ が $\leq$ のとき：$A=(1,1,1),\ (1,1,2),\ (1,2,2),\ (2,2,2)$ の $4$ つが条件を満たします。

これらを合計した $6$ が出力する値となります。

サンプル2
入力
31415 92653
出力
386985440

求めた総和を $10^9+7$ で割ったあまりを出力することに注意してください。

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