#include <algorithm>
#include <cstring>
#include <experimental/functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using ii = __uint128_t;

ii fib(ii n) {
  static auto known = std::unordered_map<__uint64_t, ii>{{0,0}, {1,1}, {2,1}};
  auto it = known.find(n);
  if (it != known.end())
    return it->second;

  if (n & 1) {
    ii k = (n+1)/2, fk = fib(k), fk1 = fib(k-1);
    return fk*fk + fk1*fk1;
  } else {
    ii k = n/2, fk = fib(k);
    return (2*fib(k-1) + fk)*fk;
  }
}

ii fibsum3(ii n) {
  return fib(n+6) - (n+5) - (n+2)*(n+3)/2;
}

class ascii_coded_decimals {
  char _n[128] = {0};
  char* _begin = std::end(_n) - 2;
  char* _end = std::end(_n) - 2;

public:
  ascii_coded_decimals() {
    *_begin = '1';
  }
  ascii_coded_decimals(const std::string& init) {
    _begin = std::copy_backward(init.cbegin(), init.cend(), _begin+1);
  }
  ascii_coded_decimals(ii n) {
    do {
      *_begin = "0123456789"[n % 10];
      n /= 10;
      --_begin;
    } while (n);
    ++_begin;
  }
  ascii_coded_decimals& operator ++() {
    char *p = _end;
    bool carry = true;
    while (carry && p > _n) {
      char c = *p;
      if (c) {
        ++c;
        carry = c > '9';
        if (carry)
          c = '0';
        *p = c;
      } else {
        *p = '1';
        carry = false;
      }

      --p;
    }

    if (p < _begin)
      _begin = p + 1;

    return *this;
  }
  const char* cbegin() const { return _begin; }
  const char* cend() const { return _end; }
  const char* cstr() const { return _begin; }
  size_t size() const { return _end - _begin + 1; }
};

void main14() {
  const std::vector<std::string> xs{
    "0", "1", "4", "25", "97", "9226935",
  };

  auto n = ascii_coded_decimals("2660000000");
  ii count = 43230504ULL;
  for(ii i = 0; i<10000000ULL; ++i) {
    std::string nstr{n.cstr(), n.size()};
    count += std::none_of(xs.cbegin(), xs.cend(), [&](const auto& x) -> auto {
        return nstr.find(x) != std::string::npos;
      });

    if (i % 10000000ULL == 0ULL || count == 103371362ULL) {
      std::cout << n.cstr() << "\t"
                << ascii_coded_decimals(count).cstr() << std::endl;
      if (count == 103371362ULL)
        break;
    }

    ++n;
  }
}

/*
void main17() {
  auto xs = std::vector< std::experimental::boyer_moore_searcher<const char*> >{};
  for (const char* x : {"0", "1", "4", "25", "97", "9226935"}) {
    auto searcher = std::experimental::make_boyer_moore_searcher<const char*>(x, x + std::strlen(x));
    xs.emplace_back(std::move(searcher));
  }

  auto n = ascii_coded_decimals("2660000000");
  ii count = 43230504ULL;
  for(ii i = 0; i<10000000ULL; ++i) {
    auto nstr = std::string{n.cstr(), n.size()};
    count += std::none_of(xs.cbegin(), xs.cend(), [&](auto x) -> auto {
      });

    if (i % 1000000ULL == 0ULL || count == 103371362ULL) {
      std::cout << n.cstr() << "\t"
                << ascii_coded_decimals(count).cstr() << std::endl;
      if (count == 103371362ULL)
        break;
    }

    ++n;
  }
}
*/

int main() { main14(); }