結果
| 問題 | No.3178 free sort |
| ユーザー |
 VvyLw
|
| 提出日時 | 2025-06-13 22:14:37 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 38,500 bytes |
| コンパイル時間 | 3,984 ms |
| コンパイル使用メモリ | 344,924 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-13 22:14:45 |
| 合計ジャッジ時間 | 5,747 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 40 |
ソースコード
#line 1 "main.cpp"
/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")//*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#line 2 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
#ifndef TEMPLATE
#define TEMPLATE
#endif
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wdeprecated-copy"
#include <bits/stdc++.h>
namespace VvyLw {
enum TestCase { single, multi };
inline void solve() noexcept;
template <TestCase tc = single, int x = 12> constexpr inline void wa_haya_exe() noexcept {
std::cin.tie(nullptr) -> sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(x);
int t = 1;
if constexpr (tc == multi) {
std::cin >> t;
}
for([[maybe_unused]] const auto _: std::views::iota(0, t)) {
solve();
}
}
}
using enum VvyLw::TestCase;
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/alias.hpp"
#ifndef ALIAS
#define ALIAS
#endif
#line 8 "/home/wa_haya_exe/CP_Library/C++/core/alias.hpp"
#include <numbers>
#line 10 "/home/wa_haya_exe/CP_Library/C++/core/alias.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
constexpr int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};
constexpr int MOD = 0x3b800001;
constexpr int M0D = 1e9 + 7;
constexpr int INF = 1 << 30;
constexpr int64_t LINF = (1LL << 61) - 1;
constexpr long double DINF = std::numeric_limits<long double>::infinity();
template <internal::num T> constexpr T LIM = std::numeric_limits<T>::max();
constexpr long double PI = std::numbers::pi;
constexpr long double E = std::numbers::e;
typedef int64_t i64;
typedef long double ld;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
template <size_t N> using ti = std::array<i64, N>;
typedef ti<3> tri;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqr = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class T> using TREE = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::greater<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
/**
* @brief エイリアス
*/
#line 28 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
namespace man {
inline bool isdigit(const std::string &s) noexcept;
std::mt19937 EhaL(std::hash<std::string>()("Huitloxopetl"));
inline std::mt19937 rand() noexcept {
std::random_device seed_gen;
std::mt19937 engine {seed_gen()};
return engine;
}
template <class T, class U> constexpr inline bool chmax(T& a, const U& b) noexcept { if(a < b){ a = b; return true; } return false; }
template <class T, class U> constexpr inline bool chmin(T& a, const U& b) noexcept { if(a > b){ a = b; return true; } return false; }
template <internal::num T, internal::num U> constexpr inline bool overflow_if_add(const T a, const U b) noexcept { return (std::numeric_limits<T>::max() - a) < b; }
template <internal::num T, internal::num U> constexpr inline bool overflow_if_mul(const T a, const U b) noexcept { return (std::numeric_limits<T>::max() / a) < b; }
inline std::string string_replace(const std::string &s, const std::string &a, const std::string &b) noexcept { return std::regex_replace(s, std::regex(a), b); }
inline bool regex_contains(const std::string &s, const std::string &t) noexcept { return std::regex_search(s, std::regex(t)); }
constexpr inline auto yes(const bool ok) noexcept { return ok ? "Yes" : "No"; }
template <internal::num T> constexpr inline T sqr(const T x) noexcept { return x * x; }
template <internal::num T> constexpr inline T cub(const T x) noexcept { return x * x * x; }
template <std::integral T> constexpr inline T mod(T x, const T m) noexcept {
x %= m;
return x < 0 ? x + m : x;
}
template <std::integral T> constexpr inline T pow(T a, T b, const T mod = 0) noexcept {
T ret = 1;
if(mod != 0) {
ret %= mod;
a %= mod;
}
while(b > 0) {
if(b & 1) {
ret *= a;
}
if(mod != 0) {
ret %= mod;
}
a *= a;
if(mod) {
a %= mod;
}
b >>= 1;
}
return ret;
}
constexpr inline int64_t ceil(const long double x, const int64_t m) noexcept { return std::ceil(x / m); }
constexpr inline long double round(const long double x, const int64_t m, const short fx = 0) noexcept {
if(fx == 0) {
return std::round(x / m);
}
const uint64_t y = pow<uint64_t>(10, fx);
return std::round((x * y) / m) / y;
}
constexpr inline long double log(const int64_t x, const long double base = 2) noexcept { return std::log2(x) / std::log2(base); }
constexpr inline int bitdigit(const int64_t x) noexcept { return 64 - __builtin_clzll(x); }
constexpr inline int popcnt(const int64_t x) noexcept { return __builtin_popcountll(x); }
constexpr inline int fione(const int64_t x) noexcept { return __builtin_ffsll(x); }
constexpr inline int zrcnt(const int64_t x) noexcept { return __builtin_ctzll(x); }
template <internal::num T> constexpr inline bool scope(const T a, const T x, const T b) noexcept { return a <= x && x <= b; }
constexpr inline bool isupper(const char c) noexcept { return std::isupper(c); }
inline bool isupper(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isupper(el);
}
return ok;
}
constexpr inline bool islower(const char c) noexcept { return std::islower(c); }
inline bool islower(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= islower(el);
}
return ok;
}
constexpr inline bool isalpha(const char c) noexcept { return std::isalpha(c); }
inline bool isalpha(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isalpha(el);
}
return ok;
}
constexpr inline bool isdigit(const char c) noexcept { return std::isdigit(c); }
inline bool isdigit(const std::string &s) noexcept {
bool ok = true, neg = s.front() == '-';
for(const auto &el: s) {
if(neg) {
neg = false;
continue;
}
ok &= isdigit(el);
}
return ok;
}
constexpr inline bool isalnum(const char c) noexcept { return std::isalnum(c); }
inline bool isalnum(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isalnum(el);
}
return ok;
}
constexpr inline bool isspace(const char c) noexcept { return std::isspace(c); }
inline bool isspace(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isspace(el);
}
return ok;
}
constexpr inline bool ispunct(const char c) noexcept { return std::ispunct(c); }
inline bool ispunct(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= ispunct(el);
}
return ok;
}
constexpr inline bool isprint(const char c) noexcept { return std::isprint(c); }
inline bool isprint(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isprint(el);
}
return ok;
}
inline auto strins(std::string &s, const int id, const std::string &t) noexcept {
s.insert(id, t);
return std::ssize(s);
}
inline std::string toupper(std::string s) noexcept {
for(auto &c: s) {
c = std::toupper(c);
}
return s;
}
inline std::string tolower(std::string s) noexcept {
for(auto &c: s) {
c = std::tolower(c);
}
return s;
}
inline std::string ten_to(int64_t n, const int base, const bool upper = true) noexcept {
assert(base <= 10 || base == 16);
if(base == 16) {
std::stringstream ss;
ss << std::hex << n;
const std::string s = ss.str();
return upper ? toupper(s) : s;
}
if(n == 0 || base == 0) {
return "0";
}
std::vector<int> ret;
while(n > 0) {
ret.emplace_back(n % base);
n /= base;
}
std::string s;
for(const auto &e: ret | std::views::reverse) {
s += std::to_string(e);
}
return s;
}
inline int64_t to_ten(const std::string &s, const int base = 10) noexcept { return std::stoll(s, nullptr, base); }
template <std::integral... Ts> constexpr uint64_t gcd(const Ts... a) noexcept {
std::vector v = std::initializer_list<std::common_type_t<Ts...>>{a...};
uint64_t g = 0;
for(const auto &el: v) {
g = std::gcd(g, el);
}
return g;
}
template <std::integral... Ts> constexpr uint64_t lcm(const Ts... a) noexcept {
std::vector v = std::initializer_list<std::common_type_t<Ts...>>{a...};
uint64_t l = 1;
for(const auto &el: v) {
l = std::lcm(l, el);
}
return l;
}
template <internal::num... Ts> constexpr auto min(const Ts... a) noexcept { return std::min(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <internal::num... Ts> constexpr auto max(const Ts... a) noexcept { return std::max(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <class K, class V> inline std::vector<K> key_l(const std::map<K, V> &m, const V val) noexcept {
std::vector<K> keys;
for(auto it = m.cbegin(); it != m.cend(); ++it) {
if(it->second == val) {
keys.emplace_back(it->first);
}
}
return keys;
}
template <class K, class V> constexpr inline K key_min(const std::map<K, V> &m) noexcept { return m.begin()->first; }
template <class K, class V> constexpr inline K key_max(const std::map<K, V> &m) noexcept { return m.rbegin()->first; }
template <class K, class V> constexpr inline V key_min_v(const std::map<K, V> &m) noexcept { return m.begin()->second; }
template <class K, class V> constexpr inline V key_max_v(const std::map<K, V> &m) noexcept { return m.rbegin()->second; }
template <class K, class V> constexpr inline auto val_min(const std::map<K, V> &m) noexcept {
return *std::ranges::min_element(m, [](const std::pair<K, V> &x, const std::pair<K, V> &y) -> bool { return x.second < y.second; });
}
template <class K, class V> constexpr inline auto val_max(const std::map<K, V> &m) noexcept {
return *std::ranges::max_element(m, [](const std::pair<K, V> &x, const std::pair<K, V> &y) -> bool { return x.second < y.second; });
}
template <std::integral T> constexpr inline T count(std::vector<T> v, const T &x) noexcept {
if(!std::ranges::is_sorted(v)) {
std::ranges::sort(v);
}
return std::ranges::upper_bound(v, x) - std::ranges::lower_bound(v, x);
}
template <class T> constexpr inline T inner_prod(const std::vector<T> &v, const std::vector<T> &u, const T init) noexcept { return std::inner_product(v.cbegin(), v.cend(), u.cbegin(), init); }
inline std::vector<int> iota(const int n, const int init = 0) noexcept {
std::vector<int> a(n);
std::iota(a.begin(), a.end(), init);
return a;
}
template <class T> constexpr inline int uniq(T& v) noexcept {
if(!std::ranges::is_sorted(v)) {
std::ranges::sort(v);
}
const auto it = std::ranges::unique(v);
v.erase(it.begin(), it.end());
return std::ssize(v);
}
template <class T> constexpr inline void rotate(T& s, const int idx) noexcept {
const int id = mod<int>(idx, std::ssize(s));
std::ranges::rotate(s, s.begin() + id);
}
template <class T> constexpr inline T set_diff(const T& s, const T& t) noexcept {
assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
T ret;
std::ranges::set_difference(s, t, std::inserter(ret, std::end(ret)));
return ret;
}
template <class T> constexpr inline T set_sum(const T& s, const T& t) noexcept {
assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
T ret;
std::ranges::set_union(s, t, std::inserter(ret, std::end(ret)));
return ret;
}
template <class T> constexpr inline T set_mul(const T& s, const T& t) noexcept {
assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
T ret;
std::ranges::set_intersection(s, t, std::inserter(ret, std::end(ret)));
return ret;
}
template <class T> inline std::vector<T> adj_diff(const std::vector<T> &v) noexcept {
std::vector<T> a;
std::adjacent_difference(v.cbegin(), v.cend(), std::back_inserter(a));
rotate(a, 1);
a.pop_back();
return a;
}
template <class T, class F> inline std::vector<T> isum(const std::vector<T> &v, const F &fn) noexcept {
std::vector<T> s{0};
std::inclusive_scan(v.cbegin(), v.cend(), std::back_inserter(s), fn);
return s;
}
template <class T> inline std::vector<T> rand_extract(const std::vector<T> &v, const int size) noexcept {
std::vector<T> ret;
std::ranges::sample(v, std::back_inserter(ret), size, rand());
return ret;
}
template <class T> inline T rand_extract(const std::vector<T> &v) noexcept {
std::vector<T> ret;
std::ranges::sample(v, std::back_inserter(ret), 1, rand());
return ret.front();
}
template <std::ranges::random_access_range T> inline auto sum(const T &v) noexcept { return std::accumulate(v.cbegin(), v.cend(), decltype(v.front())(0)); }
template <std::ranges::random_access_range T> inline auto sum(const T &v, const int a, const int b) noexcept { return std::accumulate(v.cbegin() + a, v.cbegin() + b, decltype(v.front())(0)); }
template <std::ranges::random_access_range T, class Boolean = bool> inline auto sum(const T &v, const Boolean &fn) noexcept { return std::accumulate(v.cbegin(), v.cend(), decltype(v.front())(0), fn); }
template <std::ranges::random_access_range T, class Boolean = bool> inline auto sum(const T &v, const int a, const int b, const Boolean &fn) noexcept { return std::accumulate(v.cbegin() + a, v.cbegin() + b, decltype(v.front())(0), fn); }
template <internal::num T, class Boolean = bool> constexpr inline T bins(T ok, T ng, const Boolean &fn, const long double eps = 1) noexcept {
while(std::abs(ok - ng) > eps) {
const T mid = (ok + ng) / 2;
(fn(mid) ? ok : ng) = mid;
}
return ok;
}
inline std::vector<std::string> rotate(const std::vector<std::string> &s) noexcept {
const int h = std::ssize(s), w = std::ssize(s.front());
std::vector t(w, std::string(h, {}));
for(const auto i: std::views::iota(0, h)) {
for(const auto j: std::views::iota(0, w)) {
t[j][i] = s[i][j];
}
}
for(const auto i: std::views::iota(0, w)) {
std::ranges::reverse(t[i]);
}
return t;
}
template <internal::num T> inline std::vector<std::vector<T>> rotate(const std::vector<std::vector<T>> &v) noexcept {
const int h = std::ssize(v), w = std::ssize(v.front());
std::vector ret(w, std::vector<T>(h));
for(const auto i: std::views::iota(0, h)) {
for(const auto j: std::views::iota(0, w)) {
ret[j][i] = v[i][j];
}
}
for(const auto i: std::views::iota(0, w)) {
std::ranges::reverse(ret[i]);
}
return ret;
}
template <std::integral T> constexpr inline T factor(T n, const T mod = 0) noexcept {
T ret = 1;
while(n > 0) {
ret *= n--;
if(mod) {
ret %= mod;
}
}
return ret;
}
template <std::integral T> constexpr inline T perm(T n, const T r, const T mod = 0) noexcept {
const T tmp = n;
T ret = 1;
while(n > tmp - r) {
ret *= n--;
if(mod) {
ret %= mod;
}
}
return ret;
}
template <std::integral T> constexpr inline T binom(T n, const T r, const T mod = 0) noexcept {
if(r < 0 || n < r) {
return 0;
}
T ret = 1;
for(const auto i: std::views::iota(1) | std::views::take(r)) {
ret *= n--;
if(mod) {
ret %= mod;
}
ret /= i;
if(mod) {
ret %= mod;
}
}
return ret;
}
constexpr inline bool is_int(const long double n) noexcept { return n == std::floor(n); }
constexpr inline bool is_sqr(const int64_t n) noexcept { return is_int(std::sqrt(n)); }
}
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp"
#line 5 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp"
typedef std::chrono::system_clock::time_point Timer;
Timer start, stop;
#if local
inline void now(Timer &t) noexcept { t = std::chrono::system_clock::now(); }
inline void time(const Timer &t1, const Timer &t2) noexcept { std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << "ms\n"; }
#else
void now(Timer &t){ void(0); }
void time(const Timer &t1, const Timer &t2){ void(0); }
#endif
/**
* @brief タイマー
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp"
#line 4 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp"
#ifndef ALIAS
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
#endif
namespace man {
namespace vec {
template <class T> using V = std::vector<T>;
typedef V<int64_t> zhl;
typedef V<uint64_t> uzhl;
typedef V<long double> dec;
typedef V<char> chr;
typedef V<std::string> str;
typedef V<bool> bol;
typedef V<zhl> zhl2;
typedef V<uzhl> uzhl2;
typedef V<dec> dec2;
typedef V<chr> chr2;
typedef V<str> str2;
typedef V<bol> bol2;
#ifdef EDGE
typedef V<man::edge> edg;
typedef V<edg> edg2;
#endif
template <class T, class U> inline V<U> ndiv(T&& n, U&& v) noexcept {
return V<U>(std::forward<T>(n), std::forward<U>(v));
}
template <class T, class... Ts> inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept {
return V<decltype(ndiv(std::forward<Ts>(v)...))>(std::forward<T>(n), ndiv(std::forward<Ts>(v)...));
}
template <internal::num T> constexpr V<T>& operator++(V<T>& v) noexcept { for(auto &el: v){ el++; } return v; }
template <internal::num T> constexpr V<T>& operator--(V<T>& v) noexcept { for(auto &el: v){ el--; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator+=(V<T>& v, const U x) noexcept { for(auto &el: v){ el += x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator-=(V<T>& v, const U x) noexcept { for(auto &el: v){ el -= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator*=(V<T>& v, const U x) noexcept { for(auto &el: v){ el *= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator/=(V<T>& v, const U x) noexcept { for(auto &el: v){ el /= x; } return v; }
template <std::integral T, std::integral U> constexpr V<T>& operator%=(V<T>& v, const U x) noexcept { for(auto &el: v){ el %= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T> operator+(const V<T>& v, const U x) noexcept { V<T> ret = v; ret += x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator-(const V<T>& v, const U x) noexcept { V<T> ret = v; ret -= x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator*(const V<T>& v, const U x) noexcept { V<T> ret = v; ret *= x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator/(const V<T>& v, const U x) noexcept { V<T> ret = v; ret /= x; return ret; }
template <std::integral T, std::integral U> constexpr V<T> operator%(const V<T>& v, const U x) noexcept { V<T> ret = v; ret %= x; return ret; }
}
}
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp"
#line 8 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp"
#ifndef ALIAS
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
#endif
namespace man {
namespace pav {
template <class T, class U> using P = std::pair<T, U>;
template <class T> using PP = P<T, T>;
typedef PP<int64_t> zhl;
typedef PP<long double> dec;
typedef PP<char> chr;
typedef PP<std::string> str;
template <internal::num T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; }
template <internal::num T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; }
template <internal::num T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; }
template <internal::num T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; }
template <internal::num T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; }
template <internal::num T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; }
template <internal::num T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; }
template <internal::num T, internal::num U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; }
template <internal::num T, internal::num U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; }
template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first == q.first && p.second == q.second; }
template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p == q); }
template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second < q.second; } return p.first < q.first; }
template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second <= q.second; } return p.first < q.first; }
template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second > q.second; } return p.first > q.first; }
template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second >= q.second; } return p.first > q.first; }
template <class T, class U> constexpr bool operator==(const P<T, U> &p, const P<T, U> &q) noexcept { return p.first == q.first && p.second == q.second; }
template <class T, class U> constexpr bool operator!=(const P<T, U> &p, const P<T, U> &q) noexcept { return !(p == q); }
template <class T, class U> constexpr bool operator<(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second < q.second; } return p.first < q.first; }
template <class T, class U> constexpr bool operator<=(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second <= q.second; } return p.first < q.first; }
template <class T, class U> constexpr bool operator>(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second > q.second; } return p.first > q.first; }
template <class T, class U> constexpr bool operator>=(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second >= q.second; } return p.first > q.first; }
template <internal::num T> constexpr inline PP<T> rotate(const PP<T>& a) noexcept { return {-a.second, a.first}; } // 90 degree ccw
template <internal::num T> constexpr inline dec rotate(const PP<T>& a, const int ang) noexcept {
assert(0 <= ang && ang < 360);
const long double rad = PI * ang / 180;
return {a.first * std::cos(rad) - a.second * std::sin(rad), a.first * std::sin(rad) + a.second * std::cos(rad)};
}
template <internal::num T> constexpr inline T dot(const PP<T>& a, const PP<T>& b) noexcept { return a.first * b.first + a.second * b.second; }
template <internal::num T> constexpr inline T cross(const PP<T>& a, const PP<T>& b) noexcept { return dot(rotate(a), b); }
template <internal::num T> constexpr inline T square(const PP<T>& a) noexcept { return dot(a, a); }
template <internal::num T> constexpr inline long double grad(const PP<T>& a) noexcept { assert(a.first != 0); return 1.0L * a.second / a.first; }
template <internal::num T> constexpr inline long double abs(const PP<T>& a) noexcept { return std::hypotl(a.first, a.second); }
template <std::integral T> constexpr inline T lcm(const PP<T>& a) noexcept { return std::lcm(a.first, a.second); }
template <std::integral T> constexpr inline T gcd(const PP<T>& a) noexcept { return std::gcd(a.first, a.second); }
template <std::integral T> constexpr inline PP<T> extgcd(const PP<T> &p) noexcept {
T x = 1, y = 0, t1 = 0, t2 = 0, t3 = 1, a, b;
std::tie(a,b) = p;
while(b > 0) {
t1 = a / b, a -= t1 * b;
std::swap(a, b);
x -= t1 * t2;
std::swap(x, t2);
y -= t1 * t3;
std::swap(y, t3);
}
return {x, y};
}
template <std::integral T> constexpr inline PP<T> normalize(PP<T> a) noexcept {
if(a == PP<T>{}) {
return a;
}
a /= gcd(a);
if(a < PP<T>{}) {
a = -a;
}
return a;
}
template <class T, class U> constexpr inline P<U, T> swap(const P<T, U> &p) noexcept { const P<U, T> ret = {p.second, p.first}; return ret; }
template <class T, class U> inline std::vector<P<U, T>> swap(const std::vector<P<T, U>> &vp) noexcept {
std::vector<P<U, T>> ret;
for(const auto &el: vp) {
ret.emplace_back(swap(el));
}
return ret;
}
template <class T, class U> inline std::vector<T> first(const std::vector<P<T, U>> &vp) noexcept {
std::vector<T> ret;
for(const auto &el: vp) {
ret.emplace_back(el.first);
}
return ret;
}
template <class T, class U> inline std::vector<U> second(const std::vector<P<T, U>> &vp) noexcept {
std::vector<U> ret;
for(const auto &el: vp) {
ret.emplace_back(el.second);
}
return ret;
}
}
}
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/input.hpp"
#line 8 "/home/wa_haya_exe/CP_Library/C++/core/io/input.hpp"
#ifndef TEMPLATE
namespace man {
constexpr inline bool isdigit(const char c) noexcept { return std::isdigit(c); }
inline bool isdigit(const std::string &s) noexcept {
bool ok = true, neg = s.front() == '-';
for(const auto &el: s) {
if(neg) {
neg = false;
continue;
}
ok &= isdigit(el);
}
return ok;
}
}
#endif
namespace IO {
inline std::istream& operator>>(std::istream &is, __int128_t &val) noexcept {
std::string s;
std::cin >> s;
assert(man::isdigit(s));
bool neg = s.front() == '-';
val = 0;
for(const auto &el: s) {
if(neg) {
neg = false;
continue;
}
val = 10 * val + el - '0';
}
if(s.front()=='-') {
val = -val;
}
return is;
}
template <class T, class U> inline std::istream& operator>>(std::istream &is, std::pair<T, U> &p) noexcept { is >> p.first >> p.second; return is; }
template <std::ranges::random_access_range T> requires (!std::same_as<std::remove_cvref_t<T>, std::string> && !std::same_as<std::remove_cvref_t<T>, std::string_view> && !std::is_array_v<std::remove_cvref_t<T>>) inline std::istream& operator>>(std::istream &is, T &v) noexcept { for(auto &el: v){ is >> el; } return is; }
template <class Head, class... Tail> inline bool input(Head &head, Tail &...tail) noexcept {
if(!(std::cin >> head)) {
return false;
}
if constexpr(sizeof...(Tail) > 0) {
input(tail...);
}
return true;
}
} // IO
/**
* @brief 入力
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp"
#line 6 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp"
namespace IO {
inline std::ostream &operator<<(std::ostream &dest, const __int128_t &value) noexcept {
std::ostream::sentry s(dest);
constexpr char dig[] = "0123456789";
if(s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = dig[tmp % 10];
tmp /= 10;
} while(tmp != 0);
if(value < 0) {
--d;
*d = '-';
}
const int len = std::end(buffer) - d;
if(dest.rdbuf() -> sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
template <class T, class U> inline std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p) noexcept { os << p.first << ' ' << p.second; return os; }
template <class K, class V> inline std::ostream& operator<<(std::ostream &os, const std::map<K, V> &m) noexcept {
if(!m.empty()) {
os << m.begin()->first << ' ' << m.begin()->second;
for(auto i = m.begin(); ++i != m.end();) {
os << '\n' << i->first << ' ' << i->second;
}
}
return os;
}
template <std::ranges::range T> requires (!std::same_as<std::remove_cvref_t<T>, std::string> && !std::same_as<std::remove_cvref_t<T>, std::string_view> && !std::is_array_v<std::remove_cvref_t<T>>) inline std::ostream& operator<<(std::ostream &os, const T &v) noexcept {
if(!v.empty()) {
os << *v.cbegin();
for(auto i = v.cbegin(); ++i != v.cend();) {
os << ' ' << *i;
}
}
return os;
}
enum Flash { non_flush, flush };
template <Flash f = non_flush, class Head, class... Tail> inline void print(const Head& head, const Tail& ...tail) noexcept {
std::cout << head;
if constexpr(sizeof...(Tail) > 0) {
std::cout << ' ';
print<f>(tail...);
} else {
if constexpr(f == flush) {
std::cout.flush();
}
}
}
inline void println() noexcept { std::cout << '\n'; }
template <Flash f = non_flush, class Head, class... Tail> inline void println(const Head& head, const Tail& ...tail) noexcept { print<f>(head, tail...); std::cout << '\n'; }
} // IO
using enum IO::Flash;
#if local
//https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3
#include <C++/core/io/debug_print.hpp>
#else
#define dump(...) static_cast<void>(0)
#endif
/**
* @brief 出力
*/
#line 381 "/home/wa_haya_exe/CP_Library/C++/template.hpp"
#define REP(n) for([[maybe_unused]] const auto _: std::views::iota(0, (n)))
using namespace IO;
using namespace std::views;
namespace iter = std::ranges;
/**
* @brief テンプレート
* @docs docs/template.md
*/
#line 2 "/home/wa_haya_exe/CP_Library/C++/math/Modint.hpp"
#pragma GCC diagnostic ignored "-Wdeprecated-copy"
#ifndef MODINT
#define MODINT
#endif
#line 14 "/home/wa_haya_exe/CP_Library/C++/math/Modint.hpp"
#include <type_traits>
#line 16 "/home/wa_haya_exe/CP_Library/C++/math/Modint.hpp"
#include <ranges>
namespace man {
template <uint mod> struct Modint {
uint num = 0;
constexpr Modint() noexcept {}
constexpr Modint(const Modint &x) noexcept : num(x.num){}
constexpr operator int64_t() const noexcept { return num; }
constexpr static unsigned get_mod(){ return mod; }
constexpr Modint& operator+=(Modint x) noexcept { num += x.num; if(num >= mod) num -= mod; return *this; }
constexpr Modint& operator++() noexcept { if(num == mod - 1) num = 0; else num++; return *this; }
constexpr Modint operator++(int) noexcept { Modint ans(*this); operator++(); return ans; }
constexpr Modint operator-() const noexcept { return Modint(0) -= *this; }
constexpr Modint& operator-=(Modint x) noexcept { if(num < x.num) num += mod; num -= x.num; return *this; }
constexpr Modint& operator--() noexcept { if(num == 0) num = mod - 1; else num--; return *this; }
constexpr Modint operator--(int) noexcept { Modint ans(*this); operator--(); return ans; }
constexpr Modint& operator*=(Modint x) noexcept { num = uint64_t(num) * x.num % mod; return *this; }
constexpr Modint& operator/=(Modint x) noexcept { return operator*=(x.inv()); }
constexpr void operator%=(Modint x) noexcept { void(0); }
template <class T> constexpr Modint(T x) noexcept {
using U = typename std::conditional<sizeof(T)>= 4, T, int>::type;
U y = x; y %= U(mod); if(y < 0) y += mod; num = unsigned(y);
}
template <class T> constexpr Modint operator+(T x) const noexcept { return Modint(*this) += x; }
template <class T> constexpr Modint& operator+=(T x) noexcept { return operator+=(Modint(x)); }
template <class T> constexpr Modint operator-(T x) const noexcept { return Modint(*this) -= x; }
template <class T> constexpr Modint& operator-=(T x) noexcept { return operator-=(Modint(x)); }
template <class T> constexpr Modint operator*(T x) const noexcept { return Modint(*this) *= x; }
template <class T> constexpr Modint& operator*=(T x) noexcept { return operator*=(Modint(x)); }
template <class T> constexpr Modint operator/(T x) const noexcept { return Modint(*this) /= x; }
template <class T> constexpr Modint& operator/=(T x) noexcept { return operator/=(Modint(x)); }
constexpr Modint inv() const noexcept { int64_t x = 0, y = 0; extgcd(num, mod, x, y); return x; }
static constexpr int64_t extgcd(int64_t a, int64_t b, int64_t &x, int64_t &y) noexcept { int64_t g = a; x = 1; y = 0; if(b){ g = extgcd(b, a % b, y, x); y -= a / b * x; } return g; }
constexpr Modint pow(uint64_t x) const noexcept { Modint ans = 1, cnt = *this; while(x){ if(x & 1) ans *= cnt; cnt *= cnt; x /= 2; } return ans; }
friend std::ostream& operator<<(std::ostream& os, const Modint& m){ os << m.num; return os; }
friend std::istream &operator>>(std::istream &is, Modint &a) {
int64_t t;
is >> t;
a = Modint(t);
return (is);
}
};
template <class mint> struct Comb {
private:
std::vector<mint> fac{1}, inv{1};
inline void reserve(uint64_t a) noexcept {
if(std::ssize(fac) >= a) {
return;
}
if(a < std::ssize(fac) * 2) {
a = std::ssize(fac) * 2;
}
if(a >= mint::get_mod()) {
a = mint::get_mod();
}
while(std::ssize(fac) < a) {
fac.emplace_back(fac.back() * mint(std::ssize(fac)));
}
inv.resize(std::ssize(fac));
inv.back() = fac.back().inv();
for(const auto i: std::views::iota(0, std::ssize(inv)) | std::views::reverse) {
inv[i - 1] = inv[i] * i;
}
}
public:
inline mint fact(const int64_t n) noexcept {
if(n < 0) {
return 0;
}
reserve(n + 1);
return fac[n];
}
inline mint nPr(int64_t n, const int64_t r) noexcept {
if(r < 0 || n < r) {
return 0;
}
if(n >> 24) {
mint ans = 1;
for(const auto i: std::views::iota(0, r)) {
ans *= n--;
}
return ans;
}
reserve(n + 1);
return fac[n] * inv[n - r];
}
inline mint nCr(const int64_t n, int64_t r) noexcept {
if(r < 0 || n < r) {
return 0;
}
r = std::min(r, n - r);
reserve(r + 1);
return nPr(n, r) * inv[r];
}
inline mint nHr(const int64_t n, const int64_t r) noexcept {
if(n == 0 && r == 0) {
return 1;
}
if(n <= 0 || r < 0) {
return 0;
}
return nCr(n + r - 1, r);
}
};
struct a_mint {
int val;
a_mint() : val(0){}
a_mint(const int64_t x) : val(x >= 0 ? x % get_mod() : (get_mod() - (-x) % get_mod()) % get_mod()){}
int getmod() { return get_mod(); }
static int &get_mod() {
static int mod = 0;
return mod;
}
static void set_mod(int md) { assert(md>0); get_mod() = md; }
a_mint &operator+=(const a_mint &p) noexcept {
if((val += p.val) >= get_mod()) {
val -= get_mod();
}
return *this;
}
a_mint &operator-=(const a_mint &p) noexcept {
if((val += get_mod() - p.val) >= get_mod()) {
val -= get_mod();
}
return *this;
}
a_mint &operator*=(const a_mint &p) noexcept {
val = (int)(1LL * val * p.val % get_mod());
return *this;
}
a_mint &operator/=(const a_mint &p) noexcept {
*this *= p.inv();
return *this;
}
a_mint operator-() const noexcept { return a_mint(-val); }
a_mint operator+(const a_mint &p) const noexcept { return a_mint(*this) += p; }
a_mint operator-(const a_mint &p) const noexcept { return a_mint(*this) -= p; }
a_mint operator*(const a_mint &p) const noexcept { return a_mint(*this) *= p; }
a_mint operator/(const a_mint &p) const noexcept { return a_mint(*this) /= p; }
a_mint& operator++() noexcept { if(val == get_mod() - 1){ val = 0; } else { val++; } return *this; }
a_mint operator++(int) noexcept { a_mint ans(*this); operator++(); return ans; }
a_mint& operator--() noexcept { if(val == 0){ val = get_mod() - 1; } else { val--; } return *this; }
a_mint operator--(int) noexcept { a_mint ans(*this); operator--(); return ans; }
constexpr inline bool operator==(const a_mint &p) const noexcept { return val == p.val; }
constexpr inline bool operator!=(const a_mint &p) const noexcept { return val != p.val; }
constexpr inline bool operator!() const noexcept { return val == 0; }
constexpr inline bool operator<=(const a_mint &p) const noexcept { return val <= p.val; }
constexpr inline bool operator>=(const a_mint &p) const noexcept { return val >= p.val; }
constexpr inline bool operator<(const a_mint &p) const noexcept { return val < p.val; }
constexpr inline bool operator>(const a_mint &p) const noexcept { return val > p.val; }
inline a_mint inv() const noexcept {
int a = val, b = get_mod(), u = 1, v = 0, t;
while(b > 0) {
t = a / b;
::std::swap(a -= t * b, b);
::std::swap(u -= t * v, v);
}
return a_mint(u);
}
inline a_mint pow(int64_t n) const noexcept {
a_mint ret(1), mul(val);
while(n > 0) {
if(n & 1) {
ret *= mul;
}
mul *= mul;
n >>= 1;
}
return ret;
}
inline friend ::std::ostream &operator<<(::std::ostream &os, const a_mint &p) noexcept { return os << p.val; }
inline friend ::std::istream &operator>>(::std::istream &is, a_mint &a) noexcept {
int64_t t;
is >> t;
a = a_mint(t);
return is;
}
};
}
#ifndef ALIAS
constexpr int MOD = 0x3b800001;
constexpr int M0D = 1e9 + 7;
#endif
typedef man::Modint<MOD> mint;
typedef man::Modint<M0D> Mint;
/**
* @brief Modint
* @docs docs/Modint.md
* @see https://atcoder.jp/contests/arc151/submissions/35526971
*/
#line 6 "main.cpp"
int main() {
now(start);
VvyLw::wa_haya_exe();
now(stop);
time(start, stop);
}
// --------------------------------------------------------------------------------------------------------------
man::Comb<mint> comb;
inline void VvyLw::solve() noexcept {
std::string n;
input(n);
const int m = std::ssize(n);
std::array<int, 10> cnt{};
for(const auto &d: n) {
cnt[d - '0']++;
}
mint ret = comb.fact(m), neg = comb.fact(m - 1);
for(const auto i: iota(0, 10)) {
ret /= comb.fact(cnt[i]);
neg /= comb.fact(i == 0 ? cnt[i] - 1 : cnt[i]);
}
// iter::sort(n);
// std::unordered_set<int> s;
// do {
// const int x = man::to_ten(n);
// if(m == std::ssize(std::to_string(x))) {
// s.emplace(x);
// }
// } while(iter::next_permutation(n).found);
// dump(std::ssize(s), s);
ret -= neg;
println(ret);
}