#include #include #include #include #include #include #include "atcoder/modint" using namespace std; using mint = atcoder::modint1000000007; class Sieve { private: const int _n; std::vector _max_prime_factor; std::vector _euler_phi; public: explicit Sieve(int n = 2'000'000): _n(n+1), _max_prime_factor(_n), _euler_phi(_n) { iota(_euler_phi.begin(), _euler_phi.end(), 0); for(int i=2; i<_n; i++) { if(_max_prime_factor[i]) continue; for(int j=i; j<_n; j+=i) { _max_prime_factor[j] = i; _euler_phi[j] -= _euler_phi[j]/i; } } } bool is_prime(int64_t n) const { assert(n > 0); if(n < _n) return (_max_prime_factor[n] == n); return atcoder::internal::is_prime_constexpr(n); } std::vector> prime_factorize(int64_t n) const { assert(n > 0); std::vector> res; if(n < _n) { while(n > 1) { int64_t p = _max_prime_factor[n]; int64_t exp = 0; while(_max_prime_factor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } std::reverse(res.begin(), res.end()); } else { for(int64_t i=2; i*i<=n; i++) { if(n%i == 0) { int exp = 0; while(n%i == 0) { n /= i; ++exp; } res.emplace_back(i, exp); } } if(n != 1) res.emplace_back(n, 1); } return res; } std::vector divisors(int64_t n) const { assert(n > 0); std::vector res = {1}; for(const auto [p, exp]: prime_factorize(n)) { int sz = res.size(); for(int i=0; i 0); if(n < _n) return _euler_phi[n]; int64_t res = n; for(const auto [p, exp]: prime_factorize(n)) { res -= res/p; } return res; } template std::vector divisor_transform(std::vector v) { int n = v.size(); assert(n <= _n); for(int i=2; i std::vector inverse_divisor_transform(std::vector v) { int n = v.size(); assert(n <= _n); for(int i=2; i0; j--) { v[j * i] -= v[j]; } } } return v; } template std::vector multiple_transform(std::vector v) { int n = v.size(); assert(n <= _n); for(int i=2; i0; j--) { v[j] += v[j * i]; } } } return v; } template std::vector inverse_multiple_transform(std::vector v) { int n = v.size(); assert(n <= _n); for(int i=2; i std::vector gcd_convolution(const std::vector &a, const std::vector &b) { assert(a.size() == b.size()); auto sum_a = multiple_transform(a); auto sum_b = multiple_transform(b); std::vector sum_c; std::transform(sum_a.begin(), sum_a.end(), sum_b.begin(), std::back_inserter(sum_c), std::multiplies()); return inverse_multiple_transform(sum_c); } template std::vector lcm_convolution(const std::vector &a, const std::vector &b) { assert(a.size() == b.size()); auto sum_a = divisor_transform(a); auto sum_b = divisor_transform(b); std::vector sum_c; std::transform(sum_a.begin(), sum_a.end(), sum_b.begin(), std::back_inserter(sum_c), std::multiplies()); return inverse_divisor_transform(sum_c); } }; int main(void) { cin.tie(nullptr); ios_base::sync_with_stdio(false); Sieve s(3'000'000); long long int H, W; cin >> H >> W; int M = max(H, W); vector h(M+1), w(M+1); for(int i=1; i