codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/c84e959b7fd00c2ebce39e2b33db6bdb624ba8f3.png)
     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).