fork download 
  1. #include <iostream>
  2. #define boost ios_base::sync_with_stdio(0); cin.tie(0);
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. const ll MOD = 1e9 + 7;
  8.  
  9. ll n;
  10.  
  11. class Matrix {
  12. public:
  13.     ll data[2][2];
  14.  
  15.     Matrix(){}
  16.  
  17.     Matrix(ll a, ll b, ll c, ll d) {
  18.         data[0][0] = a;
  19.         data[0][1] = b;
  20.         data[1][0] = c;
  21.         data[1][1] = d;
  22.     }
  23.  
  24.  
  25.     Matrix& operator *=(Matrix &b){
  26.         Matrix c;
  27.         for (int i = 0; i < 2; i++)
  28.             for (int j = 0; j < 2; j++)
  29.                 c.data[i][j] = (data[i][0] * b.data[0][j] + data[i][1] * b.data[1][j]) % MOD;
  30.         return *this = c;
  31.     }
  32. };
  33.  
  34. ll pow(Matrix a, ll n) {
  35.     Matrix t(1, 0, 0, 1);
  36.     for (; n > 0; n >>= 1, a *= a)
  37.         if (n & 1)
  38.             t *= a;
  39.     return t.data[0][0];
  40. }
  41.  
  42. void solve() {
  43.     cin >> n;
  44.     cout << pow(Matrix(1, 1, 1, 0), n - 1) << "\n";
  45. }
  46.  
  47. int main() {
  48.     boost
  49.     int t = 1;
  50.     while (t--) {
  51.         solve();
  52.     }
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
1000000000000000000
stdout 
209783453
https://ideone.com/sPL3Hb
language:
C++14 (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!