7847 - 试题H:数列第N项 20'

通过次数

64

提交次数

311

时间限制 : 1 秒
内存限制 : 256 MB

a_n = (3a_{n-1} + 4a_{n-2})\ mod\ 1e9 + 7

输入

输入三个正整数n,a_1,a_2

输出

输出a_n

样例

输入

5 1 1

输出

103

提示

数据规模

对于50\%的数据,3\le n\le 50, 1\le a_1,a_2 \le 10

对于70\%的数据,3\le n\le 10^7, 1\le a_1,a_2 \le 10

对于100\%的数据,3\le n\le 10^{12}, 1\le a_1,a_2 \le 10

来源

竞码编程-蓝桥杯校内选拔赛(决赛)重现赛