以下的 Barrett 只能拿 30 分。换成 operator% 之后就过了。

using OY::getline;
template <typename _ModType>
struct __integral_in_64 : public std::integral_constant<bool, std::is_integral<_ModType>::value && std::is_unsigned<_ModType>::value> {};
template <>
struct __integral_in_64<__int128> : public std::false_type {};
template <>
struct __integral_in_64<unsigned __int128> : public std::false_type {};
template <typename _ModType>
class barrett {
    _ModType _M_mod;
    int _M_l;
    __uint128_t _M_inv;
    static constexpr auto _Nd = std::numeric_limits<_ModType>::digits;
    static constexpr auto _Nd_ull = std::numeric_limits<unsigned long long>::digits;
    static_assert(__integral_in_64<_ModType>::value, "_ModType must be an unsigned integral type");
public:
    constexpr barrett() = default;
    constexpr barrett(const _ModType& mod)
        : _M_mod(mod),
          _M_l(_Nd_ull + std::__lg(mod)),
          _M_inv(((unsigned __int128)1 << _M_l) / mod + ((mod & (mod - 1)) != 0)) {}
    constexpr void set_mod(const _ModType& mod) {
        _M_mod = mod;
          _M_l = _Nd_ull + _Nd - __builtin_clzll((unsigned long long)mod) - ((mod & (mod - 1)) != 0);
          _M_inv = ((unsigned __int128)1 << _M_l) / mod + ((mod & (mod - 1)) != 0);
    }
    constexpr _ModType mod() const { return _M_mod; }
    constexpr _ModType mod(__uint128_t x) const {
        __uint128_t tmp_h = _M_inv * (x >> 64), tmp_l = _M_inv * __uint128_t(x & ~0ull);
        _ModType ret = x - ((tmp_h >> (_M_l - 64)) + (tmp_l >> _M_l)) * _M_mod;
        while (ret >= _M_mod) ret -= _M_mod;
        return ret;
    }
};