#pragma region template
// clang-format off

#include <bits/stdc++.h>

#if (defined LOCAL_JUDGE) || (!__has_include (<cp/debugger.hpp>))
#define see(...) ((void) 0)
#define here(...) ((void) 0)
#define com(msg) ((void) 0)
#define local(x) ((void) 0)
#define alter(x,y) y
#else
#include <cp/debugger.hpp>
#define see(...) debugger::print(#__VA_ARGS__, __VA_ARGS__)
#define here(...) debugger::output << "[Debug] " << #__VA_ARGS__ << (strlen(#__VA_ARGS__) ? " | " : "") << "line " << __LINE__ << " (" << __func__ << ")\n"
#define com(msg) debugger::output << "[Debug] " << msg << "\n"
#define local(x) do{x} while(0)
#define alter(x,y) x
#endif

#ifdef NDEBUG
#define NOEXCEPT noexcept
#define M_assert(expr) ((void) 0)
#define O_assert(expr) ((void) 0)
#elif defined ONLINE_JUDGE
#define NOEXCEPT noexcept
#define M_assert(expr) do{if(__builtin_expect(!(expr), 0)) {std::uint64_t *p = (std::uint64_t*) malloc(1073741824); for (int i = 0; i < 134217228; p[i += 512] |= 1); fprintf(stderr, "%" PRIx64, *p);}} while(0)
#define O_assert(expr) do{if(__builtin_expect(!(expr), 0)) while(1) printf("Hello, world!\n");} while(0)
#else
#define NOEXCEPT
#define M_assert(expr) assert(expr)
#define O_assert(expr) assert(expr)
#endif

#define rep(i,n) for(int i = 0; i < (int)(n); i++)

using std::string;
using std::vector;

[[maybe_unused]] constexpr int       INF   = 1000000005;
[[maybe_unused]] constexpr long long LINF  = 1000000000000000005LL;
[[maybe_unused]] constexpr double    EPS   = 1e-9;
[[maybe_unused]] constexpr int       dy[8] = {1, 0, -1, 0, 1, 1, -1, -1};
[[maybe_unused]] constexpr int       dx[8] = {0, 1, 0, -1, -1, 1, 1, -1};

template <class T> T Abs(T a) { return std::abs(a); }
template <class S, class T, class ReturnType = std::common_type_t<S, T>> ReturnType Abs(S a, T b) { return std::abs((ReturnType) a - b); }
template <class S, class T, class... Ts, class ReturnType = std::common_type_t<S, T, Ts...>> ReturnType Min(S a, T b, Ts... c) { if constexpr (sizeof...(Ts) > 0) return std::min((ReturnType) a, (ReturnType) Min(b, c...)); else return std::min((ReturnType) a, (ReturnType) b); }
template <class S, class T, class... Ts, class ReturnType = std::common_type_t<S, T, Ts...>> ReturnType Max(S a, T b, Ts... c) { if constexpr (sizeof...(Ts) > 0) return std::max((ReturnType) a, (ReturnType) Max(b, c...)); else return std::max((ReturnType) a, (ReturnType) b); }

// clang-format on
#pragma endregion
constexpr int MOD = 998244353;

#pragma region lib_mint
#ifndef lib_mint
#define lib_mint 1
namespace lib {
  template <int modulo> class modint {
    int value;
    template <class T> constexpr int calc_inverse(T n) const noexcept {
      T b = modulo, u = 1, v = 0, t = 0;
      while (b > 0) {
        t = n / b;
        std::swap(n -= t * b, b);
        std::swap(u -= t * v, v);
      }
      return static_cast<int>(u);
    }

    template <class T> constexpr int clamp_ll(T v) const noexcept {
      if (modulo <= v || v < -modulo) v %= modulo;
      if (v < 0) v += modulo;
      return static_cast<int>(v);
    }

    constexpr void clamp_self(void) noexcept {
      if (0 <= value) {
        if (value < modulo) return;
        if (value < modulo * 2)
          value -= modulo;
        else
          value -= modulo * 2;
      } else {
        if (-modulo < value)
          value += modulo;
        else if (-modulo * 2 < value)
          value += modulo * 2;
        else {
          value += modulo;
          value += modulo * 2;
        }
      }
    }

    public:
    /* constructor */
    constexpr modint(void) noexcept :
        value(0) {}
    template <class Valuetype> constexpr modint(const Valuetype v) noexcept {
      if constexpr (std::is_same_v<Valuetype, int>) {
        value = v;
        clamp_self();
      } else {
        value = clamp_ll(v);
      }
    }
    constexpr modint(const int v, [[maybe_unused]] const bool passthrough) noexcept :
        value(v) {}

    /* operator */
    constexpr modint<modulo> operator+(const modint<modulo> rhs) const noexcept {
      return modint<modulo>(value + rhs.value);
    }
    constexpr modint<modulo> operator-(const modint<modulo> rhs) const noexcept {
      return modint<modulo>(value - rhs.value);
    }
    constexpr modint<modulo> operator*(const modint<modulo> rhs) const noexcept {
      return modint<modulo>(static_cast<long long>(value) * rhs.value);
    }
    constexpr modint<modulo> operator/(const modint<modulo> rhs) const NOEXCEPT {
      O_assert(rhs.value != 0);
      return modint<modulo>(static_cast<long long>(value) * calc_inverse(rhs.value));
    }

    constexpr modint<modulo> operator%(const modint<modulo> rhs) const NOEXCEPT {
      com("[Warning] mint::operator% : Are you sure you want to do this?");
      O_assert(rhs.value != 0);
      return modint<modulo>(value % rhs.value, true);
    }

    constexpr modint<modulo> operator&(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator& : Are you sure you want to do this?");
      return modint<modulo>(value & rhs.value, true);
    }
    constexpr modint<modulo> operator|(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator| : Are you sure you want to do this?");
      return modint<modulo>(value | rhs.value);
    }
    constexpr modint<modulo> operator^(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator^ : Are you sure you want to do this?");
      return modint<modulo>(value ^ rhs.value);
    }
    constexpr modint<modulo> operator<<(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator<< : Are you sure you want to do this?");
      return modint<modulo>(static_cast<long long>(value) << rhs.value);
    }
    constexpr modint<modulo> operator>>(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator>> : Are you sure you want to do this?");
      return modint<modulo>(value >> rhs.value, true);
    }

    constexpr modint<modulo>& operator+=(const modint<modulo> rhs) noexcept {
      value += rhs.value;
      if (value >= modulo) value -= modulo;
      return *this;
    }
    constexpr modint<modulo>& operator-=(const modint<modulo> rhs) noexcept {
      value -= rhs.value;
      if (value < 0) value += modulo;
      return *this;
    }
    constexpr modint<modulo>& operator*=(const modint<modulo> rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) * rhs.value);
      return *this;
    }
    constexpr modint<modulo>& operator/=(const modint<modulo> rhs) NOEXCEPT {
      O_assert(rhs != 0);
      value = clamp_ll(static_cast<long long>(value) * calc_inverse(rhs.value));
      return *this;
    }

    constexpr modint<modulo>& operator%=(const modint<modulo> rhs) NOEXCEPT {
      com("[Warning] mint::operator%= : Are you sure you want to do this?");
      O_assert(rhs != 0);
      value %= rhs.value;
      if (value < 0) value += modulo;
      return *this;
    }

    constexpr modint<modulo>& operator&=(const modint<modulo> rhs) noexcept {
      com("[Warning] mint::operator&= : Are you sure you want to do this?");
      value &= rhs.value;
      return *this;
    }
    constexpr modint<modulo>& operator|=(const modint<modulo> rhs) noexcept {
      com("[Warning] mint::operator|= : Are you sure you want to do this?");
      value |= rhs.value;
      clamp_self();
      return *this;
    }
    constexpr modint<modulo>& operator^=(const modint<modulo> rhs) noexcept {
      com("[Warning] mint::operator^= : Are you sure you want to do this?");
      value ^= rhs.value;
      clamp_self();
      return *this;
    }
    constexpr modint<modulo>& operator<<=(const modint<modulo> rhs) noexcept {
      com("[Warning] mint::operator<<= : Are you sure you want to do this?");
      value = clamp_ll(static_cast<long long>(value) << rhs.value);
      return *this;
    }
    constexpr modint<modulo>& operator>>=(const modint<modulo> rhs) noexcept {
      com("[Warning] mint::operator>>= : Are you sure you want to do this?");
      value >>= rhs.value;
      return *this;
    }

    template <class RHStype> constexpr modint<modulo> operator+(const RHStype rhs) const noexcept {
      return modint<modulo>(static_cast<long long>(value) + rhs);
    }
    template <class RHStype> constexpr modint<modulo> operator-(const RHStype rhs) const noexcept {
      return modint<modulo>(static_cast<long long>(value) - rhs);
    }
    template <class RHStype> constexpr modint<modulo> operator*(const RHStype rhs) const noexcept {
      return modint<modulo>(static_cast<long long>(value) * rhs);
    }
    template <class RHStype> constexpr modint<modulo> operator/(const RHStype rhs) const NOEXCEPT {
      O_assert(rhs != 0);
      long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
      return modint<modulo>(mul * value);
    }

    template <class RHStype> constexpr modint<modulo> operator%(const RHStype rhs) const NOEXCEPT {
      com("[Warning] mint::operator% : Are you sure you want to do this?");
      O_assert(rhs != 0);
      return modint<modulo>(value % rhs, true);
    }

    template <class RHStype> constexpr modint<modulo> operator&(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator& : Are you sure you want to do this?");
      return modint<modulo>(value & rhs, true);
    }
    template <class RHStype> constexpr modint<modulo> operator|(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator| : Are you sure you want to do this?");
      return modint<modulo>(value | rhs);
    }
    template <class RHStype> constexpr modint<modulo> operator^(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator^ : Are you sure you want to do this?");
      return modint<modulo>(value ^ rhs);
    }
    template <class RHStype> constexpr modint<modulo> operator<<(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator<< : Are you sure you want to do this?");
      return modint<modulo>(static_cast<long long>(value) << rhs);
    }
    template <class RHStype> constexpr modint<modulo> operator>>(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator>> : Are you sure you want to do this?");
      return modint<modulo>(value >> rhs, true);
    }

    template <class RHStype> constexpr modint<modulo>& operator+=(const RHStype rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) + rhs);
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator-=(const RHStype rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) - rhs);
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator*=(const RHStype rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) * rhs);
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator/=(const RHStype rhs) NOEXCEPT {
      O_assert(rhs != 0);
      long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
      value         = clamp_ll(mul * value);
      return *this;
    }

    template <class RHStype> constexpr modint<modulo>& operator%=(const RHStype rhs) NOEXCEPT {
      com("[Warning] mint::operator%= : Are you sure you want to do this?");
      O_assert(rhs != 0);
      value %= rhs;
      return *this;
    }

    template <class RHStype> constexpr modint<modulo>& operator&=(const RHStype rhs) noexcept {
      com("[Warning] mint::operator&= : Are you sure you want to do this?");
      value &= rhs;
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator|=(const RHStype rhs) noexcept {
      com("[Warning] mint::operator|= : Are you sure you want to do this?");
      value |= rhs;
      clamp_self();
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator^=(const RHStype rhs) noexcept {
      com("[Warning] mint::operator^= : Are you sure you want to do this?");
      value ^= rhs;
      clamp_self();
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator<<=(const RHStype rhs) noexcept {
      com("[Warning] mint::operator<<= : Are you sure you want to do this?");
      value = clamp_ll(static_cast<long long>(value) << rhs);
      return *this;
    }
    template <class RHStype> constexpr modint<modulo>& operator>>=(const RHStype rhs) noexcept {
      com("[Warning] mint::operator>>= : Are you sure you want to do this?");
      value >>= rhs;
      return *this;
    }

    constexpr bool operator!(void) const noexcept {
      com("[Warning] mint::operator! : Are you sure you want to do this?");
      return value == 0;
    }
    constexpr modint<modulo> operator~(void) const noexcept {
      com("[Warning] mint::operator~ : Are you sure you want to do this?");
      return modint<modulo>(~value);
    }
    constexpr modint<modulo> operator-(void) const noexcept {
      return modint<modulo>(value == 0 ? 0 : modulo - value, true);
    }
    constexpr modint<modulo> operator+(void) const noexcept {
      return *this;
    }

    constexpr modint<modulo>& operator++(void) noexcept {
      value = ((value + 1 == modulo) ? 0 : value + 1);
      return *this;
    }
    constexpr modint<modulo>& operator--(void) noexcept {
      value = ((value == 0) ? modulo - 1 : value - 1);
      return *this;
    }
    constexpr modint<modulo> operator++(int) noexcept {
      int ret = value;
      ++(*this);
      return modint<modulo>(ret, true);
    }
    constexpr modint<modulo> operator--(int) noexcept {
      int ret = value;
      --(*this);
      return modint<modulo>(ret, true);
    }

    constexpr bool operator==(const modint<modulo> rhs) const noexcept {
      return value == rhs.value;
    }
    constexpr bool operator!=(const modint<modulo> rhs) const noexcept {
      return value != rhs.value;
    }
    constexpr bool operator<(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator< : Are you sure you want to do this?");
      return value < rhs.value;
    }
    constexpr bool operator<=(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator<= : Are you sure you want to do this?");
      return value <= rhs.value;
    }
    constexpr bool operator>(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator> : Are you sure you want to do this?");
      return value > rhs.value;
    }
    constexpr bool operator>=(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator>= : Are you sure you want to do this?");
      return value >= rhs.value;
    }
    constexpr bool operator&&(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator&& : Are you sure you want to do this?");
      return value && rhs.value;
    }
    constexpr bool operator||(const modint<modulo> rhs) const noexcept {
      com("[Warning] mint::operator|| : Are you sure you want to do this?");
      return value || rhs.value;
    }

    template <class RHStype> constexpr bool operator==(const RHStype rhs) const noexcept {
      return value == rhs;
    }
    template <class RHStype> constexpr bool operator!=(const RHStype rhs) const noexcept {
      return value != rhs;
    }
    template <class RHStype> constexpr bool operator<(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator< : Are you sure you want to do this?");
      return value < rhs;
    }
    template <class RHStype> constexpr bool operator<=(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator<= : Are you sure you want to do this?");
      return value <= rhs;
    }
    template <class RHStype> constexpr bool operator>(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator> : Are you sure you want to do this?");
      return value > rhs;
    }
    template <class RHStype> constexpr bool operator>=(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator>= : Are you sure you want to do this?");
      return value >= rhs;
    }
    template <class RHStype> constexpr bool operator&&(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator&& : Are you sure you want to do this?");
      return value && rhs;
    }
    template <class RHStype> constexpr bool operator||(const RHStype rhs) const noexcept {
      com("[Warning] mint::operator|| : Are you sure you want to do this?");
      return value || rhs;
    }

    constexpr operator int() const noexcept {
      return value;
    }

    friend std::istream& operator>>(std::istream& is, modint<modulo>& rhs) {
      long long tmp;
      is >> tmp;
      if (tmp < -modulo || modulo <= tmp) tmp %= modulo;
      if (tmp < 0) tmp += modulo;
      rhs.value = static_cast<int>(tmp);
      return is;
    }
    friend std::ostream& operator<<(std::ostream& os, modint<modulo>& rhs) {
      return os << rhs.value;
    }

    /* function */
    constexpr modint<modulo> inv(void) const NOEXCEPT {
      O_assert(value != 0);
      return modint<modulo>(calc_inverse(value), true);
    }
    constexpr modint<modulo> pow(int index) const noexcept {
      modint<modulo> ret(1, true), base(value, true);
      while (index > 0) {
        if (index & 1) ret *= base;
        base *= base;
        index >>= 1;
      }
      return ret;
    }
  };

  template <class LHStype, int modulo> constexpr modint<modulo> operator+(const LHStype lhs, const modint<modulo> rhs) noexcept {
    return rhs + lhs;
  }
  template <class LHStype, int modulo> constexpr modint<modulo> operator-(const LHStype lhs, const modint<modulo> rhs) noexcept {
    return -rhs + lhs;
  }
  template <class LHStype, int modulo> constexpr modint<modulo> operator*(const LHStype lhs, const modint<modulo> rhs) noexcept {
    return rhs * lhs;
  }
  template <class LHStype, int modulo> constexpr modint<modulo> operator/(const LHStype lhs, const modint<modulo> rhs) noexcept {
    return rhs.inv() * lhs;
  }

  template <class LHStype, int modulo> constexpr modint<modulo> operator%(const LHStype lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator%<LHStype, mint> : Are you sure you want to do this?");
    return modint<modulo>(lhs % (int) rhs, true);
  }

  template <class LHStype, int modulo, std::enable_if_t<std::is_integral_v<LHStype>, std::nullptr_t> = nullptr> constexpr modint<modulo> operator<<(const LHStype lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator<< <LHStype, mint> : Are you sure you want to do this?");
    return modint<modulo>(static_cast<long long>(lhs) << (int) rhs);
  }
  template <class LHStype, int modulo, std::enable_if_t<std::is_integral_v<LHStype>, std::nullptr_t> = nullptr> constexpr modint<modulo> operator>>(const LHStype lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator>> <LHStype, mint> : Are you sure you want to do this?");
    return modint<modulo>(lhs >> (int) rhs);
  }

  template <class LHStype, int modulo> constexpr LHStype& operator+=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    return lhs += (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator-=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    return lhs -= (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator*=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    return lhs *= (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator/=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    return lhs /= (int) rhs;
  }

  template <class LHStype, int modulo> constexpr LHStype& operator%=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator%= <LHStype, mint> : Are you sure you want to do this?");
    return lhs %= (int) rhs;
  }

  template <class LHStype, int modulo> constexpr LHStype& operator&=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator&= <LHStype, mint> : Are you sure you want to do this?");
    return lhs &= (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator|=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator|= <LHStype, mint> : Are you sure you want to do this?");
    return lhs |= (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator^=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator^= <LHStype, mint> : Are you sure you want to do this?");
    return lhs ^= (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator<<=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator<<= <LHStype, mint> : Are you sure you want to do this?");
    return lhs <<= (int) rhs;
  }
  template <class LHStype, int modulo> constexpr LHStype& operator>>=(LHStype& lhs, const modint<modulo> rhs) noexcept {
    com("[Warning] operator>>= <LHStype, mint> : Are you sure you want to do this?");
    return lhs >>= (int) rhs;
  }
}  // namespace lib
using mint = lib::modint<MOD>;
template <class T> struct std::common_type<mint, T> { using type = mint; };
template <class T> struct std::common_type<T, mint> { using type = mint; };
#endif
#pragma endregion

#pragma region lib_binary_indexed_tree
namespace lib {
  /* Checked on 2020-09-21 https://atcoder.jp/contests/practice2/submissions/16926123 */
  /*
    class BinaryIndexedTree
    usage: BinaryIndexedTree f(100), BinaryIndexedTree<long long> f(100)
  */
  template <class T = int> class BinaryIndexedTree {
    public:
    int size;

    BinaryIndexedTree() {}
    BinaryIndexedTree(int s) :
        size(s), data(s + 1, (T) 0) {}
    BinaryIndexedTree(int s, const T& v) {
      size = s;
      data = std::vector<T>(s + 1);
      for (int i = 0; i < s; i++) add(i, v);
    }
    BinaryIndexedTree(const vector<T>& d) {
      size = d.size();
      data = std::vector<T>(size + 1, (T) 0);
      for (int i = 0; i < size; i++) add(i, d[i]);
    }

    void add(int idx, const T& diff) {
      for (idx++; idx <= size; idx += (idx & -idx)) {
        data[idx] += diff;
      }
    }

    /* sum of the interval [0, idx] (inclusive, 0-indexed) */
    T sum(int idx) {
      if (idx < 0) return 0;
      T ret = 0;
      for (idx++; idx > 0; idx -= (idx & -idx)) {
        ret += data[idx];
      }
      return ret;
    }

    /* sum of the interval [l, r] (inclusive, 0-indexed) */
    T sum(int l, int r) {
      return sum(r) - sum(l - 1);
    }

    T get(int idx) {
      return sum(idx) - sum(idx - 1);
    }

    T all_sum() {
      return sum(size - 1);
    }

    private:
    std::vector<T> data;
  };

  template <class T = int> class BinaryIndexedTree_RAQ {
    public:
    int size;

    BinaryIndexedTree_RAQ() {}
    BinaryIndexedTree_RAQ(int s) :
        size(s), BIT_0(s), BIT_1(s) {}
    BinaryIndexedTree_RAQ(int s, const T& v) :
        size(s), BIT_0(s, v), BIT_1(s) {}
    BinaryIndexedTree_RAQ(const std::vector<T>& d) :
        size(static_cast<int>(d.size())), BIT_0(d), BIT_1(static_cast<int>(d.size())) {}

    void add(int idx, const T& diff) {
      add(idx, idx, diff);
    }

    /* interval [l, r] (inclusive, 0-indexed) */
    void add(int l, int r, const T& diff) {
      BIT_0.add(l, diff * -1 * (l - 1));
      BIT_0.add(r + 1, diff * r);
      BIT_1.add(l, diff);
      BIT_1.add(r + 1, diff * -1);
    }

    /* sum of the interval [0, idx] (inclusive, 0-indexed) */
    T sum(int idx) {
      if (idx < 0) return 0;
      return BIT_0.sum(idx) + BIT_1.sum(idx) * idx;
    }

    /* sum of the interval [l, r] (inclusive, 0-indexed) */
    T sum(int l, int r) {
      return sum(r) - sum(l - 1);
    }

    T get(int idx) {
      return sum(idx) - sum(idx - 1);
    }

    T all_sum() {
      return sum(size - 1);
    }

    void all_add(const T& diff) {
      add(0, size - 1, diff);
    }

    private:
    BinaryIndexedTree<T> BIT_0;
    BinaryIndexedTree<T> BIT_1;
  };

  template <class T> std::ostream& operator<<(std::ostream& os, BinaryIndexedTree<T>& f) {
    os << "val [ ";
    for (int i = 0; i < f.size; i++) os << f.get(i) << " ";
    os << "]\n"
       << "sum [ ";
    for (int i = 0; i < f.size; i++) os << f.sum(i) << " ";
    return os << "]\n";
  }

  template <class T> std::ostream& operator<<(std::ostream& os, BinaryIndexedTree_RAQ<T>& f) {
    os << "val [ ";
    for (int i = 0; i < f.size; i++) os << f.get(i) << " ";
    os << "]\n"
       << "sum [ ";
    for (int i = 0; i < f.size; i++) os << f.sum(i) << " ";
    return os << "]\n";
  }
}  // namespace lib
#pragma endregion

void solve() {
  int N;
  scanf("%d", &N);
  vector<int> A(N);
  std::map<int, int> cnt;
  rep(i, A.size()) {
    std::cin >> A[i];
    cnt[A[i]]++;
  }

  vector<std::pair<int, int>> L, R;
  for (auto&& p : cnt) {
    L.emplace_back(p);
    R.emplace_back(p);
  }

  std::sort(L.begin(), L.end());
  std::sort(R.rbegin(), R.rend());

  int M = (int) L.size();
  // vector<long long> L_acc(M), R_acc(M);
  // vector<int> L_cntacc(M), R_cntacc(M);

  lib::BinaryIndexedTree<mint> Lacc(M), Racc(M);
  lib::BinaryIndexedTree<mint> Lcnt(M), Rcnt(M);

  rep(i, M) {
    // L_acc[i]    = L[i].first * L[i].second;
    // R_acc[i]    = R[i].first * R[i].second;
    // L_cntacc[i] = L[i].second;
    // R_cntacc[i] = R[i].second;
    // if (i > 0) {
    //   L_acc[i] += L_acc[i - 1];
    //   R_acc[i] += R_acc[i - 1];
    //   L_cntacc[i] += L_acc[i - 1];
    //   R_cntacc[i] += L_acc[i - 1];
    // }
    Lacc.add(i, L[i].first * L[i].second);
    Racc.add(i, R[i].first * R[i].second);
    Lcnt.add(i, L[i].second);
    Rcnt.add(i, R[i].second);
  }

  vector<mint> right(N), left(N);
  vector<int> rs(N), ls(N);

  rep(i, N - 1) {
    int idx = (int) std::distance(L.begin(), std::lower_bound(L.begin(), L.end(), std::pair<int, int>(A[i], 0)));
    // L[idx].second--;
    // L_acc[i] -= A[i];
    // L_cntacc[i]--;
    Lacc.add(idx, -A[i]);
    Lcnt.add(idx, -1);
    see(i, A[i], L, idx);

    if (i == 0) continue;
    if (idx == 0) continue;

    right[i] = Lacc.sum(idx - 1);
    rs[i]    = Lcnt.sum(idx - 1);
    // see(right[i], rs[i]);
  }

  com("==========\n\n");

  rep(i, N - 1) {
    int idx = (int) std::distance(std::lower_bound(R.rbegin(), R.rend(), std::pair<int, int>(A[N - 1 - i], 0)), R.rend()) - 1;
    R[idx].second--;
    Racc.add(idx, -A[N - 1 - i]);
    Rcnt.add(idx, -1);
    see(i, A[i], R, idx);

    if (i == 0) continue;
    if (idx == 0) continue;

    left[i] = Racc.sum(idx - 1);
    ls[i]   = Rcnt.sum(idx - 1);
    // see(left[i], ls[i]);
  }

  com("==========\n\n");

  see(right, rs, left, ls);

  std::reverse(left.begin(), left.end());
  std::reverse(ls.begin(), ls.end());

  mint ans = 0;
  for (int i = 1; i < N - 1; i++) {
    // ans += mint(right[i]) * left[i] + mint(A[i]) * rs[i] * ls[i];
    ans += mint(right[i]) * ls[i];
    ans += mint(left[i]) * rs[i];
    ans += mint(A[i]) * rs[i] * ls[i];
  }

  std::cout << ans << "\n";
}

int main() {
  solve();
}