A-A simple problem_第三届太原理工大学程序设计竞赛新生赛(重现赛)

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

已知

f(0)=0,f(1)=1
$f(x)=af(x-1)+bf(x-2)\qquad (x \geq 2)$

并有

$g(x,y)=\sum^{y}_{i=x}f(i)\qquad (1 \leq x \leq y)$
$F(x)=\sum^{x}_{i=1} \sum^{x}_{j=i} g(i,j)\qquad (x \geq 1)$

现已知 $a,b,x(1 \leq a,b \leq 10^5,1 \leq x \leq 10^{12})$ ，求 F(x)，结果对 $10^9+7$ 取模。

输入描述:

三个整数 a,b,x 。

输出描述:

一个整数 F(x)，结果对  取模。

示例1

输入

复制

3 1 3

输出

复制

示例2

输入

复制

2 2 3

输出

复制