450B.md (967B)
1 Source: https://codeforces.com/problemset/problem/450/B 2 3 B. Jzzhu and Sequences 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Jzzhu has invented a kind of sequences, they meet the following property: 22 23  24 25 You are given *x* and *y*, please calculate *f**n* modulo 1000000007 (109 + 7). 26 27 Input 28 29 The first line contains two integers *x* and *y* (|*x*|, |*y*| ≤ 109). The second line contains a single integer *n* (1 ≤ *n* ≤ 2·109). 30 31 Output 32 33 Output a single integer representing *f**n* modulo 1000000007 (109 + 7). 34 35 Examples 36 37 Input 38 39 ``` 40 2 3 41 3 42 ``` 43 44 Output 45 46 ``` 47 1 48 ``` 49 50 Input 51 52 ``` 53 0 -1 54 2 55 ``` 56 57 Output 58 59 ``` 60 1000000006 61 ``` 62 63 Note 64 65 In the first sample, *f*2 = *f*1 + *f*3, 3 = 2 + *f*3, *f*3 = 1. 66 67 In the second sample, *f*2 = - 1; - 1 modulo (109 + 7) equals (109 + 6).