#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:36777216")
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline double &RF(double &x) {
  scanf("%lf", &x);
  return x;
}
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s);
inline char &RC(char &c);
inline char RC();
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, less<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < int(n); ++i) CLR(A[i]);
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
  return A;
}
template <class T>
inline T &UNQ(T &A) {
  A.resize(unique(SRT(A).begin(), SRT(A).end()) - A.begin());
  return A;
}
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long INFF = 1LL << 60;
const double EPS = 1e-9;
const double OO = 1e15;
const double PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (a < b) a = b;
}
template <class T>
inline void checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
}
template <class T>
inline void checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
}
template <class T, class C>
inline void checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
}
template <class T, class C>
inline void checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
inline int Ceil(int x, int y) { return (x - 1) / y + 1; }
namespace BO {
inline bool _1(int x, int i) { return bool(x & 1 << i); }
inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
inline int reverse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long reverse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
template <class T>
inline bool odd(T x) {
  return x & 1;
}
template <class T>
inline bool even(T x) {
  return !odd(x);
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
inline int low_idx(int x) { return __builtin_ffs(x); }
inline int low_idx(long long x) { return __builtin_ffsll(x); }
inline int high_idx(int x) { return low_idx(reverse_bits(x)); }
inline int high_idx(long long x) { return low_idx(reverse_bits(x)); }
inline int clz(int x) { return __builtin_clz(x); }
inline int clz(long long x) { return __builtin_clzll(x); }
inline int ctz(int x) { return __builtin_ctz(x); }
inline int ctz(long long x) { return __builtin_ctzll(x); }
inline int parity(int x) { return __builtin_parity(x); }
inline int parity(long long x) { return __builtin_parityll(x); }
inline int lg2(int a) { return 31 - clz(a); }
inline int lg2(long long a) { return 63 - clz(a); }
inline int count_bits(int x) { return __builtin_popcount(x); }
inline int count_bits(long long x) { return __builtin_popcountll(x); }
}  // namespace BO
using namespace BO;
namespace SL {
namespace KMP {
void calc_pi(const char *P, int n, int *pi) {
  for (int i = 1, j = pi[0] = -1; i < n; ++i) {
    while (j >= 0 && P[i] != P[j + 1]) j = pi[j];
    if (P[i] == P[j + 1]) ++j;
    pi[i] = j;
  }
}
bool run(const char *T, int n, const char *P, int m, const int *pi) {
  for (int i = 0, j = -1; i < n; ++i) {
    while (j >= 0 && T[i] != P[j + 1]) j = pi[j];
    if (T[i] == P[j + 1]) ++j;
    if (j == m - 1) return true;
  }
  return false;
}
}  // namespace KMP
namespace Z {
void calc_z(const char *P, int n, int *z) {
  z[0] = n;
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i > r) {
      for (l = r = i; r < n && P[r] == P[r - l];) ++r;
      z[i] = r - l, --r;
    } else {
      if (z[i - l] < r - i + 1)
        z[i] = z[i - l];
      else {
        for (l = i; r < n && P[r] == P[r - l];) ++r;
        z[i] = r - l, --r;
      }
    }
  }
}
int run(const char *T, int n, const char *P, int m, const int *z) {
  int ex;
  for (int n____ = (ex = 0, int(min(n, m))); ex < n____; ++ex)
    if (T[ex] != P[ex]) break;
  int res = ex == m;
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i > r) {
      for (l = r = i; r < n && T[r] == P[r - l];) ++r;
      ex = r - l, --r;
    } else {
      if (z[i - l] < r - i + 1)
        ex = z[i - l];
      else {
        for (l = i; r < n && T[r] == P[r - l];) ++r;
        ex = r - l, --r;
      }
    }
    if (ex == m) ++res;
  }
  return res;
}
}  // namespace Z
void Manacher(char s[], int n, int p[]) {
  const int NN = 0;
  static char ss[NN * 2 + 2];
  int nn = 2 * n + 2;
  ss[0] = '$', ss[nn - 1] = '#', ss[nn] = 0;
  for (int i = 0; i < int(n); ++i) ss[i * 2 + 1] = '#', ss[i * 2 + 2] = s[i];
  int mx = 0, id = 0;
  for (int i = int(1); i < int(nn); ++i) {
    p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
    while (ss[i + p[i]] == ss[i - p[i]]) ++p[i];
    if (i + p[i] > mx) mx = i + p[i], id = i;
  }
}
}  // namespace SL
namespace CG {
struct Po;
struct Line;
struct Seg;
inline int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
inline int sgn(double x, double y) { return sgn(x - y); }
struct Po {
  double x, y;
  Po(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  friend istream &operator>>(istream &in, Po &p) { return in >> p.x >> p.y; }
  friend ostream &operator<<(ostream &out, Po p) {
    return out << "(" << p.x << ", " << p.y << ")";
  }
  bool operator==(const Po &r) const { return !sgn(x - r.x) && !sgn(y - r.y); };
  bool operator!=(const Po &r) const { return sgn(x - r.x) || sgn(y - r.y); }
  Po operator+(const Po &r) const { return Po(x + r.x, y + r.y); }
  Po operator-(const Po &r) const { return Po(x - r.x, y - r.y); }
  Po operator*(double k) const { return Po(x * k, y * k); }
  Po operator/(double k) const { return Po(x / k, y / k); }
  double operator*(const Po &) const;
  double operator^(const Po &) const;
  bool operator<(const Po &r) const {
    return sgn(x, r.x) < 0 || !sgn(x, r.x) && sgn(y, r.y) < 0;
  }
  Po operator-() const { return Po(-x, -y); }
  Po &operator+=(const Po &r) {
    x += r.x, y += r.y;
    return *this;
  }
  Po &operator-=(const Po &r) {
    x -= r.x, y -= r.y;
    return *this;
  }
  Po &operator*=(double k) {
    x *= k, y *= k;
    return *this;
  }
  Po &operator/=(double k) {
    x /= k, y /= k;
    return *this;
  }
  double length_sqr() const { return sqr(x) + sqr(y); }
  double length() const { return sqrt(length_sqr()); }
  Po unit() const { return *this / length(); }
  bool dgt() const { return !sgn(x) && !sgn(y); }
  double atan() const { return atan2(y, x); }
  void input() { RF(x, y); }
};
Po operator*(double k, Po a) { return a * k; }
struct Line {
  Po a, b;
  Line(double x0 = 0, double y0 = 0, double x1 = 0, double y1 = 0)
      : a(Po(x0, y0)), b(Po(x1, y1)) {}
  Line(const Po &a, const Po &b) : a(a), b(b) {}
  Line(const Line &l) : a(l.a), b(l.b) {}
  friend ostream &operator<<(ostream &out, Line p) {
    return out << p.a << "-" << p.b;
  }
  Line operator+(Po x) const { return Line(a + x, b + x); }
  double length() const { return (b - a).length(); }
  bool dgt() const { return (b - a).dgt(); }
  void input() { a.input(), b.input(); }
  void getequation(double, double, double) const;
};
struct Seg : Line {};
inline double dot(const double &x1, const double &y1, const double &x2,
                  const double &y2) {
  return x1 * x2 + y1 * y2;
}
inline double dot(const Po &a, const Po &b) { return dot(a.x, a.y, b.x, b.y); }
inline double dot(const Po &p0, const Po &p1, const Po &p2) {
  return dot(p1 - p0, p2 - p0);
}
inline double dot(const Po &o, const Line &l) { return dot(o, l.a, l.b); }
inline double dot(const Line &l, const Po &o) { return dot(o, l.a, l.b); }
inline double dot(const Line &l1, const Line &l2) {
  return dot(l1.b - l1.a, l2.b - l2.a);
}
inline double det(const double &x1, const double &y1, const double &x2,
                  const double &y2) {
  return x1 * y2 - x2 * y1;
}
inline double det(const Po &a, const Po &b) { return det(a.x, a.y, b.x, b.y); }
inline double det(const Po &p0, const Po &p1, const Po &p2) {
  return det(p1 - p0, p2 - p0);
}
inline double det(const Po &o, const Line &l) { return det(o, l.a, l.b); }
inline double det(const Line &l, const Po &o) { return det(o, l.a, l.b); }
inline double det(const Line &l1, const Line &l2) {
  return det(l1.b - l1.a, l2.b - l2.a);
}
double Po::operator*(const Po &r) const { return dot(*this, r); }
double Po::operator^(const Po &r) const { return det(*this, r); }
void Line::getequation(double A, double B, double C) const {
  A = a.y - b.y, B = b.x - a.x, C = det(a, b);
}
template <class T1, class T2>
inline double dist(const T1 &x, const T2 &y) {
  return sqrt(dist_sqr(x, y));
}
template <class T1, class T2, class T3>
inline double dist(const T1 &x, const T2 &y, const T3 &z) {
  return sqrt(dist_sqr(x, y, z));
}
template <class T1, class T2>
inline int dett(const T1 &x, const T2 &y) {
  return sgn(det(x, y));
}
template <class T1, class T2>
inline int dott(const T1 &x, const T2 &y) {
  return sgn(dot(x, y));
}
template <class T1, class T2, class T3>
inline int dett(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(det(x, y, z));
}
template <class T1, class T2, class T3>
inline int dott(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(dot(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(det(x, y, z, w));
}
template <class T1, class T2, class T3, class T4>
inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(dot(x, y, z, w));
}
inline double dist_sqr(const double &x, const double &y) {
  return sqr(x) + sqr(y);
}
inline double dist_sqr(const double &x, const double &y, const double &z) {
  return sqr(x) + sqr(y) + sqr(z);
}
inline double dist_sqr(const Po &a, const Po &b) {
  return sqr(a.x - b.x) + sqr(a.y - b.y);
}
inline double dist_sqr(const Po &p, const Line &l) {
  Po v0 = l.b - l.a, v1 = p - l.a;
  return sqr(fabs(det(v0, v1))) / v0.length_sqr();
}
inline double dist_sqr(const Po &p, const Seg &l) {
  Po v0 = l.b - l.a, v1 = p - l.a, v2 = p - l.b;
  if (sgn(dot(v0, v1)) * sgn(dot(v0, v2)) <= 0)
    return dist_sqr(p, Line(l));
  else
    return min(v1.length_sqr(), v2.length_sqr());
}
inline double dist_sqr(Line l, Po p) { return dist_sqr(p, l); }
inline double dist_sqr(Seg l, Po p) { return dist_sqr(p, l); }
inline double dist_sqr(Line l1, Line l2) {
  if (sgn(det(l1, l2)) != 0) return 0;
  return dist_sqr(l1.a, l2);
}
inline double dist_sqr(Line l1, Seg l2) {
  Po v0 = l1.b - l1.a, v1 = l2.a - l1.a, v2 = l2.b - l1.a;
  double c1 = det(v0, v1), c2 = det(v0, v2);
  return sgn(c1) != sgn(c2) ? 0
                            : sqr(min(fabs(c1), fabs(c2))) / v0.length_sqr();
}
bool isIntersect(Seg l1, Seg l2) {
  if (l1.a == l2.a || l1.a == l2.b || l1.b == l2.a || l1.b == l2.b) return true;
  return min(l1.a.x, l1.b.x) <= max(l2.a.x, l2.b.x) &&
         min(l2.a.x, l2.b.x) <= max(l1.a.x, l1.b.x) &&
         min(l1.a.y, l1.b.y) <= max(l2.a.y, l2.b.y) &&
         min(l2.a.y, l2.b.y) <= max(l1.a.y, l1.b.y) &&
         sgn(det(l1.a, l2.a, l2.b)) * sgn(det(l1.b, l2.a, l2.b)) <= 0 &&
         sgn(det(l2.a, l1.a, l1.b)) * sgn(det(l2.b, l1.a, l1.b)) <= 0;
}
inline double dist_sqr(Seg l1, Seg l2) {
  if (isIntersect(l1, l2))
    return 0;
  else
    return min(dist_sqr(l1.a, l2), dist_sqr(l1.b, l2), dist_sqr(l2.a, l1),
               dist_sqr(l2.b, l1));
}
inline bool isOnSide(const Po &p, const Seg &l) { return p == l.a || p == l.b; }
inline bool isOnSeg(const Po &p, const Seg &l) {
  return sgn(det(p, l.a, l.b)) == 0 && sgn(l.a.x, p.x) * sgn(l.b.x, p.x) <= 0 &&
         sgn(l.a.y, p.y) * sgn(l.b.y, p.y) <= 0;
}
inline bool isOnSegg(const Po &p, const Seg &l) {
  return sgn(det(p, l.a, l.b)) == 0 && sgn(l.a.x, p.x) * sgn(l.b.x, p.x) < 0 &&
         sgn(l.a.y, p.y) * sgn(l.b.y, p.y) < 0;
}
inline Po intersect(const Line &l1, const Line &l2) {
  return l1.a + (l1.b - l1.a) * (det(l2.a, l1.a, l2.b) / det(l2, l1));
}
inline Po intersect(const Po &p, const Line &l) {
  return intersect(Line(p, p + Po(l.a.y - l.b.y, l.b.x - l.a.x)), l);
}
inline Po rotate(Po p, double alpha, Po o = Po()) {
  p.x -= o.x, p.y -= o.y;
  return Po(p.x * cos(alpha) - p.y * sin(alpha),
            p.y * cos(alpha) + p.x * sin(alpha)) +
         o;
}
}  // namespace CG
using namespace CG;
template <class T>
inline T &RD(T &x) {
  scanf("%d", &x);
  return x;
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
int Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
const int N = 100009, L = 20;
vector<int> adj[N];
int ST[L][2 * N], st[N], dep[N], sz[N], bj[N];
int n, m, cnt;
int ans[N];
bool cmp(int a, int b) { return dep[a] < dep[b]; }
inline int lca(int a, int b) {
  int l = st[a], r = st[b];
  if (l > r) swap(l, r);
  ++r;
  int lv = lg2(r - l);
  return min(ST[lv][l], ST[lv][r - (1 << lv)], cmp);
}
void dfs(int u = 1, int p = -1) {
  sz[u] = 1, ST[0][st[u] = ++cnt] = u;
  for (int i = 0; i < int(int(adj[u].size())); ++i)
    if (adj[u][i] != p) {
      dep[adj[u][i]] = dep[u] + 1;
      dfs(adj[u][i], u), ST[0][++cnt] = u;
      sz[u] += sz[adj[u][i]];
    }
}
struct Op {
  int u, v;
  void gao() {}
  void input() { RD(u, v); }
  bool operator<(const Op &r) const {
    return min(dep[u], dep[v]) < min(dep[r.u], dep[r.v]);
  }
};
vector<Op> op[N];
long long p = 1000000007, z;
long long pw(long long x, long long y) {
  long long _ = 1;
  for (; y; y >>= 1) {
    if (y & 1) _ = _ * x % p;
    x = x * x % p;
  }
  return _;
}
int a[100020], c[100020];
int b[100020], w;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", a + i), c[a[i]]++;
  for (int i = 1; i <= 100000; i++) c[i] += c[i - 1];
  sort(a, a + n);
  for (int i = 1; i <= a[n - 1]; i++) {
    w = 0;
    for (int j = 1; j * j <= i; j++)
      if (i % j == 0) {
        b[w++] = j;
        if (j * j != i) b[w++] = i / j;
      }
    sort(b, b + w);
    long long u = 1;
    for (int i = 1; i < w; i++) {
      u = u * pw(i, c[b[i] - 1] - c[b[i - 1] - 1]) % p;
    }
    z = (z +
         u * (pw(w, n - c[b[w - 1] - 1]) + p - pw(w - 1, n - c[b[w - 1] - 1])) %
             p) %
        p;
  }
  if (z < 0) z += p;
  cout << z << endl;
}
