### 问题描述 给定整数 $n,a,b$，已知 $f(1)=f(2)=1$，$f(k)=a \times f(k-1)+b \times f(k-2)$（$k \geq 3$），求 $f(n)$。 由于答案可能很大，结果需对 $1000000007$ 取余。 ### 输入格式 输入共一行，包含 $3$ 个整数 $n,a,b$，表示给定整数。 ### 输出格式 输出共一行，包含一个整数，表示 $f(n)$。 ### 样例输入 ``` 3 2 2 ``` ### 样例输出 ``` 4 ``` ### 评测数据规模 对于所有评测数据，$3 \leq n \leq 10^9$，$1 \leq a,b \leq 10^9$。