Problem: An infinitely long Line Chillland Collider (LCC) was built in Chillland. There are n pipes with coordinates x_i that are connected to LCC. When the experiment starts at time 0, i-th proton flies from the i-th pipe with speed v_i. It flies to the right with probability p_i and flies to the left with probability (1 - p_i). The duration of the experiment is determined as the time of the first collision of any two protons. In case there is no collision, the duration of the experiment is considered to be zero.

Find the expected value of the duration of the experiment.

<image>Illustration for the first example

Input

The first line of input contains one integer n — the number of pipes (1 ≤ n ≤ 10^5). Each of the following n lines contains three integers x_i, v_i, p_i — the coordinate of the i-th pipe, the speed of the i-th proton and the probability that the i-th proton flies to the right in percentage points (-10^9 ≤ x_i ≤ 10^9, 1 ≤ v ≤ 10^6, 0 ≤ p_i ≤ 100). It is guaranteed that all x_i are distinct and sorted in increasing order.

Output

It's possible to prove that the answer can always be represented as a fraction P/Q, where P is an integer and Q is a natural number not divisible by 998 244 353. In this case, print P ⋅ Q^{-1} modulo 998 244 353.

Examples

Input


2
1 1 100
3 1 0


Output


1


Input


3
7 10 0
9 4 86
14 5 100


Output


0


Input


4
6 4 50
11 25 50
13 16 50
15 8 50


Output


150902884

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
struct mod_int {
  int val;
  mod_int(long long v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = v;
  }
  static int mod_inv(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int() const { return val; }
  mod_int &operator+=(const mod_int &other) {
    val += other.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  mod_int &operator-=(const mod_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return x % m;
    unsigned x_high = x >> 32, x_low = (unsigned)x;
    unsigned quot, rem;
    asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
    return rem;
  }
  mod_int &operator*=(const mod_int &other) {
    val = fast_mod((uint64_t)val * other.val);
    return *this;
  }
  mod_int &operator/=(const mod_int &other) { return *this *= other.inv(); }
  friend mod_int operator+(const mod_int &a, const mod_int &b) {
    return mod_int(a) += b;
  }
  friend mod_int operator-(const mod_int &a, const mod_int &b) {
    return mod_int(a) -= b;
  }
  friend mod_int operator*(const mod_int &a, const mod_int &b) {
    return mod_int(a) *= b;
  }
  friend mod_int operator/(const mod_int &a, const mod_int &b) {
    return mod_int(a) /= b;
  }
  mod_int &operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  mod_int &operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  mod_int operator++(int) {
    mod_int before = *this;
    ++*this;
    return before;
  }
  mod_int operator--(int) {
    mod_int before = *this;
    --*this;
    return before;
  }
  mod_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const mod_int &other) const { return val == other.val; }
  bool operator!=(const mod_int &other) const { return val != other.val; }
  mod_int inv() const { return mod_inv(val); }
  mod_int pow(long long p) const {
    assert(p >= 0);
    mod_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }
  friend ostream &operator<<(ostream &stream, const mod_int &m) {
    return stream << m.val;
  }
};
struct mod_matrix2 {
  mod_int values[2][2];
  mod_matrix2() {
    values[0][0] = values[0][1] = values[1][0] = values[1][1] = 0;
  }
  mod_matrix2(const vector<vector<mod_int>> &v) {
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) values[i][j] = v[i][j];
  }
  void make_identity() {
    values[0][0] = values[1][1] = 1;
    values[0][1] = values[1][0] = 0;
  }
  mod_matrix2 operator*(const mod_matrix2 &other) const {
    mod_matrix2 product;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        if (values[i][j] != 0)
          for (int k = 0; k < 2; k++)
            product.values[i][k] += values[i][j] * other.values[j][k];
    return product;
  }
  mod_matrix2 &operator*=(const mod_matrix2 &other) {
    return *this = *this * other;
  }
  mod_matrix2 power(long long p) const {
    assert(p >= 0);
    mod_matrix2 m = *this;
    mod_matrix2 result;
    result.make_identity();
    while (p > 0) {
      if (p & 1) result *= m;
      p >>= 1;
      if (p > 0) m *= m;
    }
    return result;
  }
  void print() const {
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) cout << values[i][j] << (j < 1 ? ' ' : '\n');
  }
};
struct segment {
  mod_matrix2 m;
  segment(mod_int m00 = 1, mod_int m01 = 0, mod_int m10 = 0, mod_int m11 = 1) {
    m = mod_matrix2({{m00, m01}, {m10, m11}});
  }
  void join(const segment &other) { m *= other.m; }
  void join(const segment &a, const segment &b) { m = a.m * b.m; }
};
int right_half[32];
struct basic_seg_tree {
  static const bool POWER_OF_TWO_MODE = true;
  int tree_n = 0;
  vector<segment> tree;
  basic_seg_tree(int n = -1) {
    if (n >= 0) init(n);
  }
  void init(int n) {
    if (POWER_OF_TWO_MODE) {
      tree_n = 1;
      while (tree_n < n) tree_n *= 2;
    } else {
      tree_n = n;
    }
    tree.assign(2 * tree_n, segment());
  }
  void build(const vector<segment> &initial) {
    int n = initial.size();
    init(n);
    assert(n <= tree_n);
    for (int i = 0; i < n; i++) tree[tree_n + i] = initial[i];
    for (int position = tree_n - 1; position > 0; position--)
      tree[position].join(tree[2 * position], tree[2 * position + 1]);
  }
  segment query(int a, int b) {
    assert(0 <= a && a <= b && b <= tree_n);
    segment answer;
    int r_size = 0;
    for (a += tree_n, b += tree_n; a < b; a /= 2, b /= 2) {
      if (a & 1) answer.join(tree[a++]);
      if (b & 1) right_half[r_size++] = --b;
    }
    for (int i = r_size - 1; i >= 0; i--) answer.join(tree[right_half[i]]);
    return answer;
  }
  segment query_single(int index) {
    assert(0 <= index && index < tree_n);
    return tree[tree_n + index];
  }
  void join_up(int position) {
    while (position > 1) {
      position /= 2;
      tree[position].join(tree[2 * position], tree[2 * position + 1]);
    }
  }
  void update(int index, const segment &seg) {
    assert(0 <= index && index < tree_n);
    int position = tree_n + index;
    tree[position] = seg;
    join_up(position);
  }
};
struct event {
  long long distance = 0, velocity = 1;
  int index;
  event() {}
  event(long long _distance, long long _velocity, int _index)
      : distance(_distance), velocity(_velocity), index(_index) {
    assert(distance >= 0 && velocity > 0);
  }
  mod_int get_time() const { return mod_int(distance) / velocity; }
  bool operator<(const event &other) const {
    return distance * other.velocity < other.distance * velocity;
  }
};
const long long DIST_INF = 2e9 + 5;
int N;
vector<int> X, V;
vector<mod_int> probability[2];
basic_seg_tree tree;
string status;
event build_event(int before, int after, int before_dir, int after_dir) {
  assert(after - before == 1);
  static const event EMPTY(DIST_INF, 1, 0);
  if (before_dir == 0 && after_dir == 1) return EMPTY;
  long long distance = X[after] - X[before];
  if (before_dir == 1 && after_dir == 0)
    return event(distance, V[before] + V[after], after);
  if (before_dir == 0 && after_dir == 0) {
    if (V[after] > V[before])
      return event(distance, V[after] - V[before], after);
    return EMPTY;
  }
  if (before_dir == 1 && after_dir == 1) {
    if (V[before] > V[after])
      return event(distance, V[before] - V[after], after);
    return EMPTY;
  }
  assert(false);
}
segment build_segment_for_time(int before, int after, event ev) {
  assert(after - before == 1);
  mod_int m[2][2] = {{0, 0}, {0, 0}};
  for (int before_dir = 0; before_dir < 2; before_dir++)
    for (int after_dir = 0; after_dir < 2; after_dir++)
      if (ev < build_event(before, after, before_dir, after_dir))
        m[before_dir][after_dir] = probability[after_dir][after];
  return segment(m[0][0], m[0][1], m[1][0], m[1][1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  X.resize(N);
  V.resize(N);
  probability[0].resize(N);
  probability[1].resize(N);
  const mod_int INV100 = mod_int(100).inv();
  for (int i = 0; i < N; i++) {
    int P;
    cin >> X[i] >> V[i] >> P;
    probability[1][i] = P * INV100;
    probability[0][i] = 1 - probability[1][i];
  }
  tree.init(N);
  vector<segment> initial(N);
  mod_matrix2 initial_vector({{1, 0}, {0, 0}});
  initial[0] = segment(probability[0][0], probability[1][0], 0, 0);
  const event ZERO(0, 1, 0);
  for (int i = 1; i < N; i++)
    initial[i] = build_segment_for_time(i - 1, i, ZERO);
  tree.build(initial);
  auto &&get_probability = [&]() {
    mod_matrix2 result = initial_vector * tree.tree[1].m;
    return result.values[0][0] + result.values[0][1];
  };
  vector<event> events;
  for (int i = 1; i < N; i++)
    for (int before_dir = 0; before_dir < 2; before_dir++)
      for (int after_dir = 0; after_dir < 2; after_dir++) {
        event ev = build_event(i - 1, i, before_dir, after_dir);
        if (ev.distance < DIST_INF) events.push_back(ev);
      }
  sort(events.begin(), events.end());
  mod_int total = 0, previous_time = 0;
  for (event &ev : events) {
    mod_int time = ev.get_time();
    total += get_probability() * (time - previous_time);
    tree.update(ev.index, build_segment_for_time(ev.index - 1, ev.index, ev));
    previous_time = time;
  }
  total -= get_probability() * previous_time;
  cout << total << '\n';
}