Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
910 B
6
Indexable
Never
#include <bits/stdc++.h>

#define M 1000000007
typedef long long ll;
typedef unsigned long long int lli;

using namespace std;

struct Matran
{
  lli F[2][2];
  Matran()
  {
    F[0][0] = 0;
    F[0][1] = 1;
    F[1][0] = 1;
    F[1][1] = 1;
  }
};
Matran operator*(Matran a, Matran b)
{
  Matran c;
  c.F[0][0] = (a.F[0][0] * b.F[0][0] + a.F[0][1] * b.F[1][0]) % M;
  c.F[0][1] = (a.F[0][0] * b.F[0][1] + a.F[0][1] * b.F[1][1]) % M;
  c.F[1][0] = (a.F[1][0] * b.F[0][0] + a.F[1][1] * b.F[1][0]) % M;
  c.F[1][1] = (a.F[1][0] * b.F[0][1] + a.F[1][1] * b.F[1][1]) % M;
  return c;
}

Matran powermod(Matran a, lli n)
{
  if (n == 1)
    return a;
  if (n % 2 != 0)
    return a * powermod(a, n - 1);
  Matran x = powermod(a, n / 2);
  return x * x;
}

int main()
{
    lli n;
    cin >> n;
    Matran a;
    a = powermod(a, n);
    cout << a.F[0][1];
  return 0;
}