#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

const int MSZ = 3;

struct Mat {
  int d[MSZ][MSZ];

  Mat() {
    memset(d, 0, sizeof d);
    for (int i = 0; i < MSZ; i++)
      d[i][i] = 1;
  }

  void operator*=(const Mat &m2) {
    int res[MSZ][MSZ];
    memset(res, 0, sizeof res);
    for (int i = 0; i < MSZ; i++)
    for (int j = 0; j < MSZ; j++)
    for (int k = 0; k < MSZ; k++)
      res[i][j] += d[i][k] * m2.d[k][j];
    memcpy(d, res, sizeof d);
  }
};

Mat pow1(Mat a, int b) {
  Mat res;
  for (; b; b >>= 1, a *= a)
    if (b & 1) res *= a;
  return res;
}

Mat pow2(Mat a, int b) {
  if (b == 0) return Mat();
  if (b & 1) {
    Mat res = pow2(a, b - 1);
    res *= a;
    return res;
  }
  Mat res = pow2(a, b >> 1);
  res *= res;
  return res;
}

const int POW = 1e9;
const int STEPS = 3e5;

int main() {
  Mat src;
  for (int i = 0; i < MSZ; i++)
  for (int j = 0; j < MSZ - i; j++)
    src.d[i][j] = 1;
  
  clock_t st = clock();
  for (int step = 0; step < STEPS; step++)
    pow1(src, POW);
  printf("%d\n", clock() - st);

  st = clock();
  for (int step = 0; step < STEPS; step++)
    pow2(src, POW);
  printf("%d\n", clock() - st);  
  return 0;
}