pepeuri

#include <fstream>

using namespace std;
ifstream f("pepeuri.in");
ofstream g("pepeuri.out");
long long n , m , k , i , j , a[10] , p[10][10] , b[10][10] ,c[10][10] , sol , suma , cif[31],u ,t ,d ;

void ridiclapatrat()
{
    for(i=0;i<=9;i++)
      for(j=0;j<=9;j++)
      {
        c[i][j]=0;
        for(k=0;k<=9;k++)c[i][j]=(c[i][j]+p[i][k]*p[k][j])%m;
      }
    for(i=0;i<=9;i++)
      for(j=0;j<=9;j++)p[i][j]=c[i][j];
}

void inmultesc()
{
    for(i=0;i<=9;i++)
      for(j=0;j<=9;j++)
      {
        c[i][j]=0;
        for(k=0;k<=9;k++)c[i][j]=(c[i][j]+p[i][k]*b[k][j])%m;
      }
    for(i=0;i<=9;i++)
      for(j=0;j<=9;j++)p[i][j]=c[i][j];
}

int main()
{
    f >> n;
    m=10111121 ;
    t=n-2;
    d=0 ;
    while( t!=0 )
    {
       d++;
       cif[d]=t%2;
       t=t/2;
    }
    a[0]=3;a[1]=2;a[2]=2;a[3]=2;a[4]=1;a[5]=1;a[6]=1;a[7]=2;a[8]=2;a[9]=1;
    for(i=0;i<=9;i++)p[i][i]=1;
    b[0][0]=1;
    b[0][1]=1;
    b[1][0]=1;
    for(i=0;i<=4;i++)b[i][4-i]=1;
    for(i=0;i<=9;i++)b[i][9-i]=1;
    b[7][9]=1;
    b[8][8]=1;
    b[9][7]=1;

    for(u=d;u>=1;u--)
    {
        if(cif[u]==1){ridiclapatrat();inmultesc();}
                else {ridiclapatrat();}
    }
    sol=0;
    for(i=0;i<=9;i++)
    {
        suma=0;
        for(j=0;j<=9;j++)suma=(suma+p[i][j]*a[j])%m;
        sol=(sol+suma)%m;
    }
    g << sol ;
    return 0;
}