#include <bits/stdc++.h>
#pragma GCC optimize("O3")
namespace io {
class input_reader {
  std::istream &in;
  void throw_error() {
    throw std::runtime_error("No more inputs while reading number");
  }
  template <typename T>
  inline void readIntegerValue(T &f) {
    bool positive = true;
    f = 0;
    char c;
    if (!in.get(c)) throw_error();
    while (c < '0' || c > '9') {
      if (c == '-') positive = false;
      if (!in.get(c)) throw_error();
    }
    while (c >= '0' && c <= '9') {
      f = (f << 3) + (f << 1) + (c & 15);
      if (!in.get(c)) break;
    }
    if (!positive) f *= -1;
  }

 public:
  explicit input_reader(std::istream &in) : in(in) {}
  inline void read(int &f) { readIntegerValue(f); }
  inline void read(short &f) { readIntegerValue(f); }
  inline void read(long int &f) { readIntegerValue(f); }
  inline void read(long long int &f) { readIntegerValue(f); }
  inline void read(unsigned int &f) { readIntegerValue(f); }
  inline void read(unsigned short &f) { readIntegerValue(f); }
  inline void read(unsigned long int &f) { readIntegerValue(f); }
  inline void read(unsigned long long int &f) { readIntegerValue(f); }
  template <typename T>
  inline void read(std::vector<T> &f) {
    for (auto &i : f) read(i);
  }
  template <typename T, int N>
  inline void read(std::array<T, N> &res) {
    for (auto &i : res) read(i);
  }
  template <typename T1, typename T2>
  inline void read(std::pair<T1, T2> &p) {
    in.read(p.first, p.second);
  }
  template <typename T>
  inline void read(T &f) {
    in >> f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args &...args) {
    read(t), read(args...);
  }
  template <typename T>
  inline void readArray(int n, T *res) {
    while (n--) read(*(res++));
  }
  template <typename T>
  inline input_reader &operator>>(T &t) {
    return read(t), *this;
  }
};
}  // namespace io
namespace io {
class output_writer {
  std::ostream &out;
  template <typename T>
  inline void printIntegerHelper(T x) {
    if (x >= 10) printIntegerHelper(x / 10);
    out.put(x % 10 + 48);
  }
  template <typename T>
  inline void printInteger(T x) {
    if (x < 0) out.put('-'), x = -x;
    printIntegerHelper(x);
  }
  template <typename T>
  inline void printArray(T &ar) {
    bool first = true;
    for (auto &t : ar) print((first) ? first = false, "" : " ", t);
  }

 public:
  explicit output_writer(std::ostream &out) : out(out) {}
  inline void flush() { out.flush(); }
  inline void print() {}
  inline void print(char x) { out.put(x); }
  inline void print(short x) { printInteger(x); }
  inline void print(int x) { printInteger(x); }
  inline void print(long int x) { printInteger(x); }
  inline void print(long long int x) { printInteger(x); }
  inline void print(unsigned short x) { printInteger(x); }
  inline void print(unsigned int x) { printInteger(x); }
  inline void print(unsigned long int x) { printInteger(x); }
  inline void print(unsigned long long int x) { printInteger(x); }
  template <typename T1>
  inline void print(const T1 &t1) {
    out << t1;
  }
  template <typename T1>
  inline void print(const std::vector<T1> &t1) {
    printArray(t1);
  }
  template <typename T1, int N>
  inline void print(const std::array<T1, N> &t1) {
    printArray(t1);
  }
  template <typename T1, int N, int M>
  inline void print(const std::array<std::array<T1, M>, N> &t1) {
    for (auto &t : t1) println(t);
  }
  template <typename T1>
  inline void print(const std::vector<std::vector<T1>> &t1) {
    for (auto &t : t1) println(t);
  }
  template <typename T, typename... Args>
  inline void print(const T &t, Args... args) {
    print(t), print(args...);
  }
  template <typename... Args>
  inline void println(Args... args) {
    print(args...), print('\n');
  }
  template <typename T>
  output_writer &operator<<(const T &t) {
    return print(t), *this;
  }
};
}  // namespace io
inline long long int pow_mod(const long long int a, const long long int b,
                             const long long int MOD) {
  if (b == 0) return 1;
  if (b == 1) return a % MOD;
  long long int res = pow_mod(a * a % MOD, b >> 1, MOD);
  if (b & 1) res = res * a % MOD;
  return res % MOD;
}
inline long long int mod_inv(const long long int a, const long long int MOD) {
  return pow_mod(a, MOD - 2, MOD);
}
template <typename T>
T gcd(const T &a, const T &b) {
  if (*a == 0) return b;
  return gcd(b % a, a);
}
template <typename T>
T lcm(const T &a, const T &b) {
  assert(a != 0 && b != 0);
  return a / gcd(a, b) * b;
}
using namespace std;
class DFrogJumping {
  class Solver {
    io::input_reader in;
    io::output_writer out;

   public:
    Solver(std::istream &in, std::ostream &out) : in(in), out(out) {}
    long long int seqsum(long long int i, long long int j) {
      if (i > j) return 0;
      return (abs(i - j) + 1) * (j + i) / 2;
    }
    long long int sum_number_of_unique_values(int m, int a, int from_index,
                                              int start_index) {
      long long int total = 0;
      int first_rep_index = (from_index - start_index) / a;
      int last_rep_index = (m - start_index) / a;
      total += seqsum(first_rep_index + 1 + 1, last_rep_index - 1 + 1) * a;
      if (first_rep_index != last_rep_index) {
        long long int first_rep_size =
            first_rep_index * a + a + start_index - from_index;
        total += first_rep_size * (first_rep_index + 1);
        long long int last_rep_size =
            m - (last_rep_index * a + start_index) + 1;
        total += last_rep_size * (last_rep_index + 1);
      } else {
        long long int last_rep_size = m - from_index + 1;
        total += (last_rep_index + 1) * last_rep_size;
      }
      return total;
    }
    void solve() {
      int m, a, b;
      in.read(m, a, b);
      long long int total = 0;
      int current = 0;
      int current_start = 0;
      int real_start = 0;
      vector<int> moda(a + 1, -1);
      while (true) {
        if (moda[current % a] == -1) {
          total += sum_number_of_unique_values(m, a, real_start, current);
          moda[current % a] = current;
        } else {
          if (moda[current % a] > current) {
            total += sum_number_of_unique_values(m, a, real_start, current);
            total -= sum_number_of_unique_values(m, a, real_start,
                                                 moda[current % a]);
            moda[current % a] = current;
          }
          if (current == 0) break;
        }
        if (current >= b) {
          current -= b;
        } else {
          int next_who_is_greater_then_b =
              ((b - current + a - 1) / a) * a + current;
          current_start = next_who_is_greater_then_b;
          current = current_start - b;
          real_start = max(current_start, real_start);
          if (real_start > m) break;
        }
      }
      out << total;
      total += a;
    }
  };

 public:
  void solve(std::istream &in, std::ostream &out) { Solver(in, out).solve(); }
};
int main() {
  std::ios_base::sync_with_stdio(false), cin.tie(0);
  DFrogJumping solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

A frog is initially at position 0 on the number line. The frog has two positive integers a and b. From a position k, it can either jump to position k+a or k-b.

Let f(x) be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval [0, x]. The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from 0.

Given an integer m, find ∑_{i=0}^{m} f(i). That is, find the sum of all f(i) for i from 0 to m.

Input

The first line contains three integers m, a, b (1 ≤ m ≤ 10^9, 1 ≤ a,b ≤ 10^5).

Output

Print a single integer, the desired sum.

Examples

Input


7 5 3


Output


19


Input


1000000000 1 2019


Output


500000001500000001


Input


100 100000 1


Output


101


Input


6 4 5


Output


10

Note

In the first example, we must find f(0)+f(1)+…+f(7). We have f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8. The sum of these values is 19.

In the second example, we have f(i) = i+1, so we want to find ∑_{i=0}^{10^9} i+1.

In the third example, the frog can't make any jumps in any case.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
namespace io {
class input_reader {
  std::istream &in;
  void throw_error() {
    throw std::runtime_error("No more inputs while reading number");
  }
  template <typename T>
  inline void readIntegerValue(T &f) {
    bool positive = true;
    f = 0;
    char c;
    if (!in.get(c)) throw_error();
    while (c < '0' || c > '9') {
      if (c == '-') positive = false;
      if (!in.get(c)) throw_error();
    }
    while (c >= '0' && c <= '9') {
      f = (f << 3) + (f << 1) + (c & 15);
      if (!in.get(c)) break;
    }
    if (!positive) f *= -1;
  }

 public:
  explicit input_reader(std::istream &in) : in(in) {}
  inline void read(int &f) { readIntegerValue(f); }
  inline void read(short &f) { readIntegerValue(f); }
  inline void read(long int &f) { readIntegerValue(f); }
  inline void read(long long int &f) { readIntegerValue(f); }
  inline void read(unsigned int &f) { readIntegerValue(f); }
  inline void read(unsigned short &f) { readIntegerValue(f); }
  inline void read(unsigned long int &f) { readIntegerValue(f); }
  inline void read(unsigned long long int &f) { readIntegerValue(f); }
  template <typename T>
  inline void read(std::vector<T> &f) {
    for (auto &i : f) read(i);
  }
  template <typename T, int N>
  inline void read(std::array<T, N> &res) {
    for (auto &i : res) read(i);
  }
  template <typename T1, typename T2>
  inline void read(std::pair<T1, T2> &p) {
    in.read(p.first, p.second);
  }
  template <typename T>
  inline void read(T &f) {
    in >> f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args &...args) {
    read(t), read(args...);
  }
  template <typename T>
  inline void readArray(int n, T *res) {
    while (n--) read(*(res++));
  }
  template <typename T>
  inline input_reader &operator>>(T &t) {
    return read(t), *this;
  }
};
}  // namespace io
namespace io {
class output_writer {
  std::ostream &out;
  template <typename T>
  inline void printIntegerHelper(T x) {
    if (x >= 10) printIntegerHelper(x / 10);
    out.put(x % 10 + 48);
  }
  template <typename T>
  inline void printInteger(T x) {
    if (x < 0) out.put('-'), x = -x;
    printIntegerHelper(x);
  }
  template <typename T>
  inline void printArray(T &ar) {
    bool first = true;
    for (auto &t : ar) print((first) ? first = false, "" : " ", t);
  }

 public:
  explicit output_writer(std::ostream &out) : out(out) {}
  inline void flush() { out.flush(); }
  inline void print() {}
  inline void print(char x) { out.put(x); }
  inline void print(short x) { printInteger(x); }
  inline void print(int x) { printInteger(x); }
  inline void print(long int x) { printInteger(x); }
  inline void print(long long int x) { printInteger(x); }
  inline void print(unsigned short x) { printInteger(x); }
  inline void print(unsigned int x) { printInteger(x); }
  inline void print(unsigned long int x) { printInteger(x); }
  inline void print(unsigned long long int x) { printInteger(x); }
  template <typename T1>
  inline void print(const T1 &t1) {
    out << t1;
  }
  template <typename T1>
  inline void print(const std::vector<T1> &t1) {
    printArray(t1);
  }
  template <typename T1, int N>
  inline void print(const std::array<T1, N> &t1) {
    printArray(t1);
  }
  template <typename T1, int N, int M>
  inline void print(const std::array<std::array<T1, M>, N> &t1) {
    for (auto &t : t1) println(t);
  }
  template <typename T1>
  inline void print(const std::vector<std::vector<T1>> &t1) {
    for (auto &t : t1) println(t);
  }
  template <typename T, typename... Args>
  inline void print(const T &t, Args... args) {
    print(t), print(args...);
  }
  template <typename... Args>
  inline void println(Args... args) {
    print(args...), print('\n');
  }
  template <typename T>
  output_writer &operator<<(const T &t) {
    return print(t), *this;
  }
};
}  // namespace io
inline long long int pow_mod(const long long int a, const long long int b,
                             const long long int MOD) {
  if (b == 0) return 1;
  if (b == 1) return a % MOD;
  long long int res = pow_mod(a * a % MOD, b >> 1, MOD);
  if (b & 1) res = res * a % MOD;
  return res % MOD;
}
inline long long int mod_inv(const long long int a, const long long int MOD) {
  return pow_mod(a, MOD - 2, MOD);
}
template <typename T>
T gcd(const T &a, const T &b) {
  if (*a == 0) return b;
  return gcd(b % a, a);
}
template <typename T>
T lcm(const T &a, const T &b) {
  assert(a != 0 && b != 0);
  return a / gcd(a, b) * b;
}
using namespace std;
class DFrogJumping {
  class Solver {
    io::input_reader in;
    io::output_writer out;

   public:
    Solver(std::istream &in, std::ostream &out) : in(in), out(out) {}
    long long int seqsum(long long int i, long long int j) {
      if (i > j) return 0;
      return (abs(i - j) + 1) * (j + i) / 2;
    }
    long long int sum_number_of_unique_values(int m, int a, int from_index,
                                              int start_index) {
      long long int total = 0;
      int first_rep_index = (from_index - start_index) / a;
      int last_rep_index = (m - start_index) / a;
      total += seqsum(first_rep_index + 1 + 1, last_rep_index - 1 + 1) * a;
      if (first_rep_index != last_rep_index) {
        long long int first_rep_size =
            first_rep_index * a + a + start_index - from_index;
        total += first_rep_size * (first_rep_index + 1);
        long long int last_rep_size =
            m - (last_rep_index * a + start_index) + 1;
        total += last_rep_size * (last_rep_index + 1);
      } else {
        long long int last_rep_size = m - from_index + 1;
        total += (last_rep_index + 1) * last_rep_size;
      }
      return total;
    }
    void solve() {
      int m, a, b;
      in.read(m, a, b);
      long long int total = 0;
      int current = 0;
      int current_start = 0;
      int real_start = 0;
      vector<int> moda(a + 1, -1);
      while (true) {
        if (moda[current % a] == -1) {
          total += sum_number_of_unique_values(m, a, real_start, current);
          moda[current % a] = current;
        } else {
          if (moda[current % a] > current) {
            total += sum_number_of_unique_values(m, a, real_start, current);
            total -= sum_number_of_unique_values(m, a, real_start,
                                                 moda[current % a]);
            moda[current % a] = current;
          }
          if (current == 0) break;
        }
        if (current >= b) {
          current -= b;
        } else {
          int next_who_is_greater_then_b =
              ((b - current + a - 1) / a) * a + current;
          current_start = next_who_is_greater_then_b;
          current = current_start - b;
          real_start = max(current_start, real_start);
          if (real_start > m) break;
        }
      }
      out << total;
      total += a;
    }
  };

 public:
  void solve(std::istream &in, std::ostream &out) { Solver(in, out).solve(); }
};
int main() {
  std::ios_base::sync_with_stdio(false), cin.tie(0);
  DFrogJumping solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}

```