問題文

はむこさんは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$は与えられないことが保証される。

出力

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

サンプル

0
3 1

11

4
3 1

4

7
3 1

0

4
3 2

31

114514
1919114 5141919

666638169