No.681 Fractal Gravity Glue

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : はむこはむこ / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
0 ProblemId : 1853 / 出題時の順位表

問題文

はむこさんは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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。