该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：gravity.in 输出文件：gravity.out

重力粘合艺术是一种不使用粘合剂，将不同大小的石头高高堆叠起来的艺术形式。

小明痴迷分形艺术，他决定让所用石头的大小按分形规律堆叠。

称 $S_i$ 是一块大小为 $i$ 的石头，$G_{b, d}$ 是一种由美观度$b(b \gt 0)$ 和难度 $d(d \gt 0)$ 唯一确定的石头堆叠方式。

美观度为 $1$ 的 $G_{1, d}$ 是由 $d$ 块大小为 $1$ 的石头堆叠而成（$d$为任意正整数）。

美观度为 $i+1$ 的 $G_{i+1, d}$ 的堆叠规则如下：使用 $d$ 块大小为 $i+1$ 的石头，将 $G_{i, d}$、$S_{i+1}$、$G_{i, d}$、$S_{i+1}$、……、$S_{i+1}$、$G_{i, d}$ 这样的结构“夹在中间”堆叠而成。即 $S_{i+1}$ 与 $G_{i, d}$ 交替排列，且首尾均为 $G_{i, d}$）。

目前，小明已经完成了 $G_{b, d}$ 从最下层到第 $n$ 层的堆叠。

请计算完成剩余部分所需的石头大小总和，并将结果对 $10^9+7$ 取余后输出。

输入格式

第一行一个整数 $n$。

第二行两个正整数 $b,d$。

输出格式

输出一个整数，表示答案。

样例

样例 1

0
3 1

11

样例说明：

目标结构从最下层开始到最上层的石头大小为 $1213121$。

样例 2

4
3 1

4

样例 3

4
3 2

31

样例说明：

目标结构从最下层开始到最上层的石头大小为 $11211211311211211311211211$。

样例 4

114514
1919114 5141919

666638169

数据范围

对于 30% 的数据，$n,b,d \le 10$。

对于 50% 的数据，$n,b,d \le 10^5$。

对于 100% 的数据，$0 \le n \le 10^9$，$1 \le b \le 10^9$，$1 \le d \le 10^9$。