結果
問題 | No.1919 Many Monster Battles |
ユーザー |
|
提出日時 | 2022-04-30 01:03:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 41,386 bytes |
コンパイル時間 | 2,799 ms |
コンパイル使用メモリ | 223,616 KB |
最終ジャッジ日時 | 2025-01-29 00:43:51 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In instantiation of ‘std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&) [with T = atcoder::static_modint<1000000007>; std::ostream = std::basic_ostream<char>]’: main.cpp:151:15: required from ‘void print(const Head&, const Tail& ...) [with Head = std::vector<atcoder::static_modint<1000000007> >; Tail = {}]’ main.cpp:1269:10: required from here main.cpp:134:13: error: no match for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘const atcoder::static_modint<1000000007>’) 134 | out << *it; | ~~~~^~~~~~ In file included from /usr/include/c++/13/istream:41, from /usr/include/c++/13/sstream:40, from /usr/include/c++/13/complex:45, from /usr/include/c++/13/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127, from main.cpp:7: /usr/include/c++/13/ostream:110:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(__ostream_type& (*)(__ostream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’ 110 | operator<<(__ostream_type& (*__pf)(__ostream_type&)) | ^~~~~~~~ /usr/include/c++/13/ostream:110:36: note: no known conversion for argument 1 from ‘const atcoder::static_modint<1000000007>’ to ‘std::basic_ostream<char>::__ostream_type& (*)(std::basic_ostream<char>::__ostream_type&)’ {aka ‘std::basic_ostream<char>& (*)(std::basic_ostream<char>&)’} 110 | operator<<(__ostream_type& (*__pf)(__ostream_type&)) | ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/13/ostream:119:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(__ios_type& (*)(__ios_type&)) [with _CharT = char; _Traits = std::char_traits<cha
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")// #pragma comment(linker, "/stack:200000000")#include <bits/stdc++.h>#include <limits>#include <type_traits>namespace suisen {// ! utilitytemplate <typename ...Types>using constraints_t = std::enable_if_t<std::conjunction_v<Types...>, std::nullptr_t>;template <bool cond_v, typename Then, typename OrElse>constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) {if constexpr (cond_v) {return std::forward<Then>(then);} else {return std::forward<OrElse>(or_else);}}// ! functiontemplate <typename ReturnType, typename Callable, typename ...Args>using is_same_as_invoke_result = std::is_same<std::invoke_result_t<Callable, Args...>, ReturnType>;template <typename F, typename T>using is_uni_op = is_same_as_invoke_result<T, F, T>;template <typename F, typename T>using is_bin_op = is_same_as_invoke_result<T, F, T, T>;template <typename Comparator, typename T>using is_comparator = std::is_same<std::invoke_result_t<Comparator, T, T>, bool>;// ! integraltemplate <typename T, typename = constraints_t<std::is_integral<T>>>constexpr int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits;template <typename T, unsigned int n>struct is_nbit { static constexpr bool value = bit_num<T> == n; };template <typename T, unsigned int n>static constexpr bool is_nbit_v = is_nbit<T, n>::value;// ?template <typename T>struct safely_multipliable {};template <>struct safely_multipliable<int> { using type = long long; };template <>struct safely_multipliable<long long> { using type = __int128_t; };template <>struct safely_multipliable<unsigned int> { using type = unsigned long long; };template <>struct safely_multipliable<unsigned long long> { using type = __uint128_t; };template <>struct safely_multipliable<float> { using type = float; };template <>struct safely_multipliable<double> { using type = double; };template <>struct safely_multipliable<long double> { using type = long double; };template <typename T>using safely_multipliable_t = typename safely_multipliable<T>::type;} // namespace suisen// ! type aliasesusing i128 = __int128_t;using u128 = __uint128_t;using ll = long long;using uint = unsigned int;using ull = unsigned long long;template <typename T> using vec = std::vector<T>;template <typename T> using vec2 = vec<vec <T>>;template <typename T> using vec3 = vec<vec2<T>>;template <typename T> using vec4 = vec<vec3<T>>;template <typename T>using pq_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>;template <typename T, typename U>using umap = std::unordered_map<T, U>;// ! macros (capital: internal macro)#define OVERLOAD2(_1,_2,name,...) name#define OVERLOAD3(_1,_2,_3,name,...) name#define OVERLOAD4(_1,_2,_3,_4,name,...) name#define REP4(i,l,r,s) for(std::remove_reference_t<std::remove_const_t<decltype(r)>>i=(l);i<(r);i+=(s))#define REP3(i,l,r) REP4(i,l,r,1)#define REP2(i,n) REP3(i,0,n)#define REPINF3(i,l,s) for(std::remove_reference_t<std::remove_const_t<decltype(l)>>i=(l);;i+=(s))#define REPINF2(i,l) REPINF3(i,l,1)#define REPINF1(i) REPINF2(i,0)#define RREP4(i,l,r,s) for(std::remove_reference_t<std::remove_const_t<decltype(r)>>i=(l)+fld((r)-(l)-1,s)*(s);i>=(l);i-=(s))#define RREP3(i,l,r) RREP4(i,l,r,1)#define RREP2(i,n) RREP3(i,0,n)#define rep(...) OVERLOAD4(__VA_ARGS__, REP4 , REP3 , REP2 )(__VA_ARGS__)#define rrep(...) OVERLOAD4(__VA_ARGS__, RREP4 , RREP3 , RREP2 )(__VA_ARGS__)#define repinf(...) OVERLOAD3(__VA_ARGS__, REPINF3, REPINF2, REPINF1)(__VA_ARGS__)#define CAT_I(a, b) a##b#define CAT(a, b) CAT_I(a, b)#define UNIQVAR(tag) CAT(tag, __LINE__)#define loop(n) for (std::remove_reference_t<std::remove_const_t<decltype(n)>> UNIQVAR(loop_variable) = n; UNIQVAR(loop_variable) --> 0;)#define all(iterable) (iterable).begin(), (iterable).end()#define input(type, ...) type __VA_ARGS__; read(__VA_ARGS__)// ! I/O utilities// pairtemplate <typename T, typename U>std::ostream& operator<<(std::ostream& out, const std::pair<T, U> &a) {return out << a.first << ' ' << a.second;}// tupletemplate <unsigned int N = 0, typename ...Args>std::ostream& operator<<(std::ostream& out, const std::tuple<Args...> &a) {if constexpr (N >= std::tuple_size_v<std::tuple<Args...>>) {return out;} else {out << std::get<N>(a);if constexpr (N + 1 < std::tuple_size_v<std::tuple<Args...>>) {out << ' ';}return operator<<<N + 1>(out, a);}}// vectortemplate <typename T>std::ostream& operator<<(std::ostream& out, const std::vector<T> &a) {for (auto it = a.begin(); it != a.end();) {out << *it;if (++it != a.end()) out << ' ';}return out;}// arraytemplate <typename T, size_t N>std::ostream& operator<<(std::ostream& out, const std::array<T, N> &a) {for (auto it = a.begin(); it != a.end();) {out << *it;if (++it != a.end()) out << ' ';}return out;}inline void print() { std::cout << '\n'; }template <typename Head, typename... Tail>inline void print(const Head &head, const Tail &...tails) {std::cout << head;if (sizeof...(tails)) std::cout << ' ';print(tails...);}template <typename Iterable>auto print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") -> decltype(std::cout << *v.begin(), void()) {for (auto it = v.begin(); it != v.end();) {std::cout << *it;if (++it != v.end()) std::cout << sep;}std::cout << end;}// pairtemplate <typename T, typename U>std::istream& operator>>(std::istream& in, std::pair<T, U> &a) {return in >> a.first >> a.second;}// tupletemplate <unsigned int N = 0, typename ...Args>std::istream& operator>>(std::istream& in, std::tuple<Args...> &a) {if constexpr (N >= std::tuple_size_v<std::tuple<Args...>>) {return in;} else {return operator>><N + 1>(in >> std::get<N>(a), a);}}// vectortemplate <typename T>std::istream& operator>>(std::istream& in, std::vector<T> &a) {for (auto it = a.begin(); it != a.end(); ++it) in >> *it;return in;}// arraytemplate <typename T, size_t N>std::istream& operator>>(std::istream& in, std::array<T, N> &a) {for (auto it = a.begin(); it != a.end(); ++it) in >> *it;return in;}template <typename ...Args>void read(Args &...args) {( std::cin >> ... >> args );}// ! integral utilities// Returns pow(-1, n)template <typename T>constexpr inline int pow_m1(T n) {return -(n & 1) | 1;}// Returns pow(-1, n)template <>constexpr inline int pow_m1<bool>(bool n) {return -int(n) | 1;}// Returns floor(x / y)template <typename T>constexpr inline T fld(const T x, const T y) {return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y;}template <typename T>constexpr inline T cld(const T x, const T y) {return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y;}template <typename T, suisen::constraints_t<suisen::is_nbit<T, 16>> = nullptr>constexpr inline int popcount(const T x) { return __builtin_popcount(x); }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 32>> = nullptr>constexpr inline int popcount(const T x) { return __builtin_popcount(x); }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 64>> = nullptr>constexpr inline int popcount(const T x) { return __builtin_popcountll(x); }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 16>> = nullptr>constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num<T>; }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 32>> = nullptr>constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num<T>; }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 64>> = nullptr>constexpr inline int count_lz(const T x) { return x ? __builtin_clzll(x) : suisen::bit_num<T>; }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 16>> = nullptr>constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num<T>; }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 32>> = nullptr>constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num<T>; }template <typename T, suisen::constraints_t<suisen::is_nbit<T, 64>> = nullptr>constexpr inline int count_tz(const T x) { return x ? __builtin_ctzll(x) : suisen::bit_num<T>; }template <typename T>constexpr inline int floor_log2(const T x) { return suisen::bit_num<T> - 1 - count_lz(x); }template <typename T>constexpr inline int ceil_log2(const T x) { return floor_log2(x) + ((x & -x) != x); }template <typename T>constexpr inline int kth_bit(const T x, const unsigned int k) { return (x >> k) & 1; }template <typename T>constexpr inline int parity(const T x) { return popcount(x) & 1; }struct all_subset {struct all_subset_iter {const int s; int t;constexpr all_subset_iter(int s) : s(s), t(s + 1) {}constexpr auto operator*() const { return t; }constexpr auto operator++() {}constexpr auto operator!=(std::nullptr_t) { return t ? (--t &= s, true) : false; }};int s;constexpr all_subset(int s) : s(s) {}constexpr auto begin() { return all_subset_iter(s); }constexpr auto end() { return nullptr; }};// ! containertemplate <typename T, typename Comparator, suisen::constraints_t<suisen::is_comparator<Comparator, T>> = nullptr>auto priqueue_comp(const Comparator comparator) {return std::priority_queue<T, std::vector<T>, Comparator>(comparator);}template <typename Iterable>auto isize(const Iterable &iterable) -> decltype(int(iterable.size())) {return iterable.size();}template <typename T, typename Gen, suisen::constraints_t<suisen::is_same_as_invoke_result<T, Gen, int>> = nullptr>auto generate_vector(int n, Gen generator) {std::vector<T> v(n);for (int i = 0; i < n; ++i) v[i] = generator(i);return v;}template <typename T>auto generate_range_vector(T l, T r) {return generate_vector(r - l, [l](int i) { return l + i; });}template <typename T>auto generate_range_vector(T n) {return generate_range_vector(0, n);}template <typename T>void sort_unique_erase(std::vector<T> &a) {std::sort(a.begin(), a.end());a.erase(std::unique(a.begin(), a.end()), a.end());}template <typename InputIterator, typename BiConsumer>auto foreach_adjacent_values(InputIterator first, InputIterator last, BiConsumer f) -> decltype(f(*first++, *last), void()) {if (first != last) for (auto itr = first, itl = itr++; itr != last; itl = itr++) f(*itl, *itr);}template <typename Container, typename BiConsumer>auto foreach_adjacent_values(Container c, BiConsumer f) -> decltype(c.begin(), c.end(), void()){foreach_adjacent_values(c.begin(), c.end(), f);}// ! other utilities// x <- min(x, y). returns true iff `x` has chenged.template <typename T>inline bool chmin(T &x, const T &y) {if (y >= x) return false;x = y;return true;}// x <- max(x, y). returns true iff `x` has chenged.template <typename T>inline bool chmax(T &x, const T &y) {if (y <= x) return false;x = y;return true;}namespace suisen {}using namespace suisen;using namespace std;struct io_setup {io_setup(int precision = 20) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(precision);}} io_setup_{};// ! code from here#include <cassert>#include <numeric>#ifdef _MSC_VER#include <intrin.h>#endif#include <utility>#ifdef _MSC_VER#endifnamespace atcoder {namespace internal {// @param m `1 <= m`// @return x mod mconstexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}// Fast modular multiplication by barrett reduction// Reference: https://en.wikipedia.org/wiki/Barrett_reduction// NOTE: reconsider after Ice Lakestruct barrett {unsigned int _m;unsigned long long im;// @param m `1 <= m < 2^31`explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}// @return munsigned int umod() const { return _m; }// @param a `0 <= a < m`// @param b `0 <= b < m`// @return `a * b % m`unsigned int mul(unsigned int a, unsigned int b) const {// [1] m = 1// a = b = im = 0, so okay// [2] m >= 2// im = ceil(2^64 / m)// -> im * m = 2^64 + r (0 <= r < m)// let z = a*b = c*m + d (0 <= c, d < m)// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2// ((ab * im) >> 64) == c or c + 1unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x =(unsigned long long)(((unsigned __int128)(z)*im) >> 64);#endifunsigned int v = (unsigned int)(z - x * _m);if (_m <= v) v += _m;return v;}};// @param n `0 <= n`// @param m `1 <= m`// @return `(x ** n) % m`constexpr long long pow_mod_constexpr(long long x, long long n, int m) {if (m == 1) return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while (n) {if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}// Reference:// M. Forisek and J. Jancina,// Fast Primality Testing for Integers That Fit into a Machine Word// @param n `0 <= n`constexpr bool is_prime_constexpr(int n) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;long long d = n - 1;while (d % 2 == 0) d /= 2;constexpr long long bases[3] = {2, 7, 61};for (long long a : bases) {long long t = d;long long y = pow_mod_constexpr(a, t, n);while (t != n - 1 && y != 1 && y != n - 1) {y = y * y % n;t <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}template <int n> constexpr bool is_prime = is_prime_constexpr(n);// @param b `1 <= b`// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/gconstexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0) return {b, 0};// Contracts:// [1] s - m0 * a = 0 (mod b)// [2] t - m1 * a = 0 (mod b)// [3] s * |m1| + t * |m0| <= blong long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b// [3]:// (s - t * u) * |m1| + t * |m0 - m1 * u|// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)// = s * |m1| + t * |m0| <= bauto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}// by [3]: |m0| <= b/g// by g != b: |m0| < b/gif (m0 < 0) m0 += b / s;return {s, m0};}// Compile time primitive root// @param m must be prime// @return primitive root (and minimum in now)constexpr int primitive_root_constexpr(int m) {if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long long)(i)*i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) {x /= i;}}}if (x > 1) {divs[cnt++] = x;}for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}template <int m> constexpr int primitive_root = primitive_root_constexpr(m);// @param n `n < 2^32`// @param m `1 <= m < 2^32`// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)unsigned long long floor_sum_unsigned(unsigned long long n,unsigned long long m,unsigned long long a,unsigned long long b) {unsigned long long ans = 0;while (true) {if (a >= m) {ans += n * (n - 1) / 2 * (a / m);a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}unsigned long long y_max = a * n + b;if (y_max < m) break;// y_max < m * (n + 1)// floor(y_max / m) <= nn = (unsigned long long)(y_max / m);b = (unsigned long long)(y_max % m);std::swap(m, a);}return ans;}} // namespace internal} // namespace atcodernamespace atcoder {namespace internal {#ifndef _MSC_VERtemplate <class T>using is_signed_int128 =typename std::conditional<std::is_same<T, __int128_t>::value ||std::is_same<T, __int128>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::value ||std::is_same<T, unsigned __int128>::value,std::true_type,std::false_type>::type;template <class T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value,__uint128_t,unsigned __int128>;template <class T>using is_integral = typename std::conditional<std::is_integral<T>::value ||is_signed_int128<T>::value ||is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_signed_int = typename std::conditional<(is_integral<T>::value &&std::is_signed<T>::value) ||is_signed_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<(is_integral<T>::value &&std::is_unsigned<T>::value) ||is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value,std::make_unsigned<T>,std::common_type<T>>::type>::type;#elsetemplate <class T> using is_integral = typename std::is_integral<T>;template <class T>using is_signed_int =typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<is_integral<T>::value &&std::is_unsigned<T>::value,std::true_type,std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int<T>::value,std::make_unsigned<T>,std::common_type<T>>::type;#endiftemplate <class T>using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;template <class T>using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;template <class T> using to_unsigned_t = typename to_unsigned<T>::type;} // namespace internal} // namespace atcodernamespace atcoder {namespace internal {struct modint_base {};struct static_modint_base : modint_base {};template <class T> using is_modint = std::is_base_of<modint_base, T>;template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;} // namespace internaltemplate <int m, std::enable_if_t<(1 <= m)>* = nullptr>struct static_modint : internal::static_modint_base {using mint = static_modint;public:static constexpr int mod() { return m; }static mint raw(int v) {mint x;x._v = v;return x;}static_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T>* = nullptr>static_modint(T v) {long long x = (long long)(v % (long long)(umod()));if (x < 0) x += umod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T>* = nullptr>static_modint(T v) {_v = (unsigned int)(v % umod());}unsigned int val() const { return _v; }mint& operator++() {_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--() {if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++*this;return result;}mint operator--(int) {mint result = *this;--*this;return result;}mint& operator+=(const mint& rhs) {_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs) {_v -= rhs._v;if (_v >= umod()) _v += umod();return *this;}mint& operator*=(const mint& rhs) {unsigned long long z = _v;z *= rhs._v;_v = (unsigned int)(z % umod());return *this;}mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const {if (prime) {assert(_v);return pow(umod() - 2);} else {auto eg = internal::inv_gcd(_v, m);assert(eg.first == 1);return eg.second;}}friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static constexpr unsigned int umod() { return m; }static constexpr bool prime = internal::is_prime<m>;};template <int id> struct dynamic_modint : internal::modint_base {using mint = dynamic_modint;public:static int mod() { return (int)(bt.umod()); }static void set_mod(int m) {assert(1 <= m);bt = internal::barrett(m);}static mint raw(int v) {mint x;x._v = v;return x;}dynamic_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T>* = nullptr>dynamic_modint(T v) {long long x = (long long)(v % (long long)(mod()));if (x < 0) x += mod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T>* = nullptr>dynamic_modint(T v) {_v = (unsigned int)(v % mod());}unsigned int val() const { return _v; }mint& operator++() {_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--() {if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++*this;return result;}mint operator--(int) {mint result = *this;--*this;return result;}mint& operator+=(const mint& rhs) {_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs) {_v += mod() - rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator*=(const mint& rhs) {_v = bt.mul(_v, rhs._v);return *this;}mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const {auto eg = internal::inv_gcd(_v, mod());assert(eg.first == 1);return eg.second;}friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static internal::barrett bt;static unsigned int umod() { return bt.umod(); }};template <int id> internal::barrett dynamic_modint<id>::bt(998244353);using modint998244353 = static_modint<998244353>;using modint1000000007 = static_modint<1000000007>;using modint = dynamic_modint<-1>;namespace internal {template <class T>using is_static_modint = std::is_base_of<internal::static_modint_base, T>;template <class T>using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;template <class> struct is_dynamic_modint : public std::false_type {};template <int id>struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};template <class T>using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;} // namespace internal} // namespace atcoderusing mint = atcoder::modint1000000007;std::istream& operator>>(std::istream& in, mint& a) {long long e; in >> e; a = e;return in;}std::ostream& operator<<(std::ostream& out, const mint& a) {out << a.val();return out;}#include <algorithm>#include <vector>namespace suisen {struct Permutation : public std::vector<int> {using base_type = std::vector<int>;using base_type::base_type;Permutation() : Permutation(0) {}Permutation(std::size_t n) : Permutation(int(n)) {}Permutation(int n) : base_type(n) {std::iota(begin(), end(), 0);}Permutation(const std::vector<int>& a) : std::vector<int>(a) {}Permutation(std::vector<int>&& a) : std::vector<int>(std::move(a)) {}// returns b s.t. b[i] = a[p[i]]template <typename T>std::vector<T> permute(const std::vector<T>& a) const {const int n = a.size();std::vector<T> res(n);for (int i = 0; i < n; ++i) res[i] = a[(*this)[i]];return res;}// returns b s.t. b[p[i]] = a[i]template <typename T>std::vector<T> inv_permute(const std::vector<T>& a) const {const int n = a.size();std::vector<T> res(n);for (int i = 0; i < n; ++i) res[(*this)[i]] = a[i];return res;}// returns p * q s.t. (p * q)[i] = p[q[i]]friend Permutation operator*(const Permutation& p, const Permutation& q) {return q.permute(p);}Permutation& operator*=(const Permutation& q) {return *this = *this * q;}Permutation inv() const {const int n = size();Permutation res(n);for (int i = 0; i < n; ++i) res[(*this)[i]] = i;return res;}Permutation pow(long long k) const {assert(k >= 0);const int n = size();std::vector<int8_t> seen(n, false);Permutation res(n);for (int s = 0; s < n; ++s) {if (seen[s]) continue;std::vector<int> cycle { s };for (int v = (*this)[s]; v != s; v = (*this)[v]) cycle.push_back(v);const int l = cycle.size();for (int j = 0; j < l; ++j) {int v = cycle[j];seen[v] = true;res[v] = cycle[(j + k) % l];}}return res;}template <typename T, typename Comp = std::less<T>>static Permutation index_sort(const std::vector<T>& a, Comp comp = Comp{}) {Permutation p(a.size());std::sort(p.begin(), p.end(), [&](int i, int j) { return comp(a[i], a[j]); });return p;}};template <typename hash_t>struct PermutationHash {hash_t operator()(const Permutation &p) const {return hash(p);}/*** minimal perfect hash function for permutations.* complexity: O(n) time, O(n) extra space* reference: https://twitter.com/noshi91/status/1452081886025555972?s=20*/static hash_t hash(const Permutation &per) {hash_t h = 0;const int n = per.size();Permutation p = per;Permutation q = per.inv();for (int i = n - 1; i >= 0; --i) {h = h * (i + 1) + p[i];p[q[i]] = p[i];q[p[i]] = q[i];}return h;}static Permutation unhash(int n, hash_t h) {Permutation p = Permutation(n), q = p;for (int i = 0; i < n; ++i) {p[i] = h % (i + 1), q[i] = q[p[i]];q[p[i]] = p[q[i]] = i;h /= i + 1;}return p;}};} // namespace suisennamespace suisen {template <typename T, typename U>std::pair<T, U>& operator+=(std::pair<T, U> &p1, const std::pair<T, U> &p2) {p1.first += p2.first, p1.second += p2.second;return p1;}template <typename T, typename U>std::pair<T, U> operator+(const std::pair<T, U> &p1, const std::pair<T, U> &p2) {return {p1.first + p2.first, p1.second + p2.second};}template <typename T, typename U>std::pair<T, U>& operator-=(std::pair<T, U> &p1, const std::pair<T, U> &p2) {p1.first -= p2.first, p1.second -= p2.second;return p1;}template <typename T, typename U>std::pair<T, U> operator-(const std::pair<T, U> &p1, const std::pair<T, U> &p2) {return {p1.first - p2.first, p1.second - p2.second};}template <typename T, typename U, typename V>std::pair<T, U>& operator*=(std::pair<T, U> &p, const V m) {p.first *= m, p.second *= m;return p;}template <typename T, typename U, typename V>std::pair<T, U> operator*(const std::pair<T, U> &p, const V m) {return {p.first * m, p.second * m};}template <typename T, typename U, typename V>std::pair<T, U> operator*(const V m, const std::pair<T, U> &p) {return {p.first * m, p.second * m};}} // namespace suisennamespace suisen {template <typename T>class CoordinateCompressorBuilder {public:struct Compressor {public:static constexpr int absent = -1;// default constructorCompressor() : _xs(std::vector<T>{}) {}// Construct from strictly sorted vectorCompressor(const std::vector<T> &xs) : _xs(xs) {assert(is_strictly_sorted(xs));}// Return the number of distinct keys.int size() const {return _xs.size();}// Check if the element is registered.bool has_key(const T &e) const {return std::binary_search(_xs.begin(), _xs.end(), e);}// Compress the element. if not registered, returns `default_value`. (default: Compressor::absent)int comp(const T &e, int default_value = absent) const {const int res = min_geq_index(e);return res != size() and _xs[res] == e ? res : default_value;}// Restore the element from the index.T decomp(const int compressed_index) const {return _xs[compressed_index];}// Compress the element. Equivalent to call `comp(e)`int operator[](const T &e) const {return comp(e);}// Return the minimum registered value greater than `e`. if not exists, return `default_value`.T min_gt(const T &e, const T &default_value) const {auto it = std::upper_bound(_xs.begin(), _xs.end(), e);return it == _xs.end() ? default_value : *it;}// Return the minimum registered value greater than or equal to `e`. if not exists, return `default_value`.T min_geq(const T &e, const T &default_value) const {auto it = std::lower_bound(_xs.begin(), _xs.end(), e);return it == _xs.end() ? default_value : *it;}// Return the maximum registered value less than `e`. if not exists, return `default_value`T max_lt(const T &e, const T &default_value) const {auto it = std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());return it == _xs.rend() ? default_value : *it;}// Return the maximum registered value less than or equal to `e`. if not exists, return `default_value`T max_leq(const T &e, const T &default_value) const {auto it = std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());return it == _xs.rend() ? default_value : *it;}// Return the compressed index of the minimum registered value greater than `e`. if not exists, return `compressor.size()`.int min_gt_index(const T &e) const {return std::upper_bound(_xs.begin(), _xs.end(), e) - _xs.begin();}// Return the compressed index of the minimum registered value greater than or equal to `e`. if not exists, return `compressor.size()`.int min_geq_index(const T &e) const {return std::lower_bound(_xs.begin(), _xs.end(), e) - _xs.begin();}// Return the compressed index of the maximum registered value less than `e`. if not exists, return -1.int max_lt_index(const T &e) const {return int(_xs.rend() - std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;}// Return the compressed index of the maximum registered value less than or equal to `e`. if not exists, return -1.int max_leq_index(const T &e) const {return int(_xs.rend() - std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;}private:std::vector<T> _xs;static bool is_strictly_sorted(const std::vector<T> &v) {return std::adjacent_find(v.begin(), v.end(), std::greater_equal<T>()) == v.end();}};CoordinateCompressorBuilder() : _xs(std::vector<T>{}) {}explicit CoordinateCompressorBuilder(const std::vector<T> &xs) : _xs(xs) {}explicit CoordinateCompressorBuilder(std::vector<T> &&xs) : _xs(std::move(xs)) {}template <typename Gen, constraints_t<is_same_as_invoke_result<T, Gen, int>> = nullptr>CoordinateCompressorBuilder(const int n, Gen generator) {reserve(n);for (int i = 0; i < n; ++i) push(generator(i));}// Attempt to preallocate enough memory for specified number of elements.void reserve(int n) {_xs.reserve(n);}// Add data.void push(const T &first) {_xs.push_back(first);}// Add data.void push(T &&first) {_xs.push_back(std::move(first));}// Add data in the range of [first, last).template <typename Iterator>auto push(const Iterator &first, const Iterator &last) -> decltype(std::vector<T>{}.push_back(*first), void()) {for (auto it = first; it != last; ++it) _xs.push_back(*it);}// Add all data in the container. Equivalent to `push(iterable.begin(), iterable.end())`.template <typename Iterable>auto push(const Iterable &iterable) -> decltype(std::vector<T>{}.push_back(*iterable.begin()), void()) {push(iterable.begin(), iterable.end());}// Add data.template <typename ...Args>void emplace(Args &&...args) {_xs.emplace_back(std::forward<Args>(args)...);}// Build compressor.auto build() {std::sort(_xs.begin(), _xs.end()), _xs.erase(std::unique(_xs.begin(), _xs.end()), _xs.end());return Compressor {_xs};}// Build compressor from vector.static auto build(const std::vector<T> &xs) {return CoordinateCompressorBuilder(xs).build();}// Build compressor from vector.static auto build(std::vector<T> &&xs) {return CoordinateCompressorBuilder(std::move(xs)).build();}// Build compressor from generator.template <typename Gen, constraints_t<is_same_as_invoke_result<T, Gen, int>> = nullptr>static auto build(const int n, Gen generator) {return CoordinateCompressorBuilder<T>(n, generator).build();}private:std::vector<T> _xs;};} // namespace suisen// Reference: https://en.wikipedia.org/wiki/Fenwick_treetemplate <class T> struct fenwick_tree {public:fenwick_tree() : _n(0) {}explicit fenwick_tree(int n) : _n(n), data(n) {}void add(int p, T x) {assert(0 <= p && p < _n);p++;while (p <= _n) {data[p - 1] += T(x);p += p & -p;}}T sum(int l, int r) {assert(0 <= l && l <= r && r <= _n);return sum(r) - sum(l);}private:int _n;std::vector<T> data;T sum(int r) {T s{};while (r > 0) {s += data[r - 1];r -= r & -r;}return s;}};using S = pair<int, mint>;int main() {input(int, n);vector<int> x(n), y(n);read(x, y);vector<mint> answers;loop(2) {vector<int> u(n), v(n);rep(i, n) {u[i] = x[i] - y[i];v[i] = x[i] + y[i];}auto p = Permutation::index_sort(u);x = p.permute(x);y = p.permute(y);u = p.permute(u);v = p.permute(v);assert(is_sorted(all(u)));auto cmp = CoordinateCompressorBuilder<int>::build(v);fenwick_tree<S> ft(n);mint& ans = answers.emplace_back();int pu = 0;vector<pair<int, int>> buf;rep(i, n) {const int r = cmp[v[i]];if (u[i] != pu) {for (auto [pos, val] : buf) ft.add(pos, { 1, val });buf.clear();}auto [num, sum] = ft.sum(0, r);ans += mint(num) * x[i] - sum;buf.emplace_back(r, x[i]);pu = u[i];}ans *= 2;x.swap(y);}print(answers);return 0;}