kyopro library
This documentation is automatically generated by online-judge-tools/verification-helper
kpr/template/alias.hpp
- View this file on GitHub
- Last update: 2023-06-25 00:32:47+09:00
- Include:
#include "kpr/template/alias.hpp"
Depends on
kpr/algorithm/Hash.hpp
- kpr/algorithm/bit.hpp
- kpr/function/compare.hpp
- kpr/function/monoid.hpp
- kpr/io/in.hpp
- kpr/io/io_option.hpp
- kpr/io/out.hpp
- kpr/math/DynamicModInt.hpp
- kpr/math/ModInt.hpp
- kpr/math/Montgomery.hpp
- kpr/math/mod.hpp
- kpr/math/power.hpp
- kpr/meta/constant.hpp
- kpr/meta/setting.hpp
- kpr/meta/trait.hpp
- kpr/meta/tuple_like.hpp
Required by
Code
#pragma once
#include <cstdint>
#include <forward_list>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include "../algorithm/Hash.hpp"
#include "../function/compare.hpp"
#include "../math/DynamicModInt.hpp"
#include "../math/ModInt.hpp"
#include "../meta/setting.hpp"
namespace kpr {
using ushort = unsigned short;
using ll = KYOPRO_LL;
using ull = unsigned long long;
using lf = KYOPRO_LF;
using llf = long double;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
#ifdef __SIZEOF_FLOAT128__
using f128 = __float128;
#endif
using mint = KYOPRO_MINT;
using dmint = DynamicModInt<KYOPRO_BASE_UINT>;
using str = std::string;
template<class T, std::size_t idx, class... Args>
struct agg_type {
using type = typename agg_type<T, idx - 1, T, Args...>::type;
};
template<class T, class... Args>
struct agg_type<T, 0, Args...> {
using type = std::tuple<Args...>;
};
template<class T>
struct agg_type<T, 0, T, T> {
using type = std::pair<T, T>;
};
template<class T, std::size_t idx>
using agg = typename agg_type<T, idx>::type;
using ll2 = agg<ll, 2>;
using ll3 = agg<ll, 3>;
using ll4 = agg<ll, 4>;
using ll5 = agg<ll, 5>;
#define DEFINE_TEMPLATE_ALIAS(short_name, type, ...) \
template<__VA_ARGS__> \
using short_name = type; \
template<__VA_ARGS__> \
using V ## short_name = Vec<type>; \
template<__VA_ARGS__> \
using VV ## short_name = VVec<type>;
#define DEFINE_ALIAS(short_name, name, short_value_type, value_type) \
using short_name ## short_value_type = name<value_type>; \
using V ## short_name ## short_value_type = V ## name<value_type>; \
using VV ## short_name ## short_value_type = VV ## name<value_type>; \
using short_name ## V ## short_value_type = name<Vec<value_type>>; \
using V ## short_name ## V ## short_value_type = V ## name<Vec<value_type>>;
#define DEFINE_ALIAS_FOR_VEC(short_name, name, short_value_type, value_type) \
using V ## short_value_type = Vec<value_type>; \
using VV ## short_value_type = VVec<value_type>; \
using VVV ## short_value_type = VVVec<value_type>; \
using VVVV ## short_value_type = VVVVec<value_type>; \
using VVVVV ## short_value_type = VVVVVec<value_type>;
#define DEFINE_MAP_ALIAS_IMPL(short_name, name, short_value_type1, value_type1, short_value_type2, value_type2) \
using short_name ## short_value_type1 ## short_value_type2 = name<value_type1, value_type2>; \
using V ## short_name ## short_value_type1 ## short_value_type2 = V ## name<value_type1, value_type2>; \
using VV ## short_name ## short_value_type1 ## short_value_type2 = VV ## name<value_type1, value_type2>; \
using short_name ## V ## short_value_type1 ## short_value_type2 = name<Vec<value_type1>, value_type2>; \
using short_name ## short_value_type1 ## V ## short_value_type2 = name<value_type1, Vec<value_type2>>; \
using short_name ## V ## short_value_type1 ## V ## short_value_type2 = name<Vec<value_type1>, Vec<value_type2>>; \
using V ## short_name ## V ## short_value_type1 ## short_value_type2 = V ## name<Vec<value_type1>, value_type2>; \
using V ## short_name ## short_value_type1 ## V ## short_value_type2 = V ## name<value_type1, Vec<value_type2>>; \
using V ## short_name ## V ## short_value_type1 ## V ## short_value_type2 = V ## name<Vec<value_type1>, Vec<value_type2>>;
#define DEFINE_MAP_ALIAS(...) \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, b, bool); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, i, int); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, l, ll); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, f, float); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, lf, lf); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, llf, llf); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, m, mint); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, dm, dmint); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, c, char); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, s, str); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll2, ll2); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll3, ll3); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll4, ll4); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll5, ll5);
#define DEFINE_CONTAINER_ALIAS(define_alias, short_name, name) \
define_alias(short_name, name, b, bool); \
define_alias(short_name, name, i, int); \
define_alias(short_name, name, l, ll); \
define_alias(short_name, name, f, float); \
define_alias(short_name, name, lf, lf); \
define_alias(short_name, name, llf, llf); \
define_alias(short_name, name, m, mint); \
define_alias(short_name, name, dm, dmint); \
define_alias(short_name, name, c, char); \
define_alias(short_name, name, s, str); \
define_alias(short_name, name, ll2, ll2); \
define_alias(short_name, name, ll3, ll3); \
define_alias(short_name, name, ll4, ll4); \
define_alias(short_name, name, ll5, ll5);
template<class T>
using Vec = std::vector<T>;
template<class T>
using VVec = Vec<Vec<T>>;
template<class T>
using VVVec = Vec<VVec<T>>;
template<class T>
using VVVVec = Vec<VVVec<T>>;
template<class T>
using VVVVVec = Vec<VVVVec<T>>;
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS_FOR_VEC, V, Vec)
DEFINE_TEMPLATE_ALIAS(Deque, std::deque<T>, class T)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, DQ, Deque)
DEFINE_TEMPLATE_ALIAS(List, std::list<T>, class T)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, L, List)
DEFINE_TEMPLATE_ALIAS(ForwardList, std::forward_list<T>, class T)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, FL, ForwardList)
DEFINE_TEMPLATE_ALIAS(Set, std::decay_t<decltype(std::declval<std::set<Key, Compare>>())>, class Key, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, S, Set)
DEFINE_TEMPLATE_ALIAS(Map, std::decay_t<decltype(std::declval<std::map<Key, T, Compare>>())>, class Key, class T, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, M, Map)
DEFINE_TEMPLATE_ALIAS(HashSet, std::decay_t<decltype(std::declval<std::unordered_set<Key, H>>())>, class Key, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, HS, HashSet)
DEFINE_TEMPLATE_ALIAS(HashMap, std::decay_t<decltype(std::declval<std::unordered_map<Key, T, H>>())>, class Key, class T, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, HM, HashMap)
DEFINE_TEMPLATE_ALIAS(MultiSet, std::decay_t<decltype(std::declval<std::multiset<Key, Compare>>())>, class Key, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, MS, MultiSet)
DEFINE_TEMPLATE_ALIAS(MultiMap, std::decay_t<decltype(std::declval<std::multimap<Key, T, Compare>>())>, class Key, class T, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, MM, MultiMap)
DEFINE_TEMPLATE_ALIAS(HashMultiSet, std::decay_t<decltype(std::declval<std::unordered_multiset<Key, H>>())>, class Key, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, HMS, HashMultiSet)
DEFINE_TEMPLATE_ALIAS(HashMultiMap, std::decay_t<decltype(std::declval<std::unordered_multimap<Key, T, H>>())>, class Key, class T, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, HMM, HashMultiMap)
DEFINE_TEMPLATE_ALIAS(Queue, std::decay_t<decltype(std::declval<std::queue<T, Container>>())>, class T, class Container = std::deque<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, Que, Queue)
DEFINE_TEMPLATE_ALIAS(Stack, std::decay_t<decltype(std::declval<std::stack<T, Container>>())>, class T, class Container = std::deque<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, Stk, Stack)
DEFINE_TEMPLATE_ALIAS(PriQ, std::decay_t<decltype(std::declval<std::priority_queue<T, Container, Compare>>())>, class T, class Compare = Less, class Container = Vec<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, PQ, PriQ)
DEFINE_TEMPLATE_ALIAS(HeapQ, std::decay_t<decltype(std::declval<std::priority_queue<T, Container, Compare>>())>, class T, class Compare = Greater, class Container = Vec<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, HQ, HeapQ)
DEFINE_TEMPLATE_ALIAS(BitSet, std::bitset<size>, std::size_t size)
#undef DEFINE_TEMPLATE_ALIAS
#undef DEFINE_ALIAS
#undef DEFINE_ALIAS_FOR_VEC
#undef DEFINE_MAP_ALIAS_IMPL
#undef DEFINE_MAP_ALIAS
#undef DEFINE_CONTAINER_ALIAS
} // namespace kpr
using namespace std;
using namespace kpr;#line 2 "kpr/template/alias.hpp"
#include <cstdint>
#include <forward_list>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#line 2 "kpr/algorithm/Hash.hpp"
#include <cstddef>
#line 4 "kpr/algorithm/Hash.hpp"
#include <iterator>
#include <type_traits>
#line 6 "kpr/meta/tuple_like.hpp"
namespace kpr {
namespace helper {
struct CastableToAny {
template<class T>
operator T() const noexcept;
};
template<class T, std::size_t... idx, std::void_t<decltype(T{((void)idx, CastableToAny{})...})>* = nullptr>
constexpr bool is_constructible_with(std::index_sequence<idx...>, bool) noexcept {
return true;
}
template<class T, std::size_t... idx>
constexpr bool is_constructible_with(std::index_sequence<idx...>, char) noexcept {
return false;
}
template<class T, std::size_t n = sizeof(T) * 8, class = void>
struct constructible_size {
static_assert(n != 0, "T is not constructible");
static constexpr std::size_t value = constructible_size<T, n - 1>::value;
};
template<class T, std::size_t n>
struct constructible_size<T, n, std::enable_if_t<is_constructible_with<T>(std::make_index_sequence<n>(), false)>> {
static constexpr std::size_t value = n;
};
} // namespace helper
// tuple_likeな型Tの大きさを調べる
template<class T, class = void>
struct tuple_like_size {
static constexpr std::size_t value = helper::constructible_size<T>::value;
};
template<class T>
struct tuple_like_size<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
static constexpr std::size_t value = std::tuple_size_v<T>;
};
// tuple_likeな型Tの大きさを調べる
template<class T>
inline constexpr std::size_t tuple_like_size_v = tuple_like_size<T>::value;
// tuple_likeなオブジェクトのidx(0 <= idx < 8)番目を求める関数クラス
template<class T, class = void>
struct GetFunction {
#define GET(...) \
{ \
auto&& [__VA_ARGS__] = std::forward<U>(tuple_like); \
return std::get<idx> (std::forward_as_tuple(__VA_ARGS__)); \
}
template<std::size_t idx, class U>
static constexpr decltype(auto) get(U&& tuple_like) noexcept {
constexpr std::size_t size = tuple_like_size_v<T>;
static_assert(size != 0, "The size must not be 0");
static_assert(size < 9, "The size of tuple_like must be less than 9");
if constexpr (size == 1) GET(a)
else if constexpr (size == 2) GET(a, b)
else if constexpr (size == 3) GET(a, b, c)
else if constexpr (size == 4) GET(a, b, c, d)
else if constexpr (size == 5) GET(a, b, c, d, e)
else if constexpr (size == 6) GET(a, b, c, d, e, f)
else if constexpr (size == 7) GET(a, b, c, d, e, f, g)
else GET(a, b, c, d, e, f, g, h)
}
#undef GET
};
template<class T>
struct GetFunction<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
template<std::size_t idx, class U>
static constexpr decltype(auto) get(U&& tuple_like) noexcept {
return std::get<idx>(std::forward<U>(tuple_like));
}
};
namespace helper {
template<std::size_t idx>
struct GetHelper {
template<class T>
constexpr decltype(auto) operator ()(T&& tuple_like) const noexcept {
return GetFunction<std::decay_t<T>>::template get<idx>(std::forward<T>(tuple_like));
}
};
}
// tuple-likeなオブジェクトのidx(0 <= idx < 8)番目を求める
template<std::size_t idx>
inline constexpr helper::GetHelper<idx> get;
// tuple-likeな型Tのidx(0 <= idx < 8)番目の要素の型を調べる
template<std::size_t idx, class T>
struct tuple_like_element {
using type = std::decay_t<decltype(get<idx>(std::declval<T>()))>;
};
// tuple-likeな型Tのidx(0 <= idx < 8)番目の要素の型を調べる
template<std::size_t idx, class T>
using tuple_like_element_t = typename tuple_like_element<idx, T>::type;
// 型Tがtuple_likeか調べる
template<class T, class = void>
struct is_tuple_like {
static constexpr bool value = std::is_aggregate_v<T>;
};
template<class T>
struct is_tuple_like<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
static constexpr bool value = true;
};
// 型Tがtuple_likeか調べる
template<class T>
inline constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
} // namespace kpr
#line 7 "kpr/meta/trait.hpp"
namespace kpr {
namespace helper {
template<class T>
struct is_integer_helper {
static constexpr bool value = std::is_integral_v<T>;
};
#ifdef __SIZEOF_INT128__
template<>
struct is_integer_helper<__int128_t> {
static constexpr bool value = true;
};
template<>
struct is_integer_helper<__uint128_t> {
static constexpr bool value = true;
};
#endif
} // namespace helper
// 型Tが整数か調べる
template<class T>
struct is_integer {
static constexpr bool value = helper::is_integer_helper<std::remove_cv_t<T>>::value;
};
// 型Tが整数か調べる
template<class T>
inline constexpr bool is_integer_v = is_integer<T>::value;
// 型Tが符号付き整数か調べる
template<class T>
struct is_signed_integer {
static constexpr bool value = is_integer_v<T> && std::is_signed_v<T>;
};
// 型Tが符号付き整数か調べる
template<class T>
inline constexpr bool is_signed_integer_v = is_signed_integer<T>::value;
// 型Tが符号無し整数か調べる
template<class T>
struct is_unsigned_integer {
static constexpr bool value = is_integer_v<T> && !std::is_signed_v<T>;
};
// 型Tが符号無し整数か調べる
template<class T>
inline constexpr bool is_unsigned_integer_v = is_unsigned_integer<T>::value;
namespace helper {
template<class T>
struct is_floating_point_helper {
static constexpr bool value = std::is_floating_point_v<T>;
};
#ifdef __SIZEOF_FLOAT128__
template<>
struct is_floating_point_helper<__float128> {
static constexpr bool value = true;
};
#endif
} // namespace helper
// 型Tが浮動小数点数か調べる
template<class T>
struct is_floating_point {
static constexpr bool value = helper::is_floating_point_helper<std::remove_cv_t<T>>::value;
};
// 型Tが浮動小数点数か調べる
template<class T>
inline constexpr bool is_floating_point_v = is_floating_point<T>::value;
// 型Tが算術型か調べる
template<class T>
struct is_arithmetic {
static constexpr bool value = is_integer_v<T> || is_floating_point_v<T>;
};
// 型Tが算術型か調べる
template<class T>
inline constexpr bool is_arithmetic_v = is_arithmetic<T>::value;
// 型Tがスカラーか調べる
template<class T>
struct is_scalar {
static constexpr bool value = is_arithmetic_v<T> || std::is_enum_v<T> || std::is_pointer_v<T> || std::is_member_pointer_v<T> || std::is_null_pointer_v<T>;
};
// 型Tがスカラーか調べる
template<class T>
inline constexpr bool is_scalar_v = is_scalar<T>::value;
// size以上の大きさを持つ最小の符号付き整数を調べる
template<std::size_t size>
struct int_least {
private:
static constexpr auto get_type() noexcept {
static_assert(size <= 128, "The given integer type is too large");
if constexpr (size <= 8) return std::int_least8_t{};
else if constexpr (size <= 16) return std::int_least16_t{};
else if constexpr (size <= 32) return std::int_least32_t{};
else if constexpr (size <= 64) return std::int_least64_t{};
else return __int128_t{};
}
public:
using type = decltype(get_type());
};
// size以上の大きさを持つ最小の符号付き整数を調べる
template<std::size_t size>
using int_least_t = typename int_least<size>::type;
// size以上の大きさを持つ最小の符号無し整数を調べる
template<std::size_t size>
struct uint_least {
private:
static constexpr auto get_type() noexcept {
static_assert(size <= 128, "The give integer type is too large");
if constexpr (size <= 8) return std::uint_least8_t{};
else if constexpr (size <= 16) return std::uint_least16_t{};
else if constexpr (size <= 32) return std::uint_least32_t{};
else if constexpr (size <= 64) return std::uint_least64_t{};
else return __uint128_t{};
}
public:
using type = decltype(get_type());
};
// size以上の大きさを持つ最小の符号無し整数を調べる
template<std::size_t size>
using uint_least_t = typename uint_least<size>::type;
// Tの次に大きい整数型を調べる
template<class T>
struct next_integer {
static_assert(is_integer_v<T>, "The given type must be an integer type");
static_assert(sizeof(T) <= 8, "The given integer type is too large");
using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 16>, uint_least_t<sizeof(T) * 16>>;
};
// Tの次に大きい整数型を調べる
template<class T>
using next_integer_t = typename next_integer<T>::type;
// Tの次に小さい整数型を調べる
template<class T>
struct prev_integer {
static_assert(is_integer_v<T>, "The given type must be an integer type");
static_assert(sizeof(T) >= 2, "The given integer type is too large");
using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 4>, uint_least_t<sizeof(T) * 4>>;
};
// Tの次に小さい整数型を調べる
template<class T>
using prev_integer_t = typename prev_integer<T>::type;
// 型Tがイテレータか調べる
template<class T, class = void>
struct is_iterator {
static constexpr bool value = false;
};
template<class T>
struct is_iterator<T, std::void_t<typename std::iterator_traits<T>::iterator_category>> {
static constexpr bool value = true;
};
// 型Tがイテレータか調べる
template<class T>
inline constexpr bool is_iterator_v = is_iterator<T>::value;
// 型TがRangeか調べる
template<class T, class = void>
struct is_range {
static constexpr bool value = false;
};
template<class T>
struct is_range<T, std::void_t<decltype(std::begin(std::declval<std::add_lvalue_reference_t<T>>()), std::end(std::declval<std::add_lvalue_reference_t<T>>()))>> {
static constexpr bool value = true;
};
// 型TがRangeか調べる
template<class T>
inline constexpr bool is_range_v = is_range<T>::value;
// Range型Tからイテレータの型を調べる
template<class T>
struct range_iterator {
using type = std::decay_t<decltype(std::begin(std::declval<T>()))>;
};
// Range型Tからイテレータの型を調べる
template<class T>
using range_iterator_t = typename range_iterator<T>::type;
// Range型Tから読み取り専用イテレータの型を調べる
template<class T>
struct range_const_iterator {
using type = std::decay_t<decltype(std::cbegin(std::declval<T>()))>;
};
// Range型Tから読み取り専用イテレータの型を調べる
template<class T>
using range_const_iterator_t = typename range_iterator<T>::type;
// Range型Tから要素の型を調べる
template<class T>
struct range_value {
using type = std::decay_t<decltype(*std::begin(std::declval<T>()))>;
};
// Range型Tから要素の型を調べる
template<class T>
using range_value_t = typename range_value<T>::type;
} // namespace kpr
#line 9 "kpr/algorithm/Hash.hpp"
namespace kpr {
// ハッシュ(tuple_like, range対応)
template<class, class = void>
struct Hash;
template<class T>
struct Hash<T, std::enable_if_t<std::is_scalar_v<T>>> {
using value_type = T;
constexpr std::size_t operator ()(T a) const noexcept {
return std::hash<T>{}(a);
}
};
template<class T>
struct Hash<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
using value_type = T;
template<std::size_t i = 0>
constexpr std::size_t operator ()(const T& a) const noexcept {
if constexpr (i == tuple_like_size_v<T>) return tuple_like_size_v<T>;
else {
std::size_t seed = operator()<i + 1>(a);
return seed ^ (Hash<tuple_like_element_t<i, T>>{}(get<i>(a)) + 0x9e3779b97f4a7c15LU + (seed << 12) + (seed >> 4));
}
}
};
template<class T>
struct Hash<T, std::enable_if_t<is_range_v<T>>>: Hash<range_value_t<T>> {
using value_type = T;
constexpr std::size_t operator ()(const T& a) const {
std::size_t seed = std::size(a);
for (auto&& i: a) seed ^= Hash<range_value_t<T>>{}(i) + 0x9e3779b97f4a7c15LU + (seed << 12) + (seed >> 4);
return seed;
}
};
} // namespace kpr
#line 2 "kpr/function/compare.hpp"
namespace kpr {
// operator =で比較
struct Equal {
template<class T>
constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x == y)) {
return x == y;
}
};
// operator !=で比較
struct NotEqual {
template<class T>
constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x != y)) {
return x != y;
}
};
// operator <の関数クラス
struct Less {
template<class T>
constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x < y)) {
return x < y;
}
};
// operator <=の関数クラス
struct LessEqual {
template<class T>
constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x <= y)) {
return x <= y;
}
};
// operator >の関数クラス
struct Greater {
template<class T>
constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x > y)) {
return x > y;
}
};
// operator >=の関数クラス
struct GreaterEqual {
template<class T>
constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x >= y)) {
return x >= y;
}
};
} // namespace kpr
#line 3 "kpr/meta/setting.hpp"
#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型
#define KYOPRO_BASE_INT std::int64_t
#endif
#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型
#define KYOPRO_BASE_UINT std::uint64_t
#endif
#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型
#define KYOPRO_BASE_FLOAT double
#endif
#ifndef KYOPRO_LL
// ll
#define KYOPRO_LL long long
#endif
#ifndef KYOPRO_LF
// lf
#define KYOPRO_LF double
#endif
#ifndef KYOPRO_MINT
// mint
#define KYOPRO_MINT kpr::ModInt<mod>
#endif
#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod
#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif
#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)
#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif
#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す
#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif
#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ
#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif
#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限
#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 6 "kpr/function/monoid.hpp"
namespace kpr {
// 足し算のmonoid
template<class T>
struct Add {
using value_type = T;
static constexpr T id() noexcept {
return T{};
}
constexpr T operator ()(const T& a, const T& b) const noexcept {
return a + b;
}
static constexpr T inv(const T& a) noexcept {
return -a;
}
};
// 掛け算のmonoid
template<class T>
struct Mul {
using value_type = T;
static constexpr T id() noexcept {
return 1;
}
constexpr T operator ()(const T& a, const T& b) const noexcept {
return a * b;
}
static constexpr T inv(const T& a) noexcept {
return 1 / a;
}
};
// minのmonoid
template<class T>
struct Min {
using value_type = T;
static constexpr T id() noexcept {
if constexpr (std::numeric_limits<T>::has_infinity) return std::numeric_limits<T>::infinity();
return std::numeric_limits<T>::max() / KYOPRO_INF_DIV;
}
constexpr T operator ()(const T& a, const T& b) const noexcept {
return a < b ? a : b;
}
};
// maxのmonoid
template<class T>
struct Max {
using value_type = T;
static constexpr T id() noexcept {
if constexpr (std::numeric_limits<T>::has_infinity) return -std::numeric_limits<T>::infinity();
if constexpr (std::is_signed_v<T>) return -(std::numeric_limits<T>::max() / KYOPRO_INF_DIV);
return 0;
}
constexpr T operator ()(const T& a, const T& b) const noexcept {
return a > b ? a : b;
}
};
// invを持つか調べる
template<class, class = void>
struct has_inv {
static constexpr bool value = false;
};
template<class T>
struct has_inv<T, std::void_t<decltype(&T::inv)>> {
static constexpr bool value = true;
};
// invを持つか調べる
template<class T>
inline constexpr bool has_inv_v = has_inv<T>::value;
} // namespace kpr
#line 5 "kpr/math/power.hpp"
namespace kpr {
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr T operator ()(T a, KYOPRO_BASE_UINT n, T init = Mul<T>::id()) const noexcept {
while (n > 0) {
if (n & 1) init *= a;
a *= a;
n >>= 1;
}
return init;
}
} power;
} // namespace kpr
#line 5 "kpr/meta/constant.hpp"
namespace kpr {
// 問題で設定されたmod
template<class T>
inline constexpr T MOD = KYOPRO_DEFAULT_MOD;
// 問題で設定されたmod
inline constexpr KYOPRO_BASE_INT mod = MOD<KYOPRO_BASE_INT>;
// 無限大を表す整数
template<class T>
inline constexpr T INF = std::numeric_limits<T>::max() / KYOPRO_INF_DIV;
// 無限大を表す整数
inline constexpr KYOPRO_BASE_INT inf = INF<KYOPRO_BASE_INT>;
// 許容される小数誤差
template<class T, KYOPRO_BASE_UINT decimal_precision = KYOPRO_DECIMAL_PRECISION>
inline constexpr KYOPRO_BASE_FLOAT EPS = static_cast<T>(1) / power(10ULL, decimal_precision);
// 許容される小数誤差
inline constexpr KYOPRO_BASE_FLOAT eps = EPS<KYOPRO_BASE_FLOAT>;
// 円周率
template<class T>
inline constexpr T PI = 3.14159265358979323846;
// 円周率
inline constexpr KYOPRO_BASE_FLOAT pi = PI<KYOPRO_BASE_FLOAT>;
} // namespace kpr
#line 2 "kpr/io/in.hpp"
#include <unistd.h>
#include <array>
#include <bitset>
#line 7 "kpr/io/in.hpp"
#include <cstdio>
#line 5 "kpr/io/io_option.hpp"
namespace kpr {
template<class Tuple, std::size_t idx>
struct Indexed {
Tuple args_tuple;
template<class... Args>
constexpr Indexed(Args&&... args) noexcept: args_tuple{std::forward<Args>(args)...} {}
};
template<std::size_t i, class... Args>
constexpr auto indexed(Args&&... args) noexcept {
return Indexed<std::tuple<Args...>, i>{std::forward<Args>(args)...};
}
template<class... Args>
constexpr auto idx1(Args&&... args) noexcept {
return indexed<1>(std::forward<Args>(args)...);
}
template<class Tuple, bool... seps>
struct SepWith {
Tuple args_tuple;
template<class... Args>
constexpr SepWith(Args&&... args) noexcept: args_tuple{std::forward<Args>(args)...} {}
};
template<bool... seps, class... Args>
constexpr auto sep_with(Args&&... args) noexcept {
return SepWith<std::tuple<Args...>, seps...>{std::forward<Args>(args)...};
}
} // namespace kpr
#line 16 "kpr/io/in.hpp"
namespace kpr {
// バッファを用いてファイルを読み込むクラス
template<std::size_t buf_size = KYOPRO_BUFFER_SIZE>
struct Reader {
private:
int fd, idx;
std::array<char, buf_size> buffer;
public:
// バッファサイズを取得
static constexpr KYOPRO_BASE_INT get_buf_size() noexcept {
return buf_size;
}
Reader() {
[[maybe_unused]] ssize_t res = read(fd, buffer.begin(), buf_size);
}
Reader(int fd): fd(fd), idx(0), buffer() {
[[maybe_unused]] ssize_t res = read(fd, buffer.begin(), buf_size);
}
Reader(FILE* fp): fd(fileno(fp)), idx(0), buffer() {
[[maybe_unused]] ssize_t res = read(fd, buffer.begin(), buf_size);
}
// 入力イテレータ
struct iterator {
private:
Reader& reader;
public:
using difference_type = void;
using value_type = void;
using pointer = void;
using reference = void;
using iterator_category = std::input_iterator_tag;
iterator() noexcept = default;
iterator(Reader& reader) noexcept: reader(reader) {}
iterator& operator ++() {
++reader.idx;
if (reader.idx == buf_size) {
[[maybe_unused]] ssize_t res = read(reader.fd, reader.buffer.begin(), buf_size);
reader.idx = 0;
}
return *this;
}
iterator operator ++(int) {
iterator before = *this;
operator ++();
return before;
}
char& operator *() const {
return reader.buffer[reader.idx];
}
};
// ファイルの最初を示すイテレータを取得
iterator begin() noexcept {
return iterator(*this);
}
};
// 標準入力
Reader input{0};
// 値の入力の関数クラス
template<class, class = void>
struct ScanFunction;
// 入力イテレータを用いて値を入力するクラス
template<class Iterator, std::size_t decimal_precision = KYOPRO_DECIMAL_PRECISION>
struct Scanner {
using iterator_type = Iterator;
// 入力イテレータ
Iterator itr;
// 指定された小数誤差を取得
static constexpr KYOPRO_BASE_INT get_decimal_precision() noexcept {
return decimal_precision;
}
Scanner() noexcept = default;
Scanner(Iterator itr) noexcept: itr(itr) {}
// 次の文字までの空白を無視する
void discard_space() {
while (('\t' <= *itr && *itr <= '\r') || *itr == ' ') ++itr;
}
// 整数、小数を入力
template<class T>
void scan_arithmetic(T& a) {
discard_space();
bool sgn = false;
if constexpr (!std::is_unsigned_v<T>) if (*itr == '-') {
sgn = true;
++itr;
}
a = 0;
for (; '0' <= *itr && *itr <= '9'; ++itr) a = a * 10 + *itr - '0';
if (*itr == '.') {
++itr;
if constexpr (is_floating_point_v<T>) {
constexpr std::uint_fast64_t power_decimal_precision = power(10ULL, decimal_precision);
T d = 0;
std::uint_fast64_t i = 1;
for (; '0' <= *itr && *itr <= '9' && i < power_decimal_precision; i *= 10) {
d = d * 10 + *itr - '0';
++itr;
}
a += d / i;
}
while ('0' <= *itr && *itr <= '9') ++itr;
}
if constexpr (!std::is_unsigned_v<T>) if (sgn) a = -a;
}
// 複数の値を入力
void operator ()() {}
template<class Head, class... Args>
void operator ()(Head&& head, Args&&... args) {
ScanFunction<std::decay_t<Head>>::scan(*this, std::forward<Head>(head));
operator ()(std::forward<Args>(args)...);
}
};
template<>
struct ScanFunction<char> {
template<class Scanner>
static void scan(Scanner& scanner, char& a) {
scanner.discard_space();
a = *scanner.itr;
++scanner.itr;
}
};
template<>
struct ScanFunction<bool> {
template<class Scanner>
static void scan(Scanner& scanner, bool& a) {
scanner.discard_space();
a = *scanner.itr != '0';
}
};
template<>
struct ScanFunction<std::string> {
template<class Scanner>
static void scan(Scanner& scanner, std::string& a) {
scanner.discard_space();
a.clear();
while ((*scanner.itr < '\t' || '\r' < *scanner.itr) && *scanner.itr != ' ') {
a += *scanner.itr;
++scanner.itr;
}
}
};
template<std::size_t len>
struct ScanFunction<std::bitset<len>> {
template<class Scanner>
static void scan(Scanner& scanner, std::bitset<len>& a) {
scanner.discard_space();
for (int i = len - 1; i >= 0; ++i) {
a[i] = *scanner.itr != '0';
++scanner.itr;
}
}
};
template<class T>
struct ScanFunction<T, std::enable_if_t<is_arithmetic_v<T>>> {
template<class Scanner>
static void scan(Scanner& scanner, T& a) {
scanner.scan_arithmetic(a);
}
};
template<class T>
struct ScanFunction<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
template<std::size_t i = 0, class Scanner>
static void scan(Scanner& scanner, T& a) {
if constexpr (i < tuple_like_size_v<T>) {
ScanFunction<std::decay_t<tuple_like_element_t<i, T>>>::scan(scanner, get<i>(a));
scan<i + 1>(scanner, a);
}
}
};
template<class T>
struct ScanFunction<T, std::enable_if_t<is_range_v<T>>> {
template<class Scanner>
static void scan(Scanner& scanner, T& a) {
for (auto&& i: a) ScanFunction<range_value_t<T>>::scan(scanner, i);
}
};
template<class Tuple, std::size_t idx>
struct ScanFunction<Indexed<Tuple, idx>> {
template<class Scanner>
struct ScannerWrapper: Scanner {
template<class T>
void scan_arithmetic(T& a) {
Scanner::scan_arithmetic(a);
--a;
}
};
template<std::size_t i = 0, class Scanner>
static void scan_impl(ScannerWrapper<Scanner>& scanner_wrapper, const Tuple& args_tuple) {
if constexpr (i < tuple_like_size_v<Tuple>) {
ScanFunction<std::decay_t<tuple_like_element_t<i, Tuple>>>::scan(scanner_wrapper, get<i>(args_tuple));
scan_impl<i + 1>(scanner_wrapper, args_tuple);
}
}
template<class Scanner>
static void scan(Scanner& scanner, const Indexed<Tuple, idx>& a) {
ScannerWrapper<Scanner>& scanner_wrapper = static_cast<ScannerWrapper<Scanner>&>(scanner);
scan_impl(scanner_wrapper, a.args_tuple);
}
};
// 標準入力から値を入力する関数
Scanner<Reader<>::iterator> scan{input.begin()};
} // namespace kpr
#line 3 "kpr/io/out.hpp"
#include <algorithm>
#line 6 "kpr/io/out.hpp"
#include <cmath>
#line 11 "kpr/io/out.hpp"
#include <string_view>
#line 19 "kpr/io/out.hpp"
namespace kpr {
// バッファを用いてファイルに書き込むクラス
template<std::size_t buf_size = KYOPRO_BUFFER_SIZE>
struct Writer {
private:
int fd, idx;
std::array<char, buf_size> buffer;
public:
// バッファサイズを取得
static constexpr KYOPRO_BASE_INT get_buf_size() noexcept {
return buf_size;
}
Writer() noexcept = default;
Writer(int fd) noexcept: fd(fd), idx(0), buffer() {}
Writer(FILE* fp) noexcept: fd(fileno(fp)), idx(0), buffer() {}
~Writer() {
[[maybe_unused]]ssize_t res = write(fd, buffer.begin(), idx);
}
// 出力イテレータ
struct iterator {
private:
Writer& writer;
public:
using difference_type = void;
using value_type = void;
using pointer = void;
using reference = void;
using iterator_category = std::output_iterator_tag;
iterator() noexcept = default;
iterator(Writer& writer) noexcept: writer(writer) {}
iterator& operator ++() {
++writer.idx;
if (writer.idx == buf_size) {
[[maybe_unused]]ssize_t res = write(writer.fd, writer.buffer.begin(), buf_size);
writer.idx = 0;
}
return *this;
}
iterator operator ++(int) {
iterator before = *this;
operator ++();
return before;
}
char& operator *() const {
return writer.buffer[writer.idx];
}
// バッファを全て出力する
void flush() const {
[[maybe_unused]] ssize_t res = write(writer.fd, writer.buffer.begin(), writer.idx);
}
};
// ファイルの最初を示すイテレータを取得
iterator begin() noexcept {
return iterator(*this);
}
};
// 標準出力、標準エラー出力
Writer output{1}, error{2};
// 値の出力の関数クラス
template<class, class = void>
struct PrintFunction;
// 出力イテレータを用いて値を出力するクラス
template<class Iterator, bool _space = true, bool _line = true, bool _debug = false, bool _comment = false, bool _flush = false, std::size_t decimal_precision = KYOPRO_DECIMAL_PRECISION>
struct Printer {
using iterator_type = Iterator;
// 指定されたオプション
static constexpr bool space = _space, line = _line, debug = _debug, comment = _comment, flush = _flush;
// 指定された小数誤差を取得
static constexpr KYOPRO_BASE_INT get_decimal_precision() noexcept {
return decimal_precision;
}
// 出力イテレータ
Iterator itr;
Printer() noexcept = default;
Printer(Iterator itr) noexcept: itr(itr) {}
// 一文字出力する
void print_char(char c) {
*itr = c;
++itr;
}
// 整数、小数を出力
template<class T>
void print_arithmetic(T a) {
if constexpr (is_floating_point_v<T>) {
if (a == std::numeric_limits<T>::infinity()) {
print_char('i');
print_char('n');
print_char('f');
return;
}
if (a == -std::numeric_limits<T>::infinity()) {
print_char('-');
print_char('i');
print_char('n');
print_char('f');
return;
}
if (std::isnan(a)) {
print_char('n');
print_char('a');
print_char('n');
return;
}
}
if constexpr (std::is_signed_v<T>) if (a < 0) {
print_char('-');
a = -a;
}
std::uint_fast64_t p = a;
std::string s;
do {
s += '0' + p % 10;
p /= 10;
} while (p > 0);
for (auto i = s.rbegin(); i != s.rend(); ++i) print_char(*i);
if constexpr (is_integer_v<T>) return;
print_char('.');
a -= p;
for (int i = 0; i < static_cast<int>(decimal_precision); ++i) {
a *= 10;
print_char('0' + static_cast<std::uint_fast64_t>(a) % 10);
}
}
// 区切り文字を出力する
void print_sep() {
if constexpr (debug) print_char(',');
if constexpr (space) print_char(' ');
}
// 区切り文字を出力する(型によって変更)
template<class type>
void print_sep_by_type() {
if constexpr (is_tuple_like_v<type> || is_range_v<type>) {
print_end();
if constexpr (comment) print_comment();
} else print_sep();
}
// 最後の文字を出力する
void print_end() {
if constexpr (debug) print_char(',');
if constexpr (line) print_char('\n');
}
// コメント記号を出力する
void print_comment() {
if constexpr (comment) {
print_char('#');
print_char(' ');
}
}
// 複数の値を出力
template<bool first = true>
void operator ()() {
if constexpr (first) print_comment();
print_end();
if constexpr (flush) itr.flush();
}
template<bool first = true, class Head, class... Args>
void operator ()(Head&& head, Args&&... args) {
if constexpr (first) print_comment();
else print_sep();
PrintFunction<std::decay_t<Head>>::print(*this, std::forward<Head>(head));
operator ()<false>(std::forward<Args>(args)...);
}
};
template<>
struct PrintFunction<char> {
template<class Printer>
static void print(Printer& printer, char a) {
if constexpr (Printer::debug) printer.print_char('\'');
printer.print_char(a);
if constexpr (Printer::debug) printer.print_char('\'');
}
};
template<>
struct PrintFunction<bool> {
template<class Printer>
static void print(Printer& printer, bool a) {
printer.print_char(static_cast<char>('0' + a));
}
};
template<class T>
struct PrintFunction<T, std::enable_if_t<std::is_convertible_v<T, std::string_view>>> {
template<class Printer>
static void print(Printer& printer, std::string_view a) {
if constexpr (Printer::debug) printer.print_char('"');
for (char i: a) printer.print_char(i);
if constexpr (Printer::debug) printer.print_char('"');
}
};
template<std::size_t len>
struct PrintFunction<std::bitset<len>> {
template<class Printer>
static void print(Printer& printer, const std::bitset<len>& a) {
for (int i = len - 1; i >= 0; --i) PrintFunction<bool>::print(printer, a[i]);
}
};
template<class T>
struct PrintFunction<T, std::enable_if_t<std::is_arithmetic_v<T>>> {
template<class Printer>
static void print(Printer& printer, T a) {
printer.print_arithmetic(a);
}
};
template<class T>
struct PrintFunction<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
template<std::size_t i = 0, class Printer>
static void print(Printer& printer, const T& a) {
using element_type = std::decay_t<tuple_like_element_t<i, T>>;
if constexpr (Printer::debug && i == 0) printer.print_char('{');
if constexpr (tuple_like_size_v<T> != 0) PrintFunction<element_type>::print(printer, get<i>(a));
if constexpr (i + 1 < tuple_like_size_v<T>) {
printer.template print_sep_by_type<element_type>();
print<i + 1>(printer, a);
} else if constexpr (Printer::debug) printer.print_char('}');
}
};
template<class T>
struct PrintFunction<T, std::enable_if_t<is_range_v<T> && !std::is_convertible_v<T, std::string_view>>> {
template<class Printer>
static void print(Printer& printer, const T& a) {
using value_type = range_value_t<T>;
if constexpr (Printer::debug) printer.print_char('{');
if (!std::empty(a)) {
for (auto i = std::begin(a); ; ) {
PrintFunction<value_type>::print(printer, *i);
if (++i != std::end(a)) printer.template print_sep_by_type<value_type>();
else break;
}
}
if constexpr (Printer::debug) printer.print_char('}');
}
};
template<class Tuple, std::size_t idx>
struct PrintFunction<Indexed<Tuple, idx>> {
template<class Printer>
struct PrinterWrapper: Printer {
template<class T>
void print_arithmetic(T a) {
Printer::print_arithmetic(a + 1);
}
};
template<class Printer>
static void print(Printer& printer, const Indexed<Tuple, idx>& a) {
PrinterWrapper<Printer>& printer_wrapper = static_cast<PrinterWrapper<Printer>&>(printer);
PrintFunction<Tuple>::print(printer_wrapper, a.args_tuple);
}
};
// 標準出力、標準エラー出力に値を出力する(改行、区切り文字なし)
Printer<Writer<>::iterator, false, false> print{output.begin()}, eprint{error.begin()};
// 標準出力、標準エラー出力に値を出力する(改行、区切り文字あり)
Printer<Writer<>::iterator> println{output.begin()}, eprintln{error.begin()};
} // namespace kpr
#line 6 "kpr/math/Montgomery.hpp"
namespace kpr {
template<class T>
struct Montgomery {
static_assert(is_unsigned_integer_v<T>, "The given type must be an unsigned integer type");
using value_type = T;
T mod;
private:
using larger_type = next_integer_t<T>;
T r, n2;
public:
constexpr void set_mod(T mod) noexcept {
this->mod = mod;
n2 = -static_cast<larger_type>(mod) % mod;
T t = 0;
r = 0;
for (int i = 0; i < std::numeric_limits<T>::digits; ++i) {
if (!(t & 1)) {
t += mod;
r += static_cast<T>(1) << static_cast<T>(i);
}
t >>= 1;
}
}
constexpr KYOPRO_BASE_INT get_mod() const noexcept {
return mod;
}
Montgomery() noexcept = default;
Montgomery(T mod) noexcept {
set_mod(mod);
}
constexpr T transform(T x) const noexcept {
return reduce(static_cast<larger_type>(x) * n2);
}
constexpr T inv_transform(T x) const noexcept {
T y = reduce(x);
return y >= mod ? y - mod : y;
}
constexpr T reduce(larger_type x) const noexcept {
return (x + static_cast<larger_type>(static_cast<T>(x) * r) * mod) >> std::numeric_limits<T>::digits;
}
};
} // namespace kpr
#line 13 "kpr/math/DynamicModInt.hpp"
namespace kpr {
template<class T, std::size_t kind = 0, bool = false>
struct DynamicModInt {
static_assert(std::is_unsigned_v<T>, "The given type must be an unsigned integer type");
using value_type = T;
private:
using larger_type = next_integer_t<T>;
inline static Montgomery<T> montgomery;
public:
T value;
static constexpr KYOPRO_BASE_INT get_kind() noexcept {
return kind;
}
static void set_mod(T mod) noexcept {
montgomery.set_mod(mod);
}
static KYOPRO_BASE_INT get_mod() noexcept {
return montgomery.mod;
}
KYOPRO_BASE_INT get_val() noexcept {
return montgomery.inv_transform(value);
}
DynamicModInt() noexcept = default;
DynamicModInt(T value) noexcept: value(montgomery.transform(value % montgomery.mod + montgomery.mod)) {}
template<class U>
explicit operator U() const noexcept {
return montgomery.inv_transform(value);
}
static DynamicModInt raw(T value) noexcept {
DynamicModInt res;
res.value = montgomery.transform(value);
return res;
}
DynamicModInt pow(KYOPRO_BASE_UINT n) const noexcept {
DynamicModInt res = 1, a = *this;
while (n > 0) {
if (n & 1) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
DynamicModInt inv() const noexcept {
return pow(montgomery.mod - 2);
}
DynamicModInt operator +() const noexcept {
return *this;
}
DynamicModInt operator -() const noexcept {
return value == 0 ? 0 : montgomery.mod - value;
}
DynamicModInt& operator ++() noexcept {
*this += DynamicModInt::raw(1);
return *this;
}
DynamicModInt operator ++(int) noexcept {
DynamicModInt before = *this;
++*this;
return before;
}
DynamicModInt& operator --() noexcept {
*this -= DynamicModInt::raw(1);
return *this;
}
DynamicModInt operator --(int) noexcept {
DynamicModInt before = *this;
--*this;
return before;
}
DynamicModInt& operator +=(DynamicModInt rhs) noexcept {
if ((value += rhs.value - (montgomery.mod << 1)) > std::numeric_limits<std::make_signed_t<T>>::max()) value += montgomery.mod << 1;
return *this;
}
DynamicModInt& operator -=(DynamicModInt rhs) noexcept {
if ((value -= rhs.value) > std::numeric_limits<std::make_signed_t<T>>::max()) value += montgomery.mod << 1;
return *this;
}
DynamicModInt& operator *=(DynamicModInt rhs) noexcept {
value = montgomery.reduce(static_cast<larger_type>(value) * rhs.value);
return *this;
}
DynamicModInt& operator /=(DynamicModInt rhs) noexcept {
value = montgomery.reduce(static_cast<larger_type>(value) * rhs.inv().value);
return *this;
}
friend DynamicModInt operator +(DynamicModInt lhs, DynamicModInt rhs) noexcept {
return lhs += rhs;
}
friend DynamicModInt operator -(DynamicModInt lhs, DynamicModInt rhs) noexcept {
return lhs -= rhs;
}
friend DynamicModInt operator *(DynamicModInt lhs, DynamicModInt rhs) noexcept {
return lhs *= rhs;
}
friend DynamicModInt operator /(DynamicModInt lhs, DynamicModInt rhs) noexcept {
return lhs /= rhs;
}
friend bool operator ==(DynamicModInt lhs, DynamicModInt rhs) noexcept {
return lhs.value == rhs.value;
}
friend bool operator !=(DynamicModInt lhs, DynamicModInt rhs) noexcept {
return lhs.value != rhs.value;
}
friend struct ScanFunction<DynamicModInt>;
friend struct PrintFunction<DynamicModInt>;
};
template<class T, std::size_t kind>
struct ScanFunction<DynamicModInt<T, kind>> {
template<class Scanner>
static void scan(Scanner& scanner, DynamicModInt<T, kind>& a) {
std::int_fast64_t value;
ScanFunction<std::int_fast64_t>::scan(scanner, value);
a.value = a.montgomery.transform(value % a.montgomery.mod + a.montgomery.mod);
}
};
template<class T, std::size_t kind>
struct PrintFunction<DynamicModInt<T, kind>> {
template<class Printer>
static void print(Printer& printer, const DynamicModInt<T, kind>& a) {
PrintFunction<T>::print(printer, a.montgomery.inv_transform(a.value));
}
};
template<class T, std::size_t kind>
struct Hash<DynamicModInt<T, kind>> {
using value_type = DynamicModInt<T, kind>;
std::size_t operator ()(DynamicModInt<T, kind> a) const noexcept {
return static_cast<std::size_t>(a);
}
};
} // namespace kpr
#line 2 "kpr/math/ModInt.hpp"
#include <cassert>
#line 6 "kpr/algorithm/bit.hpp"
namespace kpr {
// 立っているbitの個数を返す
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
static_assert(is_integer_v<T>, "The argument must be an integer");
constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_popcount(x);
else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_popcountl(x);
else return __builtin_popcountll(x);
}
} pop_count;
// 最上位bitより左の連続した0ビットの数を返す
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
static_assert(is_integer_v<T>, "The argument must be an integer");
constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
if (x == 0) return 0;
if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_clz(x) + digits - std::numeric_limits<unsigned int>::digits;
else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_clzl(x) + digits - std::numeric_limits<unsigned long>::digits;
else return __builtin_clzll(x) + digits - std::numeric_limits<unsigned long long>::digits;
}
} lzero_count;
// 1の位から連続した0ビットの数を返す
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
static_assert(is_integer_v<T>, "The argument must be an integer");
constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
if (x == 0) return digits;
static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_ctz(x);
else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_ctzl(x);
else return __builtin_ctzll(x);
}
} rzero_count;
// ビット幅を返す
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
static_assert(is_integer_v<T>, "The argument must be an integer");
constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
if (x == 0) return 0;
if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return std::numeric_limits<unsigned int>::digits - __builtin_clz(x);
else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return std::numeric_limits<unsigned long>::digits - __builtin_clzl(x);
else return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(x);
}
} bit_len;
// 1 << n が与えられた数以下である最大の n を返す (0 の場合、0を返す)
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
return bit_len(x >> static_cast<T>(1));
}
} floor_bit;
// 1 << n が与えられた数以上である最小の n を返す
[[maybe_unused]] inline constexpr struct {
template<class T>
constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
if (x == 0) return 0;
return bit_len(x - static_cast<T>(1));
}
} ceil_bit;
} // namespace kpr
#line 4 "kpr/math/mod.hpp"
namespace kpr {
[[maybe_unused]] inline constexpr struct {
template<class T, class U>
constexpr std::common_type_t<T, U> operator ()(T x, U m) const noexcept {
static_assert(is_integer_v<T> && is_integer_v<U>, "Both of the arguments must be integers");
if constexpr (is_unsigned_integer_v<T> || is_unsigned_integer_v<U>) return x % m;
return (x %= m) < 0 ? x + m : x;
}
} floor_mod;
[[maybe_unused]] inline constexpr struct {
template<class T, class U>
constexpr std::common_type_t<T, U> operator ()(T x, U m) const noexcept {
return m - floor_mod(x - 1, m) - static_cast<T>(1);
}
} ceil_mod;
} // namespace kpr
#line 16 "kpr/math/ModInt.hpp"
namespace kpr {
template<KYOPRO_BASE_UINT mod>
struct ModInt {
using value_type = uint_least_t<bit_len(mod * 2 - 2)>;
using multiplies_type = uint_least_t<bit_len(mod) * 2>;
static constexpr value_type m = mod;
value_type value;
static constexpr KYOPRO_BASE_INT get_mod() noexcept {
return m;
}
constexpr ModInt() noexcept = default;
template<class T>
constexpr ModInt(T value) noexcept: value(floor_mod(value, m)) {}
template<class T>
explicit constexpr operator T() const noexcept {
return value;
}
static constexpr ModInt raw(value_type value) noexcept {
ModInt res;
res.value = value;
return res;
}
constexpr ModInt pow(KYOPRO_BASE_UINT n) const noexcept {
value_type res = 1, a = value;
while (n > 0) {
if (n & 1) res = static_cast<multiplies_type>(res) * a % m;
a = static_cast<multiplies_type>(a) * a % m;
n >>= 1;
}
return res;
}
constexpr ModInt inv() const noexcept {
value_type a = value, b = m;
std::make_signed_t<value_type> u = 1, v = 0;
while (b > 0) {
value_type t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return floor_mod(u, get_mod());
}
constexpr ModInt operator +() const noexcept {
return *this;
}
constexpr ModInt operator -() const noexcept {
return value == 0 ? 0 : m - value;
}
constexpr ModInt& operator ++() noexcept {
if (++value >= m) value -= m;
return *this;
}
constexpr ModInt operator ++(int) noexcept {
ModInt before = *this;
++*this;
return before;
}
constexpr ModInt& operator --() noexcept {
if (value == 0) value = m;
--value;
return *this;
}
constexpr ModInt operator --(int) noexcept {
ModInt before = *this;
--*this;
return before;
}
constexpr ModInt& operator +=(ModInt rhs) noexcept {
if ((value += rhs.value) >= m) value -= m;
return *this;
}
constexpr ModInt& operator -=(ModInt rhs) noexcept {
if (value < rhs.value) value += m;
value -= rhs.value;
return *this;
}
constexpr ModInt& operator *=(ModInt rhs) noexcept {
value = static_cast<multiplies_type>(value) * rhs.value % m;
return *this;
}
constexpr ModInt& operator /=(ModInt rhs) noexcept {
value = static_cast<multiplies_type>(value) * rhs.inv().value % m;
return *this;
}
friend constexpr ModInt operator +(ModInt lhs, ModInt rhs) noexcept {
return lhs += rhs;
}
friend constexpr ModInt operator -(ModInt lhs, ModInt rhs) noexcept {
return lhs -= rhs;
}
friend constexpr ModInt operator *(ModInt lhs, ModInt rhs) noexcept {
return lhs *= rhs;
}
friend constexpr ModInt operator /(ModInt lhs, ModInt rhs) noexcept {
return lhs /= rhs;
}
friend constexpr bool operator ==(ModInt lhs, ModInt rhs) noexcept {
return lhs.value == rhs.value;
}
friend constexpr bool operator !=(ModInt lhs, ModInt rhs) noexcept {
return lhs.value != rhs.value;
}
template<class Scanner>
void scan(Scanner& scanner) {
std::int_fast64_t value;
scanner.scan(value);
value = floor_mod(value, m);
}
template<class Printer>
void print(Printer& printer) const {
printer.print(value);
}
};
template<KYOPRO_BASE_UINT mod>
struct ScanFunction<ModInt<mod>> {
template<class Scanner>
static void scan(Scanner& scanner, ModInt<mod>& a) {
std::int_fast64_t value;
ScanFunction<std::int_fast64_t>::scan(scanner, value);
a.value = floor_mod(value, a.m);
}
};
template<KYOPRO_BASE_UINT mod>
struct PrintFunction<ModInt<mod>> {
template<class Printer>
static void print(Printer& printer, ModInt<mod> a) {
PrintFunction<typename ModInt<mod>::value_type>::print(printer, a.value);
}
};
template<KYOPRO_BASE_UINT mod>
struct Hash<ModInt<mod>> {
using value_type = ModInt<mod>;
constexpr std::size_t operator ()(ModInt<mod> a) const noexcept {
return static_cast<std::size_t>(a);
}
};
} // namespace kpr
#line 22 "kpr/template/alias.hpp"
namespace kpr {
using ushort = unsigned short;
using ll = KYOPRO_LL;
using ull = unsigned long long;
using lf = KYOPRO_LF;
using llf = long double;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
#ifdef __SIZEOF_FLOAT128__
using f128 = __float128;
#endif
using mint = KYOPRO_MINT;
using dmint = DynamicModInt<KYOPRO_BASE_UINT>;
using str = std::string;
template<class T, std::size_t idx, class... Args>
struct agg_type {
using type = typename agg_type<T, idx - 1, T, Args...>::type;
};
template<class T, class... Args>
struct agg_type<T, 0, Args...> {
using type = std::tuple<Args...>;
};
template<class T>
struct agg_type<T, 0, T, T> {
using type = std::pair<T, T>;
};
template<class T, std::size_t idx>
using agg = typename agg_type<T, idx>::type;
using ll2 = agg<ll, 2>;
using ll3 = agg<ll, 3>;
using ll4 = agg<ll, 4>;
using ll5 = agg<ll, 5>;
#define DEFINE_TEMPLATE_ALIAS(short_name, type, ...) \
template<__VA_ARGS__> \
using short_name = type; \
template<__VA_ARGS__> \
using V ## short_name = Vec<type>; \
template<__VA_ARGS__> \
using VV ## short_name = VVec<type>;
#define DEFINE_ALIAS(short_name, name, short_value_type, value_type) \
using short_name ## short_value_type = name<value_type>; \
using V ## short_name ## short_value_type = V ## name<value_type>; \
using VV ## short_name ## short_value_type = VV ## name<value_type>; \
using short_name ## V ## short_value_type = name<Vec<value_type>>; \
using V ## short_name ## V ## short_value_type = V ## name<Vec<value_type>>;
#define DEFINE_ALIAS_FOR_VEC(short_name, name, short_value_type, value_type) \
using V ## short_value_type = Vec<value_type>; \
using VV ## short_value_type = VVec<value_type>; \
using VVV ## short_value_type = VVVec<value_type>; \
using VVVV ## short_value_type = VVVVec<value_type>; \
using VVVVV ## short_value_type = VVVVVec<value_type>;
#define DEFINE_MAP_ALIAS_IMPL(short_name, name, short_value_type1, value_type1, short_value_type2, value_type2) \
using short_name ## short_value_type1 ## short_value_type2 = name<value_type1, value_type2>; \
using V ## short_name ## short_value_type1 ## short_value_type2 = V ## name<value_type1, value_type2>; \
using VV ## short_name ## short_value_type1 ## short_value_type2 = VV ## name<value_type1, value_type2>; \
using short_name ## V ## short_value_type1 ## short_value_type2 = name<Vec<value_type1>, value_type2>; \
using short_name ## short_value_type1 ## V ## short_value_type2 = name<value_type1, Vec<value_type2>>; \
using short_name ## V ## short_value_type1 ## V ## short_value_type2 = name<Vec<value_type1>, Vec<value_type2>>; \
using V ## short_name ## V ## short_value_type1 ## short_value_type2 = V ## name<Vec<value_type1>, value_type2>; \
using V ## short_name ## short_value_type1 ## V ## short_value_type2 = V ## name<value_type1, Vec<value_type2>>; \
using V ## short_name ## V ## short_value_type1 ## V ## short_value_type2 = V ## name<Vec<value_type1>, Vec<value_type2>>;
#define DEFINE_MAP_ALIAS(...) \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, b, bool); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, i, int); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, l, ll); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, f, float); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, lf, lf); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, llf, llf); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, m, mint); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, dm, dmint); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, c, char); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, s, str); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll2, ll2); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll3, ll3); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll4, ll4); \
DEFINE_MAP_ALIAS_IMPL(__VA_ARGS__, ll5, ll5);
#define DEFINE_CONTAINER_ALIAS(define_alias, short_name, name) \
define_alias(short_name, name, b, bool); \
define_alias(short_name, name, i, int); \
define_alias(short_name, name, l, ll); \
define_alias(short_name, name, f, float); \
define_alias(short_name, name, lf, lf); \
define_alias(short_name, name, llf, llf); \
define_alias(short_name, name, m, mint); \
define_alias(short_name, name, dm, dmint); \
define_alias(short_name, name, c, char); \
define_alias(short_name, name, s, str); \
define_alias(short_name, name, ll2, ll2); \
define_alias(short_name, name, ll3, ll3); \
define_alias(short_name, name, ll4, ll4); \
define_alias(short_name, name, ll5, ll5);
template<class T>
using Vec = std::vector<T>;
template<class T>
using VVec = Vec<Vec<T>>;
template<class T>
using VVVec = Vec<VVec<T>>;
template<class T>
using VVVVec = Vec<VVVec<T>>;
template<class T>
using VVVVVec = Vec<VVVVec<T>>;
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS_FOR_VEC, V, Vec)
DEFINE_TEMPLATE_ALIAS(Deque, std::deque<T>, class T)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, DQ, Deque)
DEFINE_TEMPLATE_ALIAS(List, std::list<T>, class T)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, L, List)
DEFINE_TEMPLATE_ALIAS(ForwardList, std::forward_list<T>, class T)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, FL, ForwardList)
DEFINE_TEMPLATE_ALIAS(Set, std::decay_t<decltype(std::declval<std::set<Key, Compare>>())>, class Key, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, S, Set)
DEFINE_TEMPLATE_ALIAS(Map, std::decay_t<decltype(std::declval<std::map<Key, T, Compare>>())>, class Key, class T, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, M, Map)
DEFINE_TEMPLATE_ALIAS(HashSet, std::decay_t<decltype(std::declval<std::unordered_set<Key, H>>())>, class Key, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, HS, HashSet)
DEFINE_TEMPLATE_ALIAS(HashMap, std::decay_t<decltype(std::declval<std::unordered_map<Key, T, H>>())>, class Key, class T, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, HM, HashMap)
DEFINE_TEMPLATE_ALIAS(MultiSet, std::decay_t<decltype(std::declval<std::multiset<Key, Compare>>())>, class Key, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, MS, MultiSet)
DEFINE_TEMPLATE_ALIAS(MultiMap, std::decay_t<decltype(std::declval<std::multimap<Key, T, Compare>>())>, class Key, class T, class Compare = Less)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, MM, MultiMap)
DEFINE_TEMPLATE_ALIAS(HashMultiSet, std::decay_t<decltype(std::declval<std::unordered_multiset<Key, H>>())>, class Key, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, HMS, HashMultiSet)
DEFINE_TEMPLATE_ALIAS(HashMultiMap, std::decay_t<decltype(std::declval<std::unordered_multimap<Key, T, H>>())>, class Key, class T, class H = Hash<Key>)
DEFINE_CONTAINER_ALIAS(DEFINE_MAP_ALIAS, HMM, HashMultiMap)
DEFINE_TEMPLATE_ALIAS(Queue, std::decay_t<decltype(std::declval<std::queue<T, Container>>())>, class T, class Container = std::deque<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, Que, Queue)
DEFINE_TEMPLATE_ALIAS(Stack, std::decay_t<decltype(std::declval<std::stack<T, Container>>())>, class T, class Container = std::deque<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, Stk, Stack)
DEFINE_TEMPLATE_ALIAS(PriQ, std::decay_t<decltype(std::declval<std::priority_queue<T, Container, Compare>>())>, class T, class Compare = Less, class Container = Vec<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, PQ, PriQ)
DEFINE_TEMPLATE_ALIAS(HeapQ, std::decay_t<decltype(std::declval<std::priority_queue<T, Container, Compare>>())>, class T, class Compare = Greater, class Container = Vec<T>)
DEFINE_CONTAINER_ALIAS(DEFINE_ALIAS, HQ, HeapQ)
DEFINE_TEMPLATE_ALIAS(BitSet, std::bitset<size>, std::size_t size)
#undef DEFINE_TEMPLATE_ALIAS
#undef DEFINE_ALIAS
#undef DEFINE_ALIAS_FOR_VEC
#undef DEFINE_MAP_ALIAS_IMPL
#undef DEFINE_MAP_ALIAS
#undef DEFINE_CONTAINER_ALIAS
} // namespace kpr
using namespace std;
using namespace kpr;