#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;
class matrix{ //создаем класс матрицы, в основном для красивого перемножения
private:
int n,m;
int long long **arr;
public:
matrix(){
n = 1; m = 1;
}
matrix(int x){
n = x; m = x;
arr = new int long long *[n];
for(int i = 0; i < n; i++){
arr[i] = new int long long [m];
}
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
arr[j][k] = 0;
}
}
}
matrix(int x, int y){
n = x; m = y;
arr = new int long long *[n];
for(int i = 0; i < n; i++){
arr[i] = new int long long [m];
}
for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор
for(int k = 0; k < this->m; k++){
arr[j][k] = 0;
}
}
} // выше были описанны конструкторы
~matrix(){
for(int i = 0; i < n; i++){
delete arr[i];
}
delete arr;
}// деструктор
void read(){
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
cin >> arr[j][k];
}
}
}//функция ввода
void write(){
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
cout << arr[j][k] << " ";
}
cout << endl;
}
}// функция вывода
void create(int x, int y){
n = x; m = y;
arr = new int long long *[n];
for(int i = 0; i < n; i++){
arr[i] = new int long long [m];
}
}//функция измененияколичества выделяемой под нас памяти
matrix& operator=(const matrix& x){
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
arr[j][k] = x.arr[j][k];
}
}
return *this;
}// переопределение оператора присваивания для матриц
const matrix operator*(const matrix& x){
matrix ans(this->n, this->m);
for(int i = 0; i < this->n; i++){
for(int j = 0; j < this->m; j++){
for(int k = 0; k < this->m; k++){
ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
}
}
}
return ans;
}//переопределение умножения для матриц
matrix& operator*=(const matrix& x){
matrix ans(this->n, this->m);
for(int i = 0; i < this->n; i++){
for(int j = 0; j < this->m; j++){
for(int k = 0; k < this->m; k++){
ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
}
}
}
*this=ans;
return *this;
}//переопределение присвоить равно
matrix& pow(int n){
string s;
for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0
s+= to_string((n >> i)&1);;
}
int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки
for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой
matrix ans(this->n,this->m);
for(int j = 0; j < this->n; j++){
for(int k = 0; k < this->m; k++){
if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0;
}
}
matrix temp(this->n,this->m);
temp = *this;
for(int j = 0; j <= i; j++){
if(s[j] == '1'){
ans*=temp;
}
temp*=temp;
}
*this=ans;
return *this;
}
};
int main() {
int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа
cin >> n;
matrix mas(size); // создаем матрицу
mas.read();
mas.pow(n);
mas.write();
return 0;
}