#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
  static char line[80];

  while (fgets(line, 80, stdin)) {
    char *p = strtok(line, " ");

    if (p) {
      if (strcmp(p, "F") == 0) {
        unsigned long n = 0;
        p = strtok(NULL, " \r\n");
        p += strlen(p);

        unsigned long a = 1, b = 1, c;
        while (*--p) {
          if (*p == '1') n += b;

          // a,b = a+b,a
          c = a+b;
          b = a;
          a = c;
        }

        printf("%lu\n", n);

      } else {
        unsigned long n = strtoul(strtok(NULL, " \r\n"), NULL, atoi(p));

        unsigned long a = 1, b = 1, c;
        size_t i = 0;

        while (a <= n) {
          c = a+b;
          b = a;
          a = c;
          i++;
        }

        char buf[i+1];
        i = 0;

        while (b > 0) {
          if (b <= n) {
            buf[i++] = '1';
            n -= b;
          } else {
            buf[i++] = '0';
          }

          c = a-b;
          a = b;
          b = c;
        }

        buf[i] = '\0';

        p = buf;
        while (*p) {
          if (!strncmp(p, "100", 3)) {
            strncpy(p, "011", 3);
          }
          p++;
        }

        if (i >= 4) {
          p = buf+i-4;
          if (!strncmp(p, "1010", 4)) {
            strncpy(p, "0111", 4);
          }
        }

        p = buf+i;
        while (p > buf) {
          p--;
          if (!strncmp(p, "100", 3)) {
            strncpy(p, "011", 3);
          }
        }

        printf("%s\n", buf + strspn(buf, "0"));
      }
    }
  }

  return 0;
}