#include <fstream>
#include <iostream>
#include <vector>
#include <stdexcept>

// ___________________________________________________________________________
// Constants.

::std::size_t  const maxn  = 100;

// ___________________________________________________________________________

/// \brief  Big number.
class number
{ private:
  
  /// \brief  Base 1000 digits.
  ::std::vector < unsigned >  m_d;
  
  public:
  
  /// \brief  Zero.
  number
  ()
  ;
  
  /// \brief  Digit.
  number
  ( int  d
  )
  ;
  
  /// \brief  Copy.
  number
  ( number const  & other
  )
  ; 
  
  /// \brief  +=
  number &
  operator +=
  ( number const  & other
  )
  ;
  
  /// \brief  >=
  bool
  operator >=
  ( number const  & other
  )
  const
  throw()
  ;
  
  /// \brief  Swap.
  void
  swap
  ( number  & other
  )
  throw()
  ;
  
  /// \brief  Read from stream.
  friend
  ::std::istream  &
  operator >>
  ( ::std::istream  & is
  , number          & x
  )
  ;
  
  /// \brief  Write to stream.
  friend
  ::std::ostream  &
  operator <<
  ( ::std::ostream  & is
  , number const    & z
  )
  ;
  
}
;

number::
number
()
{ m_d.resize(1);
  m_d.at(0) = 0;
}


number::
number
( int  d
)
{ bool  ok;
  ok = ( (0<=d) && (1000 >d)  );
  if( !ok)
  { ::std::logic_error  exc("base 1000 digit expected.");
    throw  exc;
  }
  m_d.resize(1);
  m_d.at(0) = d;
}

number::
number
( number const  & other
)
{ ::std::vector < unsigned >  d(other.m_d);
  d.swap(m_d);
}

number &
number::
operator +=
( number const  & other
)
{ ::std::vector < unsigned >  s;
  ::std::vector < unsigned > const  & a = m_d;
  ::std::vector < unsigned > const  & b = other.m_d;
  ::std::size_t  const na = a.size();
  ::std::size_t  const nb = b.size();
  unsigned  t = 0;
  ::std::size_t  i;
  unsigned  w;
  for(i=0; (na > i) || (nb > i) || (0<t); ++i)
  { w = (t + ((na > i) ? a.at(i) : 0) + ((nb > i) ? b.at(i) : 0)  );
    s.push_back(w % 1000);
    t = w / 1000;
  }
  
  s.swap(m_d);
  return ( *this);
}

bool
number::
operator >=
( number const  & other
)
const
throw()
{ ::std::vector < unsigned > const  & a = m_d;
  ::std::vector < unsigned > const  & b = other.m_d;
  ::std::size_t  const na = a.size();
  ::std::size_t  const nb = b.size();
  
  if(na > nb)
  { return true;
  }
  
  if(na < nb)
  { return false;
  }
  
  ::std::size_t  i;
  for(i=na; 0<i; --i)
  { if(a.at(i-1) > b.at(i-1)  )
    { return true;
    }
    
    if(a.at(i-1) < b.at(i-1)  )
    { return false;
    }
  }
  
  return true;
}

void
number::
swap
( number  & other
)
throw()
{ m_d.swap(other.m_d);
}


::std::istream  &
operator >>
( ::std::istream  & is
, number          & x
)
{ ::std::string  s;
  is >> s;
  ::std::size_t  n = s.size();
  ::std::vector < unsigned >  a;
  unsigned  d;
  while(0<n)
  { d = 0;
    d = (s.at(n-1) - '0');
    --n;
    if(0<n)
    { d += 10*(s.at(n-1) - '0');
      --n;
    }
    if(0<n)
    { d += 100*(s.at(n-1) - '0');
      --n;
    }
    a.push_back(d);
  }
  
  // no-throw, no-fail
  a.swap(x.m_d);
  return is;
}

::std::ostream  &
operator <<
( ::std::ostream  & os
, number const    & z
)
{ ::std::vector < unsigned > const  & d = z.m_d;
  ::std::size_t  n = d.size();
  unsigned  x = d.at(n-1);
  if(100 <= x)
  { os << x/100;
    os << (x%100)/10;
    os << (x%10);
  }
  else
  { if(10<=x)
    { os << x/10;
    }
    os << x%10;
  }
  
  ::std::size_t  i;
  for(i=n-1; 0<i; --i)
  { x = d.at(i-1);
    os << x/100;
    os << (x%100)/10;
    os << x%10;
  }
  
  return os;
}

// ___________________________________________________________________________

/// \brief  The instance.
class Pavare2
{ public:
  
  /// \brief  N.
  ::std::size_t  m_N;
  
  /// \brief  A.
  ::std::size_t  m_A;
  
  /// \brief  B.
  ::std::size_t  m_B;
  
  /// \brief  The rank.
  number  m_K;
  
  /// \brief  C[i][b] ― the count/number of coverings of the street 1..i with
  ///                   bricks of type 0 or 1, and brick at position i of
  ///                   type b.   Type 0 is white brick.    Type 1 is black.
  number  m_C[1+maxn][2];
  
  /// \brief  The covering with rank k.
  ::std::size_t  m_X[2+maxn];
  
}
;


// ___________________________________________________________________________

/// \brief  Loads/reads the instance/{problem data}  from file.
class LoadProcessing
{ public:
  
  /// \brief  Defines processing.
  static
  bool
  process
  ( Pavare2  & context
  )
  ;

}
;

bool
LoadProcessing::
process
( Pavare2  & context
)
{ ::std::ifstream  is("pavare2.in");
  
  
  ::std::size_t  N;
  ::std::size_t  A;
  ::std::size_t  B;
  number  K;
  
  is >> N >> A >> B >> K;
  
  ::std::size_t  & refN = context.m_N;
  ::std::size_t  & refA = context.m_A;
  ::std::size_t  & refB = context.m_B;
  number  & refK = context.m_K;
  
  refN = N;
  refA = A;
  refB = B;
  refK.swap(K);
  return true; // Success.
}


// ___________________________________________________________________________

/// \brief  Counts all coverings/configurations.
class CountProcessing
{ public:
  
  /// \brief  Defines processing.
  static
  void
  process
  ( Pavare2  & context
  )
  ;
  
}
;

void
CountProcessing::
process
( Pavare2  & context
)
{ ::std::size_t  & refN = context.m_N;
  ::std::size_t  const N = refN;
  
  ::std::size_t  & refA = context.m_A;
  ::std::size_t  const A = refA;
  
  ::std::size_t  & refB = context.m_B;
  ::std::size_t  const B = refB;
  
  ::std::size_t  L[2] = {A, B};
  
  number  ( &C)[1 + maxn][2] = context.m_C;
  
  C[0][0] = 1;
  C[0][1] = 1;
  ::std::size_t  i;
  ::std::size_t  b;
  ::std::size_t  s;
  number  r;
  for(i=1; N>=i; ++i)
  { for(b=0; 2>b; ++b)
    { r = 0;
      for(s=1; ( (i>=s) && (L[b] >= s)  ); ++s)
      { r += C[i-s][1-b];
      }
      C[i][b] = r;
    }
  }
}

// __________________________________________________________________________

/// \brief  Unranks.
class UnrankProcessing
{ public:
  
  /// \brief  Defines processing.
  static
  void
  process
  ( Pavare2  & context
  )
  ;
  
}
;

void
UnrankProcessing::
process
( Pavare2  & context
)
{ ::std::size_t  & refA = context.m_A;
  ::std::size_t  const A = refA;
  ::std::size_t  & refB = context.m_B;
  ::std::size_t  const B = refB;
  ::std::size_t  L[2] = {A, B};
  number  ( &C)[1+maxn][2] = context.m_C;
  number  ( &K) = context.m_K;
  ::std::size_t  & refN = context.m_N;
  ::std::size_t  const N = refN;
  ::std::size_t  ( & p)[2+maxn] = context.m_X; 
  ::std::size_t  r = 0;
  number  u = 0;
  number  w;
  ::std::size_t  i = 1;
  p[0] = 1;
  while(N>=i)
  { while( (N>=i) && (L[1] > r)  )
    { w  = u;
      w += C[N-i+1][0];
      if(w >= K)
      { break;
      }
      
      w.swap(u);
      p[i] = 1;
      ++i;
      ++r;
    }
    
    r = 0;
    while( (N>=i) && (L[0] > r)  )
    { p[i] = 0;
      ++i;
      ++r;
    }
    while(0<r)
    { --i;
      --r;
      w  = u;
      w += C[N-i][1];
      if(w >= K)
      { break;
      }
      
      w.swap(u);
    }
   
    ++i; 
    p[i] = 1;
    r = 1;
    ++i;
  }
  
}

// __________________________________________________________________________

/// \brief  Writes answer.
class StoreProcessing
{ public:
  
  /// \brief  Writes answer.
  static
  bool
  process
  ( Pavare2  & context
  )
  ;
}
;

bool
StoreProcessing::
process
( Pavare2  & context
)
{ ::std::ofstream  os("pavare2.out");
  
  ::std::size_t const  & refN = context.m_N;
  ::std::size_t  const N = refN;
  
  number  ( &C)[1+maxn][2] = context.m_C;
  number  m;
  m  = C[N][0];
  m += C[N][1];
  os << m;
  os << '\n';
  
  ::std::size_t  ( &X)[2+maxn] = context.m_X;
  
  ::std::size_t  i;
  for(i=1; N>=i; ++i)
  { os << X[i];
  }
  os << '\n';
  
  return true; // Success.
}

// __________________________________________________________________________

/// \brief  Solution.
class Pavare2Processing
{ public:
  
  /// \brief  Defines processing.
  static
  bool
  process
  ()
  ;
  
}
;


bool
Pavare2Processing::
process
()
{ bool  ok;
  
  Pavare2  context;
  
  ok = LoadProcessing::process(context);
  if( !ok)
  { return false; } // Failure.   The called logged.
  
  CountProcessing::process(context);
  UnrankProcessing::process(context);
  
  ok = StoreProcessing::process(context);
  if( !ok)
  { return false; } // Failure.   The called logged.
  
  return true; // Success.
}


int
main
()
{ int  status;
  try
  { bool  const ok = Pavare2Processing::process();
    status = ( ok ? 0 : 1 );
  }
  catch ( ... )
  { status = 2;
  }
  return status;
}