#define NDEBUG 1
//#pragma GCC optimize("O3")
#pragma GCC target("avx")
//#pragma GCC optimize("unroll-loops")

#define FOR(i, s, e) for(auto i = (s); i < (e); ++i)
#define REP(i, e) FOR(i, decltype(e)(), (e))
#define ALL(x) (std::begin(x)),(std::end(x))

#ifndef MOD
#define MOD 1000000007
#endif // ! MOD

#include <cstdint>
#include <cstddef>
#include <limits>

#if __cplusplus > 201703L && __cpp_concepts >= 201907L
#include <concepts>
#else
#include <type_traits>
#define NO_CONCEPT
#endif // __has_include(<concepts>)

#include <iterator>
#include <utility>
#include <algorithm>
#include <initializer_list>
#include <tuple>
#include <string_view>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <list>
#include <stack>
#include <queue>

namespace nlib {
#ifdef NO_CONCEPT
  template <class T, class U> struct is_super_type : std::conjunction<std::is_same<std::common_type_t<T, U>, T>, std::is_same<std::common_type_t<T, U>, std::common_type_t<U, T>>> {};
  template <class T, class U> inline constexpr bool is_super_type_v = is_super_type<T, U>::value;
#else
  template <class T, class U>
  concept super_type = std::same_as<std::common_type_t<T, U>, T> && std::same_as<std::common_type_t<U, T>, T>;
#endif // NO_CONCEPT

  namespace {
    using swallow = std::initializer_list<int>;
  } // namespace

  using uint = unsigned;
  using ll = long long;
  using ull = unsigned long long;
  using ld = long double;

  template <class T> using vector = std::vector<T>;
  template <class T> using deque = std::deque<T>;
  template <class T> using unordered_set = std::unordered_set<T>;
  template <class T, class U> using unordered_map = std::unordered_map<T, U>;
  template <class T> using forward_list = std::forward_list<T>;
  template <class T> using list = std::list<T>;
  template <class T, class Container = deque<T>> using stack = std::stack<T, Container>;
  template <class T, class Container = deque<T>> using queue = std::queue<T, Container>;
  template <class T, class Container = vector<T>, class Compare = std::less<typename Container::value_type>> using priority_queue = std::priority_queue<T, Container, Compare>;
  template <class T, size_t n> using array = std::array<T, n>;
  using string = std::string;
  using string_view = std::string_view;

  
  template <class T> using vecvec = vector<vector<T>>;

  using vi = vector<int>;
  template <size_t n> using ai = array<int, n>;
  template<class T> using vvi = vecvec<int>;
  template <size_t n> using vai = vector<array<int, n>>;
  template <size_t n, size_t m = n> using aai = array<array<int, m>, n>;

  using vl = vector<ll>;
  template <size_t n> using al = array<ll, n>;
  using vvl = vecvec<ll>;
  template <size_t n> using val = vector<array<ll, n>>;
  template <size_t n, size_t m = n> using aal = array<array<ll, m>, n>;

  using vs = vector<string>;
  template <size_t n> using as = array<string, n>;
  template <size_t n> using asv = array<string_view, n>;

  using namespace std::literals;

  inline constexpr string_view alnums = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"sv;
  inline constexpr string_view digits = alnums.substr(0, 10);
  inline constexpr string_view l_alphas = alnums.substr(10, 26);
  inline constexpr string_view g_alphas = alnums.substr(36, 26);
  inline constexpr string_view alphas = alnums.substr(10, 52);

  inline constexpr auto mod = MOD;
} // namespace nlib

#include <cmath>

namespace nlib {
  template <class T = int, class U = ll, T m = mod>
  class mod_int {
    T _value;
  public:
    static constexpr T mod = m;
    // TODO
    /*
    static constexpr mod_int get_inverse(T v) {
      
    }
    constexpr mod_int& inverse() {
      value = get_inverse(value);
      return *this;
    }
    */
    constexpr mod_int() noexcept = default;
    constexpr mod_int(const mod_int& v) noexcept = default;
    constexpr mod_int(mod_int&& v) noexcept = default;

    constexpr mod_int(const T& v) noexcept: _value(static_cast<T>(v) % mod) {
      if(_value < 0) _value += mod;
    }

#ifdef NO_CONCEPT
    template<class X, class = std::enable_if_t<!is_super_type_v<T, X>>>
#else
    template<class X> requires (!super_type<T, X>)
#endif // ! NO_CONCEPT
    constexpr mod_int(const X& v) noexcept: _value(static_cast<T>(v % static_cast<X>(mod))) {
      if(_value < 0) _value += mod;
    }
#if __cplusplus > 201703L
    constexpr
#endif // c++2a
    ~mod_int() noexcept = default;
    constexpr operator T() const noexcept {return _value;}

#define DEFOP(op) constexpr mod_int& operator op noexcept
    DEFOP(=(const mod_int& v) &) = default;
    DEFOP(=(mod_int&& v) &) = default;
    DEFOP(++()) {
      if(_value == std::numeric_limits<mod_int>::max()) _value = 0;
      else ++_value;
      return *this;
    }
    DEFOP(--()) {
      if(_value == 0) _value = std::numeric_limits<mod_int>::max();
      else --_value;
      return *this;
    }
    DEFOP(+=(const mod_int& v)) {
      if((_value += v._value) >= mod) _value -= mod;
      return *this;
    }
    DEFOP(-=(const mod_int& v)) {
      if((_value -= v._value) < 0) _value += mod;
      return *this;
    }
    DEFOP(*=(const mod_int& v)) {
      _value = static_cast<T>((static_cast<U>(_value) * static_cast<U>(v._value)) % static_cast<U>(mod));
      return *this;
    }
    DEFOP(/=(const mod_int& v)) {
      return *this *= inverse(v._value);
    }
    DEFOP(%=(const mod_int& v)) {
      return *this %= v._value;
    }
#undef DEFOP

#define DEFOP(op) constexpr mod_int operator op noexcept
    DEFOP(++(int)) {mod_int v = *this; ++(*this); return v;}
    DEFOP(--(int)) {mod_int v = *this; --(*this); return v;}
    DEFOP(+() const) {return *this;}
    DEFOP(-() const) {mod_int mint; if(_value) mint._value = mod - _value; return mint;}
#undef DEFOP

    explicit constexpr operator bool() const noexcept {return _value;}
    constexpr bool operator!() const noexcept {return !_value;}

#define MINT_T class X, class Y, X x
#define MINT mod_int<X, Y, x>

#define TEMPL template <MINT_T>

#ifdef NO_CONCEPT
#define TEMPL_CONV template <MINT_T, class I>
#else
#define TEMPL_CONV template <MINT_T, class I> requires (std::convertible_to<I, MINT>)
#endif // NO_CONCEPT

#ifdef NO_CONCEPT
#define CONV_R(...) std::enable_if_t<std::is_convertible_v<I, MINT>, __VA_ARGS__>
#else
#define CONV_R(...) __VA_ARGS__
#endif // NO_CONCEPT

#define DECOP(r, op)                                                    \
    TEMPL friend constexpr r operator op(const MINT&, const MINT&) noexcept; \
    TEMPL_CONV friend constexpr CONV_R(r) operator op(const MINT&, const I&) noexcept; \
    TEMPL_CONV friend constexpr CONV_R(r) operator op(const I&, const MINT&) noexcept;

    DECOP(MINT, +)
    DECOP(MINT, -)
    DECOP(MINT, *)
    DECOP(MINT, /)
    DECOP(MINT, %)
    DECOP(bool, ==)
    DECOP(bool, !=)
    DECOP(bool, <)
    DECOP(bool, >)
    DECOP(bool, <=)
    DECOP(bool, >=)

#undef DECOP
#undef MINT
  };
} // namespace nlib

#define MINT nlib::mod_int<X, Y, x>

#define DEFOP(ret, op, exp0, exp1, exp2)                                     \
  TEMPL constexpr ret operator op(const MINT& l, const MINT& r) noexcept {return exp0;} \
  TEMPL_CONV constexpr CONV_R(ret) operator op(const MINT& l, const I& r) noexcept {return exp1;} \
  TEMPL_CONV constexpr CONV_R(ret) operator op(const I& l, const MINT& r) noexcept {return exp2;}

#define DEFOP_A(op) DEFOP(MINT, op, MINT(l) op##= r, MINT(r) op##= l, MINT(l) op##= r)
DEFOP_A(+)
DEFOP_A(-)
DEFOP_A(*)
DEFOP_A(/)
DEFOP_A(%)
#undef DEFOP_A

#define DEFOP_C(op) DEFOP(bool, op, l._value op r._value, l._value op MINT(r)._value, MINT(l)._value op r._value)
DEFOP_C(==)
DEFOP_C(!=)
DEFOP_C(<)
DEFOP_C(>)
DEFOP_C(<=)
DEFOP_C(>=)
#undef DEFOP_C

#undef DEFOP
#undef CONV_R
#undef TEMPL_CONV

namespace std {
  TEMPL struct is_integral<MINT> : true_type {};
  TEMPL struct is_signed<MINT> : false_type {};

  TEMPL struct numeric_limits<MINT> : numeric_limits<X> {
    static constexpr MINT min() noexcept {return 0;}
    static constexpr MINT lowest() noexcept {return 0;}
    static constexpr MINT max() noexcept {return x - 1;}
    static constexpr int digits10 = std::floor(std::log10<X>(static_cast<X>(max())));
    static constexpr bool is_signed = false;
    static constexpr bool is_modulo = true;
  };
} // namespace std

#undef MINT
#undef TEMPL
#undef MINT_T

#include <unistd.h>
#include <cstring>
#include <cmath>

namespace nlib {
#ifndef NO_CONCEPT
  template <class T> concept integer_class = std::integral<T> && !std::same_as<T, char> && !std::same_as<T, bool>;

  template <class T> concept container_input_or_output = requires(const T x) {
    std::begin(x);
    std::end(x);
    requires std::sentinel_for<decltype(std::end(x)), decltype(std::begin(x))>;
  };

  template <class T> concept container_forward = container_input_or_output<T> && requires(const T x) {
    {std::begin(x)} -> std::forward_iterator;
  };

  template <class T> concept container_output = container_input_or_output<T> && requires(T x) {
    requires std::output_iterator<decltype(std::begin(x)), typename std::iterator_traits<decltype(std::begin(x))>::value_type>;
  };

  template <class T> concept string_output = container_input_or_output<T> && requires(T& x, const char* s, const char* e) {
    requires std::same_as<typename std::iterator_traits<decltype(std::begin(x))>::value_type, char>;
    {x.clear()} noexcept;
    x.insert(std::end(x), s, e);
  };

  template <class T> concept string_input = requires(T& x) {
    {std::data(x)} noexcept -> std::convertible_to<const char*>;
    {std::size(x)} noexcept -> std::convertible_to<size_t>;
  };

  template <class... Args> concept noonly_one = requires() {
    requires sizeof...(Args) != 1;
  };
#endif // NO_CONCEPT

  inline constexpr char endl = '\n';
  inline constexpr char wspc = ' ';

  class reader {
  public:
    static constexpr size_t max_size = 4096;
  private:
    char buf[max_size];
    size_t buf_size = 0, pt = 0;
    int fd = -1;

  public:
    reader() noexcept = default;
    reader(const reader&) = delete;
    reader(reader&&) noexcept = default;
    reader(int open_fd) noexcept : fd(open_fd) {}

    reader& operator=(const reader&) noexcept = delete;
    reader& operator=(reader&&) noexcept = default;

    void open(int open_fd) noexcept {
      if(fd != -1) fd = open_fd;
    }

    size_t read(char* str, size_t size) noexcept {
      ssize_t s = ::read(fd, str, size);
      return s == -1 ? 0 : size_t(s);
    }

    bool check() noexcept {return pt >= buf_size && reread();}
    bool reread() noexcept {if(buf_size >= max_size) {buf_size = 0;} pt = buf_size; buf_size += read(buf, max_size - pt); return buf_size == pt;}
    size_t size() const noexcept {return buf_size - pt;}
    bool getc(char& c) noexcept {if(check()) {return true;} c = buf[pt++]; return false;}

    template <class T>
#ifdef NO_CONCEPT
    auto
#else
    requires string_output<T> bool
#endif // NO_CONCEPT
    getline(T& s) noexcept
# ifdef NO_CONCEPT
      -> decltype(std::begin(s), std::end(s), (s).clear(), s.insert(std::end(s), buf + pt, buf + pt), *this)
# endif // NO_CONCEPT
    {
      s.clear();
      if(check()) return true;
      size_t p = pt;
      for(;;) {
        if(p == buf_size) {
          s.insert(std::end(s), buf + pt, buf + p);
          if(buf_size != max_size || reread()) return true;
          p = 0;
        } else if(buf[p] == endl) {
          s.insert(std::end(s), buf + pt, buf + p);
          pt = p + 1;
          return false;
        }
        ++p;
      }
    }

    bool readspace() noexcept {
      if(check()) return true;
      while(buf[pt] == wspc || buf[pt] == endl) {
        ++pt;
        if(pt == buf_size && (buf_size != max_size || reread())) return true;
      }
      return false;
    }

#ifndef NO_SCAN
    reader& scan(char& c) noexcept {if(getc(c)) c = '\0'; return *this;}

    template <class T>
# ifdef NO_CONCEPT
    std::enable_if_t<std::is_integral_v<T> && (!std::is_same_v<T, char>) && (!std::is_same_v<T, bool>), reader&>
# else
    requires integer_class<T> reader&
# endif // NO_CONCEPT
    scan(T& n) noexcept {
      constexpr T ten = 10;
      n = T();
      if(readspace()) return *this;

      bool sign = false;
      switch(buf[pt]) {
      case '-':
        sign = true;
        [[fallthrough]];
      case '+':
        ++pt;
        if(check()) return *this;
      }

      while('0' <= buf[pt] && buf[pt] <= '9') {
        n *= ten;
        n += T(buf[pt++] - '0');
        if(check()) goto end;
      }
    end:
      if(sign) n = -n;
      return *this;
    }

    template <class T>
# ifdef NO_CONCEPT
    std::enable_if_t<std::is_floating_point_v<T>, reader&>
# else
    requires std::floating_point<T> reader&
# endif // NO_CONCEPT
    scan(T& n) noexcept {
      constexpr T ten = 10;
      n = T();
      if(readspace()) return *this;

      bool sign = false;
      switch(buf[pt]) {
      case '-':
        sign = true;
        [[fallthrough]];
      case '+':
        ++pt;
        if(check()) return *this;
      }

      while('0' <= buf[pt] && buf[pt] <= '9') {
        n *= ten;
        n += T(buf[pt++] - '0');
        if(check()) goto end;
      }

      if(buf[pt] == '.') {
        ++pt;
        if(check()) goto end;
        T pow10 = 1;
        while('0' <= buf[pt] && buf[pt] <= '9') {
          pow10 *= ten;
          if(std::isinf<T>(pow10)) {
            do {
              ++pt;
            } while(!check() && '0' <= buf[pt] && buf[pt] <= '9');
            goto end;
          }
          n += T(buf[pt++] - '0') / pow10;
          if(check()) goto end;
        }
      }
    end:
      if(sign) n = -n;
      return *this;
    }

    template <class C>
# ifdef NO_CONCEPT
    auto
# else
    requires (container_output<C> && !string_output<C>) reader&
# endif // NO_CONCEPT
      scan(C& v) noexcept
# ifdef NO_CONCEPT
      -> decltype(std::begin(v), std::end(v), *this)
# endif // NO_CONCEPT
    {for(auto& e : v) scan(e); return *this;}

    template <class T, size_t N>
# ifdef NO_CONCEPT
    std::enable_if_t<is_super_type_v<char, T>, reader&>
# else
    requires (!string_output<T[N]>) reader&
# endif // NO_CONCEPT
      scan(T (&v)[N]) noexcept {for(T& e : v) scan(e); return *this;}

    template <class T>
# ifdef NO_CONCEPT
    auto
# else
    requires string_output<T> reader&
# endif // ! NO_CONCEPT
    scan(T& s) noexcept
# ifdef NO_CONCEPT
      -> std::enable_if_t<!std::is_same_v<std::iterator_traits<decltype(std::begin(s))>::value_type, char>,
                          decltype(std::end(s), (s).clear(), s.insert(std::end(s), buf + pt, buf + pt), *this)>
# endif // NO_CONCEPT
    {
      s.clear();
      if(check()) return *this;
      size_t p = pt;
      for(;;) {
        if(p == buf_size) {
          s.insert(std::end(s), buf + pt, buf + p);
          if(buf_size != max_size || reread()) return *this;
          p = 0;
        } else if(buf[p] == wspc || buf[p] == endl) {
          s.insert(std::end(s), buf + pt, buf + p);
          pt = p + 1;
          return *this;
        }
        ++p;
      }
      return *this;
    }

    template <class... Args>
# ifdef NO_CONCEPT
    std::enable_if_t<sizeof...(Args) != 1, reader&>
# else
    requires noonly_one<Args...> reader&
# endif // NO_CONCEPT
    scan(Args&... args) noexcept {(void)swallow{(scan(args), 0)...}; return *this;}
#endif // ! NO_SCAN
  };

#ifndef UNSET_STDIN
  reader rd(0);
# ifndef NO_SCAN
  template <class... Args> reader& scan(Args&... args) noexcept {return rd.scan(args...);}
  template <class T> T get_v() noexcept {T x; scan(x); return x;}
  template <class T> T&& get_v(T&& x) noexcept {scan(x); return std::move(x);}
# endif // ! NO_SCAN
#endif // ! UNSET_STDIN

  class writer {
  public:
    static constexpr size_t max_size = 4096;
  private:
    char buf[max_size];
    size_t pt = 0;
    int fd = -1;
#ifndef NO_PRINT
    bool iscontinued = false;
#endif // ! NO_PRINT
  public:
    writer() noexcept = default;
    writer(const writer&) = delete;
    writer(writer&&) noexcept = default;
    writer(int open_fd) noexcept : fd(open_fd) {}

    ~writer() noexcept {write(buf, pt);}

    writer& operator=(const writer&) = delete;
    writer& operator=(writer&&) & noexcept = default;

    void write(const char* str, size_t size) noexcept {
      ::write(fd, str, size);
    }

    void flush() noexcept {
      write(buf, pt);
      pt = 0;
    }

    void reopen(int open_fd) noexcept {
      if(pt) flush();
      fd = open_fd;
    }

    void check() noexcept {
      if(pt >= max_size) {
        write(buf, max_size);
        pt = 0;
      }
    }

    void putc(const char& c) noexcept {buf[pt] = c;++pt;check();}

    void puts(const char* str, size_t len) noexcept {
      if(!len) return;
      size_t write_size = max_size - pt;
      size_t copy_size = len;
      if(copy_size <= write_size) {
        memcpy(buf + pt, str, copy_size);
        pt += copy_size;
        check();
      } else {
        if(pt) {
          memcpy(buf + pt, str, write_size);
          write(buf, max_size);
        } else {
          write_size = 0;
        }
        if(len > max_size && (copy_size = ((copy_size - write_size) / max_size) * max_size)) {
          write(str + write_size, copy_size);
          write_size += copy_size;
        }

        copy_size = len - write_size;
        memcpy(buf, str + write_size, copy_size);
        pt = copy_size + 1;
      }
    }

    void putcs(char&& ch, size_t len) noexcept {
      if(!len) return;
      size_t write_size = max_size - pt;
      size_t copy_size = len;
      if(copy_size <= write_size) {
        memset(buf + pt, ch, copy_size);
        pt += copy_size;
        check();
      } else {
        if(pt) {
          memset(buf + pt, ch, write_size);
          write(buf, max_size);
        } else {
          write_size = 0;
        }
        if(len > max_size && (copy_size = (copy_size - write_size) / max_size)) {
          memset(buf, ch, max_size - pt);
          REP(i, copy_size) write(buf, max_size);
          write_size += copy_size * max_size;
        }

        copy_size = len - write_size;
        memset(buf, ch, copy_size);
        pt = copy_size + 1;
      }
    }

#ifndef NO_PRINT
    template<bool nonewline = true>
    void writespace() noexcept {
      if(iscontinued) {
        if constexpr(nonewline) putc(wspc);
        else putc(endl);
      }
      iscontinued = nonewline;
    }

    writer& print(const char& c) noexcept {if(c) {if(c == endl) iscontinued = false; putc(c);} else {iscontinued = false;} return *this;}

    template <class T>
# ifdef NO_CONCEPT
    std::enable_if_t<std::is_integral_v<T> && (!std::is_same_v<T, char>) && (!std::is_same_v<T, bool>), writer&>
# else
    requires integer_class<T> writer&
# endif // NO_CONCEPT
    print(T n) noexcept {
      constexpr int len = std::numeric_limits<T>::digits10 + 1;
      constexpr T ten = T(10);
      writespace();

      if constexpr(std::is_signed_v<T>) {
        if(n < 0) {
          putc('-');
          n = -n;
        } else if(!n) {
          putc('0');
          return *this;
        }
      } else {
        if(!n) {
          putc('0');
          return *this;
        }
      }

      char s[len];
      size_t i = len;
      while(n) {
        --i;
        s[i] = char(n % ten) + '0';
        n /= ten;
      }
      puts(s + i, len - i);
      return *this;
    }

    template <class T, class U, T m>
    writer& print(mod_int<T, U, m> n) noexcept {
      return print(static_cast<T>(n));
    }

    template <class T>
# ifdef NO_CONCEPT
    std::enable_if_t<std::is_floating_point_v<T>, writer&>
# else
    requires std::floating_point<T> writer&
# endif // NO_CONCEPT
    print(T n) noexcept {
      constexpr int len = std::numeric_limits<T>::digits10 + 1;
      constexpr T ten = T(10);
      writespace();

      if constexpr(std::is_signed_v<T>) {
        if(n < T()) {
          putc('-');
          n = -n;
        } else if(!n) {
          putc('0');
          return *this;
        }
      } else {
        if(!n) {
          putc('0');
          return *this;
        }
      }

      char s[len];
      int lo = int(std::floor(std::log10(n)));
      int i = 0;
      while(i < len) {
        int a;
        n = std::remquo(n, std::pow<T>(ten, lo - i), &a);
        if(a < 0) {
          a += 10;
          --s[i - 1];
        }
        s[i] = std::move(a) + '0';
        ++i;
      }

      if(lo >= 0) {
        ++lo;
        if(lo < len) {
          puts(s, lo);
          putc('.');
          puts(s + lo, len - lo);
        } else {
          puts(s, len);
          lo -= len;
          if(lo) putcs('0', lo);
        }
      } else {
        putc('0'),putc('.');
        putcs('0', -lo);
        puts(s, len);
      }
      return *this;
    }

    template <class C>
# ifdef NO_CONCEPT
    auto
#else
    requires (container_forward<C> && !string_input<C>) writer&
# endif // ! NO_CONCEPT
      print(const C& v) noexcept
# ifdef NO_CONCEPT
      -> decltype(std::begin(v), std::end(v), *this)
# endif // NO_CONCEPT
    {for(const auto& e : v) print(e); return *this;}

    template <class T, size_t N>
# ifdef NO_CONCEPT
    std::enable_if_t<!std::is_same_v<T, char>, writer&>
# else
    requires (!string_input<T[N]>) writer&
# endif // NO_CONCEPT
      print(const T (&v)[N]) noexcept {for(const T& e : v) print(e); return *this;}

    template <class T>
# ifdef NO_CONCEPT
    auto
#else
    requires string_input<T> writer&
# endif // NO_CONCEPT
    print(const T& s) noexcept
# ifdef NO_CONCEPT
      -> decltype(static_cast<const char*>(std::data(s)), static_cast<size_t>(std::size(s)), *this)
# endif // NO_CONCEPT
    {
      const char* const ptr = std::data(s);
      const size_t len = std::size(s);
      if(len == 0 || (len == 1 && !(*ptr))) {
        iscontinued = false;
        return *this;
      }
      puts(ptr, len);
      if(*(ptr + len - 1) == endl) {
        iscontinued = false;
      }
      return *this;
    }

    template <class T1, class T2>
    writer& print(std::pair<T1, T2>&& p) noexcept {
      print(std::forward<T1>(p.first)), print(std::forward<T2>(p.second));
      return *this;
    }

    template <class... Args>
    writer& print(std::tuple<Args...>&& t) noexcept {
      return std::apply(print, std::forward<std::tuple<Args...>>(t));
    }

    template <class... Args>
# ifdef NO_CONCEPT
    std::enable_if_t<sizeof...(Args) != 1, writer&>
# else
    requires noonly_one<Args...> writer&
# endif // NO_CONCEPT
    print(Args&&... args) noexcept {(void)swallow{(print(std::forward<Args>(args)), 0)...}; return *this;}

    template <class... Args>
    writer& println(Args&&... args) noexcept {writespace<false>(); print(std::forward<Args>(args)...); writespace<false>(); return *this;}
#endif // ! NO_PRINT
  };

#ifndef UNSET_STDOUT
  writer wt(1);
# ifndef NO_PRINT
  template <class... Args> writer& print(Args&&... args) noexcept {return wt.print(std::forward<Args>(args)...);}
  template <class... Args> writer& println(Args&&... args) noexcept {return wt.println(std::forward<Args>(args)...);}
# endif // ! NO_PRINT

# ifndef NDEBUG
  writer errwt(2);

#  ifndef NO_PRINT
  template <class... Args> void dprint(Args&&... args) noexcept {errwt.print(std::forward<Args>(args)...).flush();}
  template <class... Args> void dprintln(Args&&... args) noexcept {errwt.println(std::forward<Args>(args)...).flush();}
#  endif // ! NO_PRINT

# else

#  ifndef NO_PRINT
  template <class... Args> void dprint(Args&&...) noexcept {}
  template <class... Args> void dprintln(Args&&...) noexcept {}
#  endif // ! NO_PRINT

# endif // ! NDEBUG
#endif // ! UNSET_STDOUT
} // namespace nlib

#include <numeric>
#include <cmath>

namespace nlib {
#ifndef NO_CONCEPT
  template <class T> concept lessthan = requires(const T a, const T b) {
    a < b;
  };
#endif // ! NO_CONCEPT

  template <class T>
#ifndef NO_CONCEPT
  requires std::unsigned_integral<T>
#endif // ! NO_CONCEPT
  constexpr T combination(T, T);

  template <class T>
#ifndef NO_CONCEPT
  requires lessthan<T>
#endif // ! NO_CONCEPT
  constexpr T& chmin(T& a, const T& b) {if(b < a) a = b; return a;}

  template <class T, class Compare>
#ifndef NO_CONCEPT
  requires std::predicate<Compare, const T&, const T&>
#endif // ! NO_CONCEPT
  constexpr T& chmin(T& a, const T& b, Compare comp) {if(comp(b, a)) a = b; return a;}

  template <class T>
#ifndef NO_CONCEPT
  requires lessthan<T>
#endif // ! NO_CONCEPT
  constexpr T& chmax(T& a, const T& b) {if(a < b) a = b; return a;}
  template <class T, class Compare>
#ifndef NO_CONCEPT
  requires std::predicate<Compare, const T&, const T&>
#endif // ! NO_CONCEPT
  constexpr T& chmax(T& a, const T& b, Compare comp) {if(comp(a, b)) a = b; return a;}

  template <class T>
#ifndef NO_CONCEPT
  requires lessthan<T>
#endif // ! NO_CONCEPT
  constexpr void chminmax(T& a, T& b) {if(b < a) std::swap(a, b);}

  template <class T, class Compare>
#ifndef NO_CONCEPT
  requires std::predicate<Compare, const T&, const T&>
#endif // ! NO_CONCEPT
  constexpr void chminmax(T& a, T& b, Compare comp) {if(comp(b, a)) std::swap(a, b);}

  template <class T>
  class pow_preproc {
    using array_t = T[std::numeric_limits<T>::digits];
    array_t _dp = {};
  public:
    const T base;
    constexpr pow_preproc(T b) : base(b) {
      _dp[0] = b;
      FOR(i, 1, std::numeric_limits<T>::digits) {
        _dp[i] = _dp[i - 1] * _dp[i - 1];
      }
    }
    constexpr T operator[](int x) {
      return x ? _dp[x - 1] : 1;
    }
    constexpr T get_pow(T x) {
      if(x < 0) return 0;
      T y = 1;
      for(int i = 0; x; ++i) {
        if(x % 2) y *= _dp[i];
        x >>= 1;
      }
      return y;
    }
  };

  template <class T, class U, T m, T max>
  class fact_preproc {
  public:
    using value_type = mod_int<T, U, m>;
    static constexpr value_type max_value = max;
  private:
    mod_int<T, U, m> fact[max], inv[max], finv[max];
  public:
  };

  template <class T>
#ifndef NO_CONCEPT
  requires std::integral<T>
#endif // ! NO_CONCEPT
  constexpr T combination(T n, T r) {
    chmin(r, n - r);
    if(r < 0 || n < 0) return 0;
    T x = 1, i = 0;
    while(i < r) x *= (n - i) / (++i);
    return x;
  }

  template <class T, class U, T m>
  constexpr mod_int<T, U, m> combination(mod_int<T, U, m> n, mod_int<T, U, m> r) {
    chmin(r, n - r);
    mod_int<T, U, m> a = 1, d = 1, i = 0;
    while(i < r) {
      a *= n - i;
      d *= ++i;
    }
    return a / d;
  }

  template <size_t s, class T = ull>
  struct bits {
    using value_type = T;
    static constexpr size_t unit_bytes = sizeof(value_type);
    static constexpr size_t unit_bits = unit_bytes * 8;
    static constexpr size_t length = s / unit_bits + (s % unit_bits != 0);
    static constexpr value_type bitmask(size_t id) {return value_type(1) << (id % unit_bits);}

    class reference {
      friend class bits;
      friend class iterator;
      value_type* const _ptr;
      const value_type _mask;
      constexpr reference(value_type* ptr, value_type mask) : _ptr(ptr), _mask(mask) {};
    public:
      explicit constexpr operator bool() const noexcept {return bool(*_ptr & _mask);}
      constexpr bool operator!() const noexcept {return !bool(*this);}
      constexpr reference& operator=(bool b) & noexcept {
        if(b) set();
        else reset();
        return *this;
      }
      constexpr reference& operator=(const reference& b) & noexcept {
        return *this = bool(b);
      }
      constexpr void set() noexcept {*_ptr |= _mask;}
      constexpr void reset() noexcept {*_ptr &= ~_mask;}
      constexpr void flip() noexcept {*this = !(*this);}
    };

    class const_reference {
      friend class bits;
      friend class iterator;
      const value_type* const _ptr;
      const value_type _mask;
      constexpr const_reference(const value_type* ptr, value_type mask) : _ptr(ptr), _mask(mask) {};
    public:
      explicit constexpr operator bool() const noexcept {return bool(*_ptr & _mask);}
      constexpr bool operator!() const noexcept {return !bool(*this);}
      constexpr const_reference& operator=(const reference& b) & = delete;
    };

    class iterator {
      friend class bits;
      friend class reference;
      value_type* _ptr;
      size_t _bit;
      constexpr iterator(value_type* ptr, size_t bit) : _ptr(ptr), _bit(bit) {};
    public:
      constexpr iterator& operator++() {
        if(++_bit == unit_bits) {
          _bit = 0;
          ++_ptr;
        }
        return *this;
      }
      constexpr iterator operator++(int) {iterator i(*this); ++(*this); return i;}
      constexpr iterator& operator--() {
        if(!_bit) {
          _bit = unit_bits;
          --_ptr;
        }
        --_bit;
        return *this;
      }
      constexpr iterator operator--(int) {iterator i(*this); --(*this); return i;}
      constexpr reference operator*() const {return reference(_ptr, value_type(1) << _bit);}
    };

    class const_iterator {
      friend class bits;
      friend class reference;
      const value_type* _ptr;
      size_t _bit;
      constexpr const_iterator(const value_type* ptr, size_t bit) : _ptr(ptr), _bit(bit) {};
    public:
      constexpr const_iterator& operator++() {
        if(++_bit == unit_bits) {
          _bit = 0;
          ++_ptr;
        }
        return *this;
      }
      constexpr const_iterator operator++(int) {iterator i(*this); ++(*this); return i;}
      constexpr const_iterator& operator--() {
        if(!_bit) {
          _bit = unit_bits;
          --_ptr;
        }
        --_bit;
        return *this;
      }
      constexpr const_iterator operator--(int) {iterator i(*this); --(*this); return i;}
      constexpr const_reference operator*() const {return const_reference(_ptr, value_type(1) << _bit);}
    };

    value_type data[length];
    constexpr void set() noexcept {constexpr_fill(std::data(data), length, ~value_type());}
    constexpr void set(size_t id) noexcept {data[id / unit_bits] |= bitmask(id);}
    constexpr void reset() noexcept {constexpr_fill(std::data(data), length, value_type());}
    constexpr void reset(size_t id) noexcept {data[id / unit_bits] &= ~bitmask(id);}
    constexpr void set(size_t id, bool b) noexcept {if(b) set(id); else reset(id);}
    constexpr bool get(size_t id) const noexcept {return bool(data[id / unit_bits] & bitmask(id));}
    constexpr void flip() noexcept {REP(i, length) data[i] = ~data[i];}
    constexpr bool operator[](size_t id) const noexcept {return get(id);}
    constexpr reference operator[](size_t id) noexcept {return reference(data + id / unit_bits, bitmask(id));}
    constexpr size_t size() const noexcept {return s;}
    constexpr iterator begin() noexcept {return iterator(data, 0);}
    constexpr const_iterator begin() const noexcept {return const_iterator(data, 0);}
    constexpr iterator end() noexcept {return iterator(data + size() / unit_bits, size() % unit_bits);}
    constexpr const_iterator end() const noexcept {return const_iterator(data + size() / unit_bits, size() % unit_bits);}
    constexpr const_iterator cbegin() const noexcept {return const_iterator(data, 0);}
    constexpr const_iterator cend() const noexcept {return const_iterator(data + size() / unit_bits, size() % unit_bits);}
  };
} // namespace nlib

using namespace nlib;

template<class T = ll, class U = double>
T root(T a, T x) {
  T y = std::floor(std::pow(U(x), 1./U(a)));
  T pow_v = pow_preproc<T>(y).get_pow(a);
  dprint(pow_v);
  if(pow_v == x) {
    return y;
  } else if(pow_v < x) {
    do {
      ++y;
      pow_v = pow_preproc<T>(y).get_pow(a);
    } while(pow_v < x);
    --y;
    return y;
  } else {
    do {
      --y;
      pow_v = pow_preproc<T>(y).get_pow(a);
    } while(pow_v > x);
    return y;
  }
}

int main() {
  ll n, i, j = 1, k;
  scan(n);
  ll count = n + 1;
  for(;j < 60; ++j) {
    dprint(j);
    i = root(j, n);
    ll ipow = pow_preproc<ll>(i).get_pow(j);
    k = n - ipow;
    chmin(count, i + j + k);
  }
  println(count);
}