問題一覧 > 通常問題

No.681 Fractal Gravity Glue

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : はむこはむこ / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
1 ProblemId : 1853 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-04-27 23:36:39

問題文

はむこさんはGravity Glueに挑戦しようとしています。
Gravity Glueとは、様々な大きさの石を接着剤を使わず、高く積み上げるアートです。

はむこさんは、フラクタルに心酔しているので、使う石の大きさをフラクタルに積むことにしました。
Gravity Glue $G_{b, d}$は、美しさ$b>0$と難易度$d>0$で一意に決まる、石の積み方です。

美しさ$1$のGravity Glue $G_{1, d}$は、大きさ$1$の石$d$個を積み上げたものです($d$は任意の正整数)。
美しさ$i+1$のGravity Glue $G_{i+1, d}$は、大きさ$i+1$の石を$d$個使って、
($G_{i, d}$, 大きさ$i+1$の石, $G_{i, d}$, 大きさ$i+1$の石, ..., 大きさ$i+1$の石, $G_{i, d}$)とサンドイッチして積み上げたものです。

今、はむこさんは$G_{b, d}$を、下から$n$段目まで作り終えました。
残りを完成させるために必要な、石の大きさの総和をmod $10^9+7$で求めてください。

入力

n
b d

$0 \le n \le 10^9$, 整数
$1 \le b \le 10^9$, 整数
$1 \le d \le 10^9$, 整数

$G_{b, d}$の高さを超える$n$は与えられないことが保証される。

出力

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

サンプル

サンプル1
入力
0
3 1
出力
11

目標のGravity Glueは、下から1213121です。
$n=0$なので、これから全ての石を積み上げる必要があります。

サンプル2
入力
4
3 1
出力
4

目標のGravity Glueは、下から1213121です。
$n=4$なので、1213はすでに積み終えました。あとは121が必要なので、大きさの総和は4です。

サンプル3
入力
7
3 1
出力
0

すべて積み終わっています。

サンプル4
入力
4
3 2
出力
31

目標のGravity Glueは、下から11211211311211211311211211です。
$n=4$なので、1121はすでに積み終えました。残りの総和は31です。

サンプル5
入力
114514
1919114 5141919
出力
666638169

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