Codeforces ラウンド #258 (ディビジョン 2) B. Jzzhu とシーケンス (行列のクイックパワー)_html/css_WEB-ITnose

题目链接：http://codeforces.com/problemset/problem/450/B

----------------------------------------------------------------------------------------------------------------------------------------------------------

欢迎光临天资小屋：http://user.qzone.qq.com/593830943/main

----------------------------------------------------------------------------------------------------------------------------------------------------------

B. Jzzhu とシーケンス

テストごとの制限時間

テストごとのメモリ制限

入力

出力

Jzzhu は一種のシーケンスを発明しました。それらは次の特性を満たします:

あなたには x と y が与えられます, fn modulo 1000000007 (109?+?7) を計算してください。

入力

最初の行には 2 つの整数 x と y (|x|,?|y|?≤?109) が含まれています。 2 行目には単一の整数 n (1?≤?n?≤?2・109) が含まれています。

出力

fn モジュロ 1000000007 (109?+?7) を表す単一の整数を出力します。

サンプルテスト

入力

2 33

出力

入力

0 -12

出力

1000000006

注

最初のサンプルでは、​​f2?=?f1?+?f3 , 3?=?2?+?f3, f3?=?1.

2 番目のサンプルでは、​​ f2?=??-?1; ?-?1 modulo (109?+?7) equals (109?+?6)。