题目描述

小纳和小雪玩一个取石子游戏。原游戏过于经典，不适合在省选赛场上玩，因此小纳略微改动了游戏规则。

有一堆 $n$ 个石子，小雪先手，两人轮流从石子堆中取出一定数量（至少一个）的石子，并满足以下规则：

1. 第一次取石子时，不能把所有石子一次取完；

2. 设上一个人刚刚取了 $x$ 个石子，则本次取出的石子数不能超过

   $$\alpha x+\beta,$$

   其中 $\alpha,\beta$ 是预先给定的实数；

3. 轮到某人时，如果没有合法操作，则该玩家输掉游戏。

对于某些正整数 $n$，小纳存在必胜策略。将所有这样的 $n$ 从小到大排列，记为

给定 $K$，求 $H_K$。

由于答案可能很大，只需输出 $H_K$ 对

取模后的结果。

输入格式

一行三个数 $K,\alpha,\beta$。

输出格式

输出一行一个整数，表示 $H_K\bmod 1000000007$。

样例

样例输入

4 2.00 0.00

样例输出

5

样例解释

容易证明，当 $n=1,2,3$ 时，小纳均获胜。

当 $n=4$ 时，小雪先取 $1$ 个石子。之后无论小纳取 $1$ 个还是 $2$ 个，小雪都能在下一轮取完剩余石子，因此小雪获胜。

当 $n=5$ 时：

• 若小雪先取 $1$ 个，则双方地位反转，游戏进入 $n=4$ 的状态；
• 若小雪先取超过 $1$ 个，则小纳下一轮即可取完剩余石子。

因此小纳获胜。

所以：

数据范围及约定

• 对于 $5\%$ 的数据，$\alpha=1,\beta=0$；

• 对于另外 $5\%$ 的数据，$\alpha=2,\beta=0$；

• 对于另外 $20\%$ 的数据，$K\le 10^6,\beta=0$；

• 对于另外 $10\%$ 的数据，$\beta=0$；

• 对于全部数据：

  $$1\le K\le 10^9,\qquad 1\le\alpha\le 50,\qquad 0\le\beta\le 500.$$

输入中的 $\alpha,\beta$ 均保留两位小数。