SuperPerfecte

#include <fstream>

using namespace std;
ifstream f("superperfecte.in");
ofstream g("superperfecte.out");
long long  n , i , m , k , x , y , z , t , x1 , y1 , z1 , t1 , sol , c [ 101 ] , d ;

int main()
{
    d = 555557 ;
    f >> n ;
    if ( n == 1 ) g << 4 ;
    if ( n == 2 ) g << 3 ;
    if ( n == 3 ) g << 12 ;
    if ( n >= 4 )
        {
           m = n - 3 ;
           k = 0 ;
           while ( m != 0)
                {
                  k++ ;
                  c [ k ] = m % 2 ;
                  m = m / 2 ;
                }
           x = 1 ; y = 0 ;
           z = 0 ; t = 1 ;
           for ( i = k ; i >= 1 ; i-- )
               if ( c [ i ] == 1 )
                {
                   x1 = ( x * x + y * z + x * y + y * t ) % d ;
                   y1 = ( 3 * x * x + 3 * y * z ) % d ;
                   z1 = ( x * z + z * t + y * z + t * t ) % d ;
                   t1 = ( 3 * x * z + 3 * z * t ) % d ;
                   x = x1 ; y = y1 ; z = z1 ; t = t1 ;
                }
               else
                {
                   x1 = ( x * x + y * z ) % d ;
                   y1 = ( x * y + y * t ) % d ;
                   z1 = ( x * z + z * t ) % d ;
                   t1 = ( y * z + t * t ) % d ;
                   x = x1 ; y = y1 ; z = z1 ; t = t1 ;
                }
             sol = ( 3 * x + 3 * y + 9 * z + 9 * t ) % d ;
             g << sol ;
        }
    return 0;
}