fibo

/*
PROG: fibo
LANG: C++
*/

#define PROG "fibo"

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <assert.h>

#include <algorithm>
#include <iterator>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <string>

using namespace std;

#define DMP(_fmt, ...) fprintf(stderr, "[file %s, line %d]:" _fmt, __FILE__, __LINE__, __VA_ARGS__)

typedef list<int>::iterator liit;
typedef pair<int, int> pii;
typedef unsigned long long ull;

FILE *fin, *fout;

// constants and givens/pseudo-constants
// const int MAXN = 1005;
// int N;
const int INF = 999999999;
const long MOD = 1000000007;
const int MAXN = 500005;
int N;

// variables
// int nfoo, a[MAXN];
struct mat22 {
  long a, b;
  long c, d;
} fibo[MAXN]; // the awesome way to compute fibonnaci numbers
mat22 temp;

void matmult(const mat22& m1, const mat22& m2, long& a, long& b, long& c, long& d) {
  a = ((m1.a * m2.a) % MOD + (m1.b * m2.c) % MOD) % MOD;
  b = ((m1.a * m2.b) % MOD + (m1.b * m2.d) % MOD) % MOD;

  c = ((m1.c * m2.a) % MOD + (m1.d * m2.c) % MOD) % MOD;
  d = ((m1.c * m2.b) % MOD + (m1.d * m2.d) % MOD) % MOD;
} // one shit-ton of ugly coming right up

void compute(int n);
void solve() {
  compute(N);
}

void compute(int n) {
  if(n < 2) {
    return;
  }
  compute(n / 2);
  long a, b, c, d;
  matmult(fibo[n / 2], fibo[n / 2], a, b, c, d);
  if(n & 1) {
    temp = (mat22) {a, b, c, d};
    matmult(temp, fibo[1], a, b, c, d);
  }
  fibo[n] = (mat22) {a, b, c, d};
}

void init() {
  fibo[0] = (mat22) {1, 0, 1, 0};
  fibo[1] = (mat22) {1, 1, 1, 0};
}

void input() {
  // fscanf(fin, "%d", &N);
  // for(int i = 0; i < N; ++i) {
  //   fscanf(fin, "%d", a+i);
  // }
  fscanf(fin, "%d", &N);
}

void output() {
  // fprintf(fout, "%d\n", nfoo);
  fprintf(fout, "%ld\n", fibo[N].b);
}

int main(int argc, char** argv)
{
  fin = fopen(PROG ".in", "r");
  fout = fopen(PROG ".out", "w");
  assert(fin != NULL);
  assert(fout != NULL);

  init();
  input();
  solve();
  output();

  fclose(fin);
  fclose(fout);

  exit(0);
}