#include <bits/stdc++.h>
template <typename T>
T extended_gcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extended_gcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
T identity();
template <typename T, typename Enable = std::true_type>
struct impl__IdentityHelper {};
template <typename T>
struct impl__SampleIdentityHelper {
  static T identity(const T&) { return ::identity<T>(); }
};
template <typename T>
struct impl__IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity(const T& sample) {
  return impl__SampleIdentityHelper<T>::identity(sample);
}
template <typename T>
T identity() {
  return impl__IdentityHelper<T>::identity();
}
template <bool normalize>
struct impl__Normalizator {};
template <>
struct impl__Normalizator<true> {
  static void softUp(long long& value, long long mod) {
    if (value < 0) {
      value += mod;
    }
  }
  static void softDown(long long& value, long long mod) {
    if (value >= mod) {
      value -= mod;
    }
  }
  static void hardDown(long long& value, long long mod) { value %= mod; }
  static void hard(long long& value, long long mod) {
    value %= mod;
    softUp(value, mod);
  }
};
template <>
struct impl__Normalizator<false> {
  static void softUp(long long& value, long long mod) {}
  static void softDown(long long& value, long long mod) {}
  static void hardDown(long long& value, long long mod) {}
  static void hard(long long& value, long long mod) {}
};
template <bool autoNormalize = true>
class Zn {
 public:
  Zn() : mod(0), value(0) {}
  explicit Zn(long long mod) : mod(mod), value(0) {}
  static Zn valueOf(long long mod, long long value) {
    impl__Normalizator<true>::hard(value, mod);
    return Zn(mod, value);
  }
  Zn& operator+=(const Zn& rhs) {
    ;
    value += rhs.value;
    impl__Normalizator<autoNormalize>::softDown(value, mod);
    return *this;
  }
  Zn& operator+=(long long rhs) { return *this += Zn::valueOf(mod, rhs); }
  Zn& operator-=(const Zn& rhs) {
    ;
    value -= rhs.value;
    impl__Normalizator<autoNormalize>::softUp(value, mod);
    return *this;
  }
  Zn& operator-=(long long rhs) { return *this -= Zn::valueOf(mod, rhs); }
  Zn& operator*=(const Zn& rhs) {
    ;
    value *= rhs.value;
    impl__Normalizator<autoNormalize>::hardDown(value, mod);
    return *this;
  }
  Zn& operator*=(long long rhs) { return *this *= Zn::valueOf(mod, rhs); }
  void normalize() const {
    long long& value = const_cast<long long&>(this->value);
    impl__Normalizator<!autoNormalize>::hard(value, mod);
  }
  Zn operator-() const {
    Zn result(mod, mod - value);
    impl__Normalizator<autoNormalize>::softDown(result.value, mod);
    return result;
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  Zn& operator/=(long long rhs) { return *this /= Zn::valueOf(mod, rhs); }
  bool operator==(const Zn& rhs) const {
    ;
    normalize();
    rhs.normalize();
    return value == rhs.value;
  }
  Zn inversed() const {
    ;
    normalize();
    long long x, y;
    long long gcd = extended_gcd(value, mod, x, y);
    ;
    impl__Normalizator<autoNormalize>::softUp(x, mod);
    return Zn(mod, x);
  }
  template <bool aF>
  friend std::ostream& operator<<(std::ostream&, const Zn<aF>& zn);
  template <bool aF>
  friend std::istream& operator>>(std::istream&, Zn<aF>& zn);
  long long longValue() const { return value; }
  long long mod;

 private:
  Zn(long long mod, long long value) : mod(mod), value(value) { ; }
  long long value;
};
template <bool a>
Zn<a> operator+(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy += rhs;
}
template <bool a>
Zn<a> operator+(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy += rhs;
}
template <bool a>
Zn<a> operator-(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy -= rhs;
}
template <bool a>
Zn<a> operator-(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy -= rhs;
}
template <bool a>
Zn<a> operator*(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy *= rhs;
}
template <bool a>
Zn<a> operator*(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy *= rhs;
}
template <bool a>
Zn<a> operator/(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy /= rhs;
}
template <bool a>
Zn<a> operator/(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy /= rhs;
}
template <bool a>
std::ostream& operator<<(std::ostream& stream, const Zn<a>& zn) {
  zn.normalize();
  return stream << zn.value;
}
template <bool a>
std::istream& operator>>(std::istream& stream, Zn<a>& zn) {
  stream >> zn.value;
  impl__Normalizator<a>::hard(zn.value, zn.mod);
  return stream;
}
template <bool a>
struct impl__SampleIdentityHelper<Zn<a>> {
  static Zn<a> identity(const Zn<a>& sample) {
    return Zn<a>::valueOf(sample.mod, 1);
  }
};
using namespace std;
const int mod = 1000000007;
class TaskD {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    children.resize(n);
    for (int i = 1; i < n; ++i) {
      int x;
      in >> x;
      --x;
      children[x].push_back(i);
    }
    dp1.resize(n);
    dpe.resize(n);
    go(0);
    dp2.resize(n);
    go2(0, 0);
    for (int i = 0; i < n; ++i) {
      out << dp2[i] << ' ';
    }
  }
  vector<vector<int>> children;
  vector<long long> dp1;
  vector<vector<long long>> dpe;
  vector<long long> dp2;
  void go(int v) {
    dpe[v].resize(children[v].size());
    int zeros = 0;
    dp1[v] = 1;
    for (int to : children[v]) {
      go(to);
      if (1 + dp1[to] == mod) {
        zeros++;
      } else {
        dp1[v] *= 1 + dp1[to];
        dp1[v] %= mod;
      }
    }
    if (zeros >= 2) {
      for (int i = 0; i < dpe[v].size(); ++i) {
        dpe[v][i] = 0;
      }
      dp1[v] = 0;
    }
    if (zeros == 1) {
      for (int i = 0; i < dpe[v].size(); ++i) {
        if (1 + dp1[children[v][i]] == mod)
          dpe[v][i] = dp1[v];
        else
          dpe[v][i] = 0;
      }
      dp1[v] = 0;
    }
    if (zeros == 0) {
      for (int i = 0; i < dpe[v].size(); ++i) {
        dpe[v][i] = (Zn<>::valueOf(mod, dp1[v]) /
                     Zn<>::valueOf(mod, 1 + dp1[children[v][i]]))
                        .longValue();
      }
    }
  }
  void go2(int v, long long dpup) {
    dp2[v] = dp1[v] * 1LL * (1 + dpup) % mod;
    for (int i = 0; i < children[v].size(); ++i) {
      int to = children[v][i];
      go2(to, dpe[v][i] * 1LL * (1 + dpup) % mod);
    }
  }
};
int main() {
  std::cin.sync_with_stdio(false);
  std::cin.tie(0);
  std::cout << std::fixed;
  std::cout.precision(20);
  TaskD solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

The country has n cities and n - 1 bidirectional roads, it is possible to get from every city to any other one if you move only along the roads. The cities are numbered with integers from 1 to n inclusive.

All the roads are initially bad, but the government wants to improve the state of some roads. We will assume that the citizens are happy about road improvement if the path from the capital located in city x to any other city contains at most one bad road.

Your task is — for every possible x determine the number of ways of improving the quality of some roads in order to meet the citizens' condition. As those values can be rather large, you need to print each value modulo 1 000 000 007 (109 + 7).

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 2·105) — the number of cities in the country. Next line contains n - 1 positive integers p2, p3, p4, ..., pn (1 ≤ pi ≤ i - 1) — the description of the roads in the country. Number pi means that the country has a road connecting city pi and city i. 

Output

Print n integers a1, a2, ..., an, where ai is the sought number of ways to improve the quality of the roads modulo 1 000 000 007 (109 + 7), if the capital of the country is at city number i.

Examples

Input

3
1 1


Output

4 3 3

Input

5
1 2 3 4


Output

5 8 9 8 5

### Response

```cpp
#include <bits/stdc++.h>
template <typename T>
T extended_gcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extended_gcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
T identity();
template <typename T, typename Enable = std::true_type>
struct impl__IdentityHelper {};
template <typename T>
struct impl__SampleIdentityHelper {
  static T identity(const T&) { return ::identity<T>(); }
};
template <typename T>
struct impl__IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity(const T& sample) {
  return impl__SampleIdentityHelper<T>::identity(sample);
}
template <typename T>
T identity() {
  return impl__IdentityHelper<T>::identity();
}
template <bool normalize>
struct impl__Normalizator {};
template <>
struct impl__Normalizator<true> {
  static void softUp(long long& value, long long mod) {
    if (value < 0) {
      value += mod;
    }
  }
  static void softDown(long long& value, long long mod) {
    if (value >= mod) {
      value -= mod;
    }
  }
  static void hardDown(long long& value, long long mod) { value %= mod; }
  static void hard(long long& value, long long mod) {
    value %= mod;
    softUp(value, mod);
  }
};
template <>
struct impl__Normalizator<false> {
  static void softUp(long long& value, long long mod) {}
  static void softDown(long long& value, long long mod) {}
  static void hardDown(long long& value, long long mod) {}
  static void hard(long long& value, long long mod) {}
};
template <bool autoNormalize = true>
class Zn {
 public:
  Zn() : mod(0), value(0) {}
  explicit Zn(long long mod) : mod(mod), value(0) {}
  static Zn valueOf(long long mod, long long value) {
    impl__Normalizator<true>::hard(value, mod);
    return Zn(mod, value);
  }
  Zn& operator+=(const Zn& rhs) {
    ;
    value += rhs.value;
    impl__Normalizator<autoNormalize>::softDown(value, mod);
    return *this;
  }
  Zn& operator+=(long long rhs) { return *this += Zn::valueOf(mod, rhs); }
  Zn& operator-=(const Zn& rhs) {
    ;
    value -= rhs.value;
    impl__Normalizator<autoNormalize>::softUp(value, mod);
    return *this;
  }
  Zn& operator-=(long long rhs) { return *this -= Zn::valueOf(mod, rhs); }
  Zn& operator*=(const Zn& rhs) {
    ;
    value *= rhs.value;
    impl__Normalizator<autoNormalize>::hardDown(value, mod);
    return *this;
  }
  Zn& operator*=(long long rhs) { return *this *= Zn::valueOf(mod, rhs); }
  void normalize() const {
    long long& value = const_cast<long long&>(this->value);
    impl__Normalizator<!autoNormalize>::hard(value, mod);
  }
  Zn operator-() const {
    Zn result(mod, mod - value);
    impl__Normalizator<autoNormalize>::softDown(result.value, mod);
    return result;
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  Zn& operator/=(long long rhs) { return *this /= Zn::valueOf(mod, rhs); }
  bool operator==(const Zn& rhs) const {
    ;
    normalize();
    rhs.normalize();
    return value == rhs.value;
  }
  Zn inversed() const {
    ;
    normalize();
    long long x, y;
    long long gcd = extended_gcd(value, mod, x, y);
    ;
    impl__Normalizator<autoNormalize>::softUp(x, mod);
    return Zn(mod, x);
  }
  template <bool aF>
  friend std::ostream& operator<<(std::ostream&, const Zn<aF>& zn);
  template <bool aF>
  friend std::istream& operator>>(std::istream&, Zn<aF>& zn);
  long long longValue() const { return value; }
  long long mod;

 private:
  Zn(long long mod, long long value) : mod(mod), value(value) { ; }
  long long value;
};
template <bool a>
Zn<a> operator+(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy += rhs;
}
template <bool a>
Zn<a> operator+(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy += rhs;
}
template <bool a>
Zn<a> operator-(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy -= rhs;
}
template <bool a>
Zn<a> operator-(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy -= rhs;
}
template <bool a>
Zn<a> operator*(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy *= rhs;
}
template <bool a>
Zn<a> operator*(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy *= rhs;
}
template <bool a>
Zn<a> operator/(const Zn<a>& lhs, const Zn<a>& rhs) {
  Zn<a> copy = lhs;
  return copy /= rhs;
}
template <bool a>
Zn<a> operator/(const Zn<a>& lhs, long long rhs) {
  Zn<a> copy = lhs;
  return copy /= rhs;
}
template <bool a>
std::ostream& operator<<(std::ostream& stream, const Zn<a>& zn) {
  zn.normalize();
  return stream << zn.value;
}
template <bool a>
std::istream& operator>>(std::istream& stream, Zn<a>& zn) {
  stream >> zn.value;
  impl__Normalizator<a>::hard(zn.value, zn.mod);
  return stream;
}
template <bool a>
struct impl__SampleIdentityHelper<Zn<a>> {
  static Zn<a> identity(const Zn<a>& sample) {
    return Zn<a>::valueOf(sample.mod, 1);
  }
};
using namespace std;
const int mod = 1000000007;
class TaskD {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    children.resize(n);
    for (int i = 1; i < n; ++i) {
      int x;
      in >> x;
      --x;
      children[x].push_back(i);
    }
    dp1.resize(n);
    dpe.resize(n);
    go(0);
    dp2.resize(n);
    go2(0, 0);
    for (int i = 0; i < n; ++i) {
      out << dp2[i] << ' ';
    }
  }
  vector<vector<int>> children;
  vector<long long> dp1;
  vector<vector<long long>> dpe;
  vector<long long> dp2;
  void go(int v) {
    dpe[v].resize(children[v].size());
    int zeros = 0;
    dp1[v] = 1;
    for (int to : children[v]) {
      go(to);
      if (1 + dp1[to] == mod) {
        zeros++;
      } else {
        dp1[v] *= 1 + dp1[to];
        dp1[v] %= mod;
      }
    }
    if (zeros >= 2) {
      for (int i = 0; i < dpe[v].size(); ++i) {
        dpe[v][i] = 0;
      }
      dp1[v] = 0;
    }
    if (zeros == 1) {
      for (int i = 0; i < dpe[v].size(); ++i) {
        if (1 + dp1[children[v][i]] == mod)
          dpe[v][i] = dp1[v];
        else
          dpe[v][i] = 0;
      }
      dp1[v] = 0;
    }
    if (zeros == 0) {
      for (int i = 0; i < dpe[v].size(); ++i) {
        dpe[v][i] = (Zn<>::valueOf(mod, dp1[v]) /
                     Zn<>::valueOf(mod, 1 + dp1[children[v][i]]))
                        .longValue();
      }
    }
  }
  void go2(int v, long long dpup) {
    dp2[v] = dp1[v] * 1LL * (1 + dpup) % mod;
    for (int i = 0; i < children[v].size(); ++i) {
      int to = children[v][i];
      go2(to, dpe[v][i] * 1LL * (1 + dpup) % mod);
    }
  }
};
int main() {
  std::cin.sync_with_stdio(false);
  std::cin.tie(0);
  std::cout << std::fixed;
  std::cout.precision(20);
  TaskD solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

```