#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

vector<int> suma(vector<int>& v1, vector<int>& v2, int b){
    vector<int> sum;
    int emp=0;
    while(v1.size()<v2.size()){
        v1.insert(v1.begin(),0);
    }
    while(v1.size()>v2.size()){
        v2.insert(v2.begin(),0);
    }
    for(int i=v1.size()-1; i>=0; i--){
        sum.insert(sum.begin(),(v1[i]+v2[i]+emp)%b);
        emp = (emp + v1[i]+v2[i])/b;
    }
    if(emp!=0){
       sum.insert(sum.begin(),emp);
    }
    return sum;
}

int mult(vector<int> v1, vector<int> v2, int b, int m, int n){
    cout<<endl;
    if(m==n){
        //cout<<endl<<"THE END"<<endl;
    }
    else{
    for(int i=0; i<v2.size(); i++){
            cout<<v2[i]<<" ";
        }
    cout<<"^ = ";
    cout<<endl;
    v1.clear();
    v1 = v2;
    vector<int> aux1;
    vector<int> aux2;
    if(v2.size()==1){
        for(int i=0; i<m; i++){
            vector<int> aux1;
                aux1.clear();
                int emp=0;
                for(int j=v1.size()-1; j>=0; j--){
                    aux1.insert(aux1.begin(),(v2[0]*v1[j]+emp)%b);
                    emp = (emp + v2[0]*v1[j])/b;
                }
                if(emp!=0){
                    aux1.insert(aux1.begin(),emp);
                }
                v1.clear();
                v1 = aux1;
                aux1.clear();
    }
    for(int i=0; i<v1.size(); i++){
            cout<<v1[i]<<" ";
                }
    cout<<endl;
    }
    if(v2.size()==2){
        int emp=0;
        v1.clear();
        v1 = v2;
        for(int i=0; i<m; i++){
                emp = 0;
                aux1.clear();
                aux2.clear();
            for(int j=v1.size()-1; j>=0; j--){
                aux1.insert(aux1.begin(),(v2[1]*v1[j]+emp)%b);
                emp = (emp + v2[1]*v1[j])/b;
        }
            if(emp!=0){
                aux1.insert(aux1.begin(),emp);
            }
            emp=0;
            aux2.insert(aux2.begin(),0);
            for(int j=v1.size()-1; j>=0; j--){
                aux2.insert(aux2.begin(),(v2[0]*v1[j]+emp)%b);
                emp = (emp + v2[0]*v1[j])/b;
            }
            if(emp!=0){
                aux2.insert(aux2.begin(),emp);
            }
            v1 = suma(aux1, aux2, b);
        }
        for(int i=0; i<v1.size(); i++){
                cout<<v1[i]<<" ";
            }
            cout<<endl;
    }
    if(v2.size()>2){
        cout<<endl;
        v1.clear();
        v1 = v2;
        for(int i=0; i<m; i++){
            aux1.clear();
            aux2.clear();
            int emp=0;
        for(int j=v1.size()-1; j>=0; j--){
            aux1.insert(aux1.begin(),(v2[v2.size()-1]*v1[j]+emp)%b);
            emp = (emp + v2[v2.size()-1]*v1[j])/b;
        }
        if(emp!=0){
            aux1.insert(aux1.begin(),emp);
        }
        emp=0;
        aux2.insert(aux2.begin(),0);
        for(int j=v1.size()-1; j>=0; j--){
            aux2.insert(aux2.begin(),(v2[v2.size()-2]*v1[j]+emp)%b);
            emp = (emp + v2[v2.size()-2]*v1[j])/b;
        }
        if(emp!=0){
            aux2.insert(aux2.begin(),emp);
        }
        vector<int> aux3;
        aux3 = suma(aux1, aux2, b);
        aux1.clear();
        for(int i=2; i<v2.size(); i++){
            aux1.clear();
            for(int j=0; j<i; j++){
                aux1.insert(aux1.begin(),0);
            }
            emp=0;
            for(int j=v1.size()-1; j>=0; j--){
                aux1.insert(aux1.begin(),(v2[v2.size()-1-i]*v1[j]+emp)%b);
                emp = (emp + v2[v2.size()-1-i]*v1[j])/b;
            }
             if(emp!=0){
                aux1.insert(aux1.begin(),emp);
            }
             aux3 = suma(aux3, aux1, b);
             v1.clear();
             v1 = aux3;
             aux3.clear();
        }
    }
    for(int i=0; i<v1.size(); i++){
        cout<<v1[i]<<" ";
    }
    cout<<endl;
        }
        vector<int> v3;
        v3.push_back(1);
        v2 = suma(v2, v3, b);
        m++;
        return mult(v1, v2, b, m, n);
}
}

int main(){
    int b, n;
    cout<<"Introduce until which number: ";
    cin>>n;
    cout<<endl<<"Introduce the base: ";
    cin>>b;
    cout<<endl;
    vector<int> v1;
    v1.push_back(1);
    vector<int> v2;
    v2.push_back(1);
    cout<<mult(v1, v2, b, 0, n+1);
}