### Modint Constructor Examples

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Illustrates the two ways to construct a `modint` object: default constructor initializes to 0, and the parameterized constructor takes an integer value and applies the modulus.

```cpp
// (1) Default constructor: initializes to 0
modint x;

// (2) Parameterized constructor: stores y after taking mod
modint x_val(y);
```

--------------------------------

### Modint Operations Example

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Demonstrates various arithmetic operations supported by the `modint` struct, including addition, subtraction, multiplication, division, and comparisons. Note that division requires the divisor to be coprime to the modulus.

```cpp
// Unary minus
-modint_var;

// Increment/Decrement
modint_var++;
modint_var--;
++modint_var;
--modint_var;

// Arithmetic operations
modint_var1 + modint_var2;
modint_var1 - modint_var2;
modint_var1 * modint_var2;
modint_var1 / modint_var2;

// Compound assignment operations
modint_var1 += modint_var2;
modint_var1 -= modint_var2;
modint_var1 *= modint_var2;
modint_var1 /= modint_var2;

// Comparison operations
modint_var1 == modint_var2;
modint_var1 != modint_var2;

// Operations with integers (interpreted as modint(1) + x or y * modint(z))
modint x = 10;
1 + x;

modint::set_mod(11);
modint y = 10;
int z = 1234;
y * z;
```

--------------------------------

### Modint Power Function Example

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Shows how to compute modular exponentiation using the `pow` method. This is efficient for calculating large powers modulo a given number. The exponent `n` must be non-negative.

```cpp
modint result = base.pow(exponent);
```

--------------------------------

### Modint Modular Inverse Example

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Demonstrates how to calculate the modular multiplicative inverse using the `inv` method. The inverse `y` satisfies `x * y ≡ 1 (mod m)`. The value `x.val()` must be coprime to the modulus.

```cpp
modint inverse_val = x.inv();
```

--------------------------------

### Get All Connected Components

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Returns a list of all connected components in the graph, where each component is represented as a list of its vertices. The complexity is O(n).

```cpp
vector<vector<int>> d.groups()
```

--------------------------------

### get

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Retrieves the element at a specific position in the segment tree.

```APIDOC
## get

### Description
Returns the element at index `p`.

### Signature
```cpp
S seg.get(int p)
```

### Parameters
- `p` (int): The index of the element to retrieve.

### Constraints
- `0 <= p < n`

### Complexity
- O(1)
```

--------------------------------

### get

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Retrieves the value of an element at a specific position in the array.

```APIDOC
## get

```cpp
S seg.get(int p)
```

Returns `a[p]`.

**Constraints:**
- $0 \leq p < n$

**Complexity:**
- $O(\log n)$
```

--------------------------------

### Segtree Operation and Identity Element Definition

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Defines the binary operation 'op' and the identity element 'e' for the segment tree. This example uses 'min' for range minimum query.

```cpp
int op(int a, int b) {
    return min(a, b);
}

int e() {
    return (int)(1e9);
}
```

--------------------------------

### Get Edge Information

Source: https://github.com/atcoder/ac-library/blob/master/document_en/maxflow.md

Retrieves the state of a specific edge by its index or all edges in the graph.

```cpp
struct mf_graph<Cap>::edge {
    int from, to;
    Cap cap, flow;
};

mf_graph<Cap>::edge graph.get_edge(int i);
vector<mf_graph<Cap>::edge> graph.edges();
```

--------------------------------

### Z-Algorithm Implementation

Source: https://github.com/atcoder/ac-library/blob/master/document_en/string.md

Calculates the Z-array for a string or vector, where each element represents the length of the longest common prefix between the string and its suffix starting at that index.

```cpp
vector<int> z_algorithm(string s)
vector<int> z_algorithm<T>(vector<T> s)
```

--------------------------------

### Get Representative of a Component

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Returns the representative vertex of the connected component containing vertex a. Amortized complexity is O(alpha(n)).

```cpp
int d.leader(int a)
```

--------------------------------

### Get Size of a Component

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Returns the number of vertices in the connected component containing vertex a. Amortized complexity is O(alpha(n)).

```cpp
int d.size(int a)
```

--------------------------------

### Get All Edges from MinCostFlow Graph

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Returns a vector containing the internal state of all edges in the graph, ordered as they were added. Complexity: O(m), where m is the number of added edges.

```cpp
vector<mcf_graph<Cap, Cost>::edge> graph.edges();
```

--------------------------------

### Get Satisfying Assignment

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Returns a truth assignment that satisfies all clauses from the last call to satisfiable(). If called before satisfiable() or if satisfiable() returned false, the result is undefined. Complexity: O(n).

```cpp
vector<bool> ts.answer()
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Initializes a 2-SAT solver with a specified number of variables.

```APIDOC
## Constructor

### Description
It creates a 2-SAT instance with `n` variables and no clauses.

### Signature
```cpp
two_sat ts(int n)
```

### Parameters
- **n** (int) - The number of variables. Constraints: $0 \leq n \leq 10^8$.

### Complexity
$O(n)$
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/fenwicktree.md

Initializes a Fenwick Tree of a given size. All elements are set to 0.

```APIDOC
## Constructor

```cpp
fenwick_tree<T> fw(int n)
```

- It creates an array $a_0, a_1, \cdots, a_{n-1}$ of length $n$. All the elements are initialized to $0$.

**Constraints**

- `T` is `int`, `uint`, `ll`, `ull`, or `modint`
- $0 \leq n \leq 10^8$

**Complexity**

- $O(n)$
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Initializes a directed graph with a specified number of vertices and no edges. Cap and Cost are the types for capacity and cost, respectively.

```APIDOC
## Constructor

```cpp
mcf_graph<Cap, Cost> graph(int n);
```

### Description
It creates a directed graph with $n$ vertices and $0$ edges. `Cap` and `Cost` are the type of the capacity and the cost, respectively.

### Constraints

- $0 

### Complexity

- $O(n)$
```

--------------------------------

### Initialize SCC Graph with Default Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/appendix.md

Shows how to declare and initialize an `scc_graph` using its default constructor. Accessing members or calling functions before assignment is undefined behavior.

```cpp
#include <atcoder/scc>;
using namespace atcoder;

int main() {
    int n;
    scanf("%d", &n);
    scc_graph g(n); // create the graph with n vertices
    return 0;
}
```

```cpp
#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    return 0;
}
```

```cpp
#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    g = scc_graph(10);
    return 0;
}
```

--------------------------------

### Initialize 2-SAT Solver

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Creates a 2-SAT instance with n variables and no clauses. Constraints: 0 <= n <= 10^8. Complexity: O(n).

```cpp
two_sat ts(int n)
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/scc.md

Creates a directed graph with n vertices and 0 edges.

```APIDOC
## Constructor

```cpp
scc_graph graph(int n)
```

It creates a directed graph with $n$ vertices and $0$ edges.

**Constraints**

- $0 \leq n \leq 10^8$

**Complexity**

- $O(n)$
```

--------------------------------

### Get Specific Edge from MinCostFlow Graph

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Retrieves the internal state of a specific edge by its index. Constraints: 0 <= i < m. Complexity: O(1).

```cpp
mcf_graph<Cap, Cost>::edge graph.get_edge(int i);
```

--------------------------------

### Get Element from Lazy Segtree

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Retrieves the value of an element at a specific position from the lazy segment tree. This operation has a logarithmic time complexity.

```cpp
S seg.get(int p);
```

--------------------------------

### z_algorithm

Source: https://github.com/atcoder/ac-library/blob/master/document_en/string.md

Computes the Z-array for a given string or vector. The Z-array stores the length of the longest common prefix between the string itself and its suffixes starting at each index.

```APIDOC
## z_algorithm

### Description
Computes the Z-array for a string `s` of length `n`. The Z-array has length `n`, where the `i`-th element is the length of the LCP of `s[0..n)` and `s[i..n)`.

### Method Signatures

- `vector<int> z_algorithm(string s)`
- `vector<int> z_algorithm<T>(vector<T> s)`

### Constraints

- $0 \leq n \leq 10^8$
- For `z_algorithm<T>(vector<T> s)`, `T` can be `int`, `uint`, `ll`, or `ull`.

### Complexity

- $O(n)$
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Initializes a DSU structure with a specified number of vertices. Creates an undirected graph with n vertices and 0 edges.

```APIDOC
## Constructor

```cpp
dsu d(int n)
```

### Description
Initializes a DSU structure with `n` vertices and no edges.

### Parameters
- **n** (int) - The number of vertices in the graph. Constraints: $0 \leq n \leq 10^8$.

### Complexity
- $O(n)$
```

--------------------------------

### Add Benchmark Subdirectory

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Includes the benchmark subdirectory for building benchmark-related targets.

```cmake
add_subdirectory(benchmark)
```

--------------------------------

### Initialize SCC graph with n vertices

Source: https://github.com/atcoder/ac-library/blob/master/document_en/scc.md

Creates a directed graph with n vertices and no edges. Constraints: 0 <= n <= 10^8. Complexity: O(n).

```cpp
scc_graph graph(int n)
```

--------------------------------

### DSU Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Initializes a DSU structure with n vertices and no edges. The complexity is O(n).

```cpp
dsu d(int n)
```

--------------------------------

### Constructor for MinCostFlow Graph

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Initializes a directed graph with n vertices. Cap and Cost specify the data types for capacity and cost. Constraints: 0 <= n <= 10^8. Complexity: O(n).

```cpp
mcf_graph<Cap, Cost> graph(int n);
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Initializes a segment tree. It can be initialized with a size and default values or with an existing vector.

```APIDOC
## Constructor

### Description
Initializes a segment tree. It can be initialized with a size and default values or with an existing vector.

### Signature
```cpp
(1) segtree<S, op, e> seg(int n)
(2) segtree<S, op, e> seg(vector<S> v)
```

### Parameters
- `n` (int): The size of the array to be created. Elements are initialized to `e()`.
- `v` (vector<S>): The vector to initialize the segment tree with.
- `S`: The type of elements stored in the segment tree.
- `op`: A function `S op(S a, S b)` representing the binary operation of the monoid.
- `e`: A function `S e()` returning the identity element of the monoid.

### Complexity
- O(n)
```

--------------------------------

### Project and Minimum CMake Version

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Defines the project name and the minimum required CMake version for the build.

```cmake
project(ACLibrary)

cmake_minimum_required(VERSION 3.17)
```

--------------------------------

### Include Directories

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Adds include paths for the current directory and its parent.

```cmake
include_directories(.)
include_directories(../../)
```

--------------------------------

### Google Test Path Configuration

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Sets the path to the Google Test framework source directory.

```cmake
set(GOOGLETEST_PATH "${CMAKE_CURRENT_SOURCE_DIR}/../unittest/googletest")
```

--------------------------------

### all_prod

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Calculates the product of all elements in the array.

```APIDOC
## all_prod

```cpp
S seg.all_prod()
```

Returns `op(a[0], ..., a[n - 1])`. Returns `e()` if $n = 0$.

**Complexity:**
- $O(1)$
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/maxflow.md

Initializes a MaxFlow graph with a specified number of vertices. The capacity type can be int or ll.

```APIDOC
## Constructor

```cpp
mf_graph<Cap> graph(int n)
```

It creates a graph of `n` vertices and $0$ edges. `Cap` is the type of the capacity.

**Constraints:**

- $0 

**Complexity:**

- $O(n)$
```

--------------------------------

### Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Initializes a lazy segment tree. It can be initialized with a size or a vector of initial values.

```APIDOC
## Constructor

```cpp
(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<S> v);
```

- (1): Creates an array `a` of length `n` with elements initialized to `e()`.
- (2): Creates an array `a` of length `n = v.size()`, initialized to `v`.

**Constraints:**
- $0 \leq n \leq 10^8$

**Complexity:**
- $O(n)$
```

--------------------------------

### Segtree Constructor with Vector

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Initializes a segment tree with elements from a given vector v. The size of the tree will be v.size().

```cpp
segtree<int, op, e> seg(vector<int> v);
```

--------------------------------

### Fenwick Tree Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/fenwicktree.md

Initializes a Fenwick Tree of a given size with all elements set to 0. The size 'n' can be up to 10^8. Complexity is O(n).

```cpp
fenwick_tree<T> fw(int n)
```

--------------------------------

### Segtree Constructor with Size

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Initializes a segment tree of a given size n. All elements are initialized to the identity element e().

```cpp
segtree<int, op, e> seg(10);
```

--------------------------------

### all_prod

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Calculates the product of all elements in the segment tree.

```APIDOC
## all_prod

### Description
Returns the product of all elements in the segment tree. Returns `e()` if the tree is empty (`n == 0`).

### Signature
```cpp
S seg.all_prod()
```

### Complexity
- O(1)
```

--------------------------------

### Constructor for MaxFlow Graph

Source: https://github.com/atcoder/ac-library/blob/master/document_en/maxflow.md

Initializes a MaxFlow graph with a specified number of vertices. 'Cap' can be 'int' or 'll'.

```cpp
mf_graph<Cap> graph(int n);
```

--------------------------------

### Create Convolution Executable

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Defines an executable target named 'Convolution' and links it with the benchmark library.

```cmake
add_executable(Convolution convolution.cpp)
target_link_libraries(Convolution benchmark::benchmark)
```

--------------------------------

### prod

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Calculates the product of elements in a given range [l, r).

```APIDOC
## prod

```cpp
S seg.prod(int l, int r)
```

Returns `op(a[l], ..., a[r - 1])`. Returns `e()` if $l = r$.

**Constraints:**
- $0 \leq l \leq r \leq n$

**Complexity:**
- $O(\log n)$
```

--------------------------------

### add

Source: https://github.com/atcoder/ac-library/blob/master/document_en/fenwicktree.md

Adds a value `x` to the element at index `p`.

```APIDOC
## add

```cpp
void fw.add(int p, T x)
```

It processes `a[p] += x`.

**Constraints**

- $0 \leq p < n$

**Complexity**

- $O(\log n)$
```

--------------------------------

### All Product Query in Lazy Segtree

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Calculates the product of all elements in the lazy segment tree. Returns the identity element if the tree is empty.

```cpp
S seg.all_prod();
```

--------------------------------

### Modint Usage with Dynamic Modulus

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Shows how to use `modint` with a dynamically set modulus using `modint::set_mod(mod)`. This is useful when the modulus is not known at compile time. Ensure `set_mod` is called before any other operations.

```cpp
#include <atcoder/modint>
#include <iostream>

using namespace std;
using namespace atcoder;

using mint = modint;
// or: typedef modint mint;

int main() {
    // print sum of array (input mod)
    int n, mod;
    cin >> n >> mod;
    mint::set_mod(mod);
    mint sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum.val() << endl;
}
```

--------------------------------

### apply

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Applies a mapping function to elements in a range.

```APIDOC
## apply

```cpp
(1) void seg.apply(int p, F f)
(2) void seg.apply(int l, int r, F f)
```

- (1): Applies `a[p] = f(a[p])`.
- (2): Applies `a[i] = f(a[i])` for all `i = l..r-1`.

**Constraints:**
- (1) $0 \leq p < n$
- (2) $0 \leq l \leq r \leq n$

**Complexity:**
- $O(\log n)$
```

--------------------------------

### Use Convolution Function with Default Modulo

Source: https://github.com/atcoder/ac-library/blob/master/document_en/appendix.md

Demonstrates calling the `convolution` function without explicitly specifying the modulo parameter, utilizing its default value of 998244353. An alternative call shows how to specify a different modulo.

```cpp
vector<long long> c = convolution(a, b);
vector<long long> c = convolution<924844033>(a, b);
```

--------------------------------

### Modular Exponentiation (pow_mod)

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Calculates (x^n) mod m. Constraints: 0 <= n, 1 <= m. Complexity: O(log n).

```cpp
ll pow_mod(ll x, ll n, int m)
```

--------------------------------

### Using dynamic_modint for Multiple Moduli

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Demonstrates how to use `dynamic_modint<I>` to manage multiple distinct moduli, where `I` is an identifier. `modint` is an alias for `dynamic_modint<-1>`.

```cpp
using mint0 = dynamic_modint<0>;
using mint1 = dynamic_modint<1>;

// Alias for dynamic_modint with an unspecified modulus
using modint = dynamic_modint<-1>;
```

--------------------------------

### Chinese Remainder Theorem (crt)

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Solves a system of modular equations x = r[i] (mod m[i]). Returns (y, z) such that x = y (mod z), where z is the LCM of m[i]. Returns (0, 0) if no solution exists. Handles n=0 by returning (0, 1). Constraints: |r| = |m|, 1 <= m[i], LCM fits in ll. Complexity: O(n log(lcm(m[i]))).

```cpp
pair<ll, ll> crt(vector<ll> r, vector<ll> m)
```

--------------------------------

### Modular Inverse (inv_mod)

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Finds an integer y such that (x*y) is congruent to 1 mod m, where 0 <= y < m. Constraints: gcd(x, m) = 1, 1 <= m. Complexity: O(log m).

```cpp
ll inv_mod(ll x, ll m)
```

--------------------------------

### Compute Strongly Connected Components (SCC)

Source: https://github.com/atcoder/ac-library/blob/master/document_en/scc.md

Returns a list of vertices for each SCC, sorted topologically. Complexity: O(n + m), where m is the number of edges.

```cpp
vector<vector<int>> graph.scc()
```

--------------------------------

### inv_mod

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Calculates the modular multiplicative inverse of x modulo m. Constraints: gcd(x, m) = 1, 1 <= m. Complexity: O(log m).

```APIDOC
## inv_mod

### Description
Returns an integer $y$ such that $0 
xy 
1 

### Signature
```cpp
ll inv_mod(ll x, ll m)
```

### Constraints
- $\gcd(x, m) = 1$
- $1 

### Complexity
- $O(

```

--------------------------------

### Using static_modint for Fixed Moduli

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Shows how to define a modint type with a fixed modulus at compile time using `static_modint<M>`. Aliases like `modint998244353` are provided for common moduli.

```cpp
using mint = static_modint<1000000009>;

// Aliases for common moduli
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
```

--------------------------------

### groups

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Returns a list of all connected components in the graph.

```APIDOC
## groups

```cpp
vector<vector<int>> d.groups()
```

### Description
Divides the graph into connected components and returns a list of these components. Each component is represented as a list of its vertices. The order of components and vertices within components is undefined.

### Complexity
- $O(n)$
```

--------------------------------

### Floor Sum Calculation (floor_sum)

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Calculates the sum of floor((a*i + b) / m) for i from 0 to n-1. Returns the answer modulo 2^64 if overflow occurs. Constraints: 0 <= n < 2^32, 1 <= m < 2^32. Complexity: O(log m).

```cpp
ll floor_sum(ll n, ll m, ll a, ll b)
```

--------------------------------

### C++ Standard and Extensions

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Sets the C++ standard to 14 if not already defined and disables C++ extensions.

```cmake
if(NOT "${CMAKE_CXX_STANDARD}")
  set(CMAKE_CXX_STANDARD 14)
endif()
set(CMAKE_CXX_EXTENSIONS OFF)
```

--------------------------------

### Min Left Query in Lazy Segtree

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Performs a binary search on the segment tree to find the minimum left index 'l' such that a condition 'g' holds for the range [l, r). Requires 'g' to be monotone and satisfy g(e()) = true.

```cpp
(1) int seg.min_left<g>(int r)
(2) int seg.min_left<G>(int r, G g)
```

--------------------------------

### Calculate Min Cost Max Flow

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Calculates the maximum flow and its minimum cost from source s to target t. Can optionally limit the total flow. Constraints: s != t, 0 <= s, t < n. Complexity: Same as min_cost_slope.

```cpp
pair<Cap, Cost> graph.flow(int s, int t);
```

```cpp
pair<Cap, Cost> graph.flow(int s, int t, Cap flow_limit);
```

--------------------------------

### Calculate Min Cost Flow Slope

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Returns the piecewise linear cost function g(x) for s-t flow x, represented by changepoints. The function g(x) is the minimum cost for a flow of exactly x. Constraints: s != t, 0 <= s, t < n. Complexity: O(F * (n + m) * log(n + m)).

```cpp
vector<pair<Cap, Cost>> graph.slope(int s, int t);
```

```cpp
vector<pair<Cap, Cost>> graph.slope(int s, int t, Cap flow_limit);
```

--------------------------------

### Basic Modint Usage with Fixed Modulus

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Demonstrates how to use `modint998244353` for calculating the sum of array elements modulo 998244353. Include `<atcoder/modint>` and use `using namespace atcoder;`.

```cpp
#include <atcoder/modint>
#include <iostream>

using namespace std;
using namespace atcoder;

using mint = modint998244353;
// or: typedef modint998244353 mint;

int main() {
    // print sum of array (mod 998244353)
    int n;
    cin >> n;
    mint sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum.val() << endl;
}
```

--------------------------------

### Segtree Min Left Binary Search

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Finds the smallest index l such that the product of elements in the range [l, r) satisfies a given condition f. Requires f to be monotone and f(e()) to be true. Time complexity is O(log n).

```cpp
int seg.min_left<f>(int r);
```

```cpp
int seg.min_left<F>(int r, F f);
```

--------------------------------

### crt

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Solves a system of modular equations using the Chinese Remainder Theorem. Returns (y, z) such that x = y (mod z), where z is the LCM of the moduli. If no solution exists, returns (0, 0). If n=0, returns (0, 1). Constraints: |r| = |m|, 1 <= m[i], lcm(m[i]) fits in ll. Complexity: O(n log(lcm(m[i]))).

```APIDOC
## crt

### Description
Solves the modular equation system $x 
 r[i] 
 m[i], \forall i 
 \lbrace 0,1,\cdots, n - 1 
\rbrace$. If there is no solution, it returns $(0, 0)$. Otherwise, all the solutions can be written as the form $x 
 y 
 z$, using integers $y, z$ ($0 
 y < z = \mathrm{lcm}(m[i]))$. It returns this $(y, z)$ as a pair. If $n=0$, it returns $(0, 1)$.

### Signature
```cpp
pair<ll, ll> crt(vector<ll> r, vector<ll> m)
```

### Constraints
- $|r| = |m|$
- $1 
 m[i]$
- $\mathrm{lcm}(m[i])$ is in `ll`.

### Complexity
- $O(n 
{\mathrm{lcm}(m[i])})$

```

--------------------------------

### Range Product Query in Lazy Segtree

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Calculates the product of elements within a specified range [l, r) using the monoid operation. Returns the identity element if the range is empty.

```cpp
S seg.prod(int l, int r);
```

--------------------------------

### scc

Source: https://github.com/atcoder/ac-library/blob/master/document_en/scc.md

Returns the list of vertices that form the strongly connected components, sorted in topological order.

```APIDOC
## scc

```cpp
vector<vector<int>> graph.scc()
```

It returns the list of the "list of the vertices" that satisfies the following.

- Each vertex is in exactly one "list of the vertices".
- Each "list of the vertices" corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined.
- The list of "list of the vertices" are sorted in topological order, i.e., for two vertices $u, v$ in different strongly connected components, if there is a directed path from $u$ to $v$, the list containing $u$ appears earlier than the list containing $v$.

**Complexity**

- $O(n + m)$, where $m$ is the number of added edges.
```

--------------------------------

### size

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Returns the size of the connected component that contains a given vertex.

```APIDOC
## size

```cpp
int d.size(int a)
```

### Description
Returns the number of vertices in the connected component that contains vertex `a`.

### Parameters
- **a** (int) - The vertex whose component size is to be found. Constraints: $0 \leq a < n$.

### Complexity
- $O(\alpha(n))$ amortized
```

--------------------------------

### set

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Sets the value of an element at a specific position in the array.

```APIDOC
## set

```cpp
void seg.set(int p, S x)
```

Sets `a[p] = x`.

**Constraints:**
- $0 \leq p < n$

**Complexity:**
- $O(\log n)$
```

--------------------------------

### Calculate Suffix Array using Template Function

Source: https://github.com/atcoder/ac-library/blob/master/document_en/appendix.md

Demonstrates the correct usage of the `suffix_array` template function with a `vector<int>`. Avoid specifying the template argument explicitly for integral types.

```cpp
vector<int> sa = suffix_array(v);
// vector<int> sa = suffix_array<int>(v); : wrong usage
```

--------------------------------

### min_cost_max_flow

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Calculates the minimum cost flow between a source and a sink. It can augment flow as much as possible or up to a specified limit.

```APIDOC
## min_cost_max_flow

```cpp
(1) pair<Cap, Cost> graph.flow(int s, int t);
(2) pair<Cap, Cost> graph.flow(int s, int t, Cap flow_limit);
```

### Description
- It augments the flow from $s$ to $t$ as much as possible. It returns the amount of the flow and the cost.
- (1) It augments the $s-t$ flow as much as possible.
- (2) It augments the $s-t$ flow as much as possible, until reaching the amount of `flow_limit`.

### Constraints

- same as `min_cost_slope`.

### Complexity

- same as `min_cost_slope`.
```

--------------------------------

### min_left

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Finds the smallest left boundary `l` such that a condition `g` holds for the range [l, r).

```APIDOC
## min_left

```cpp
(1) int seg.min_left<g>(int r)
(2) int seg.min_left<G>(int r, G g)
```

Returns an index `l` such that `l = r` or `g(op(a[l], ..., a[r - 1])) = true`, and `l = 0` or `g(op(a[l - 1], ..., a[r - 1])) = false`.

**Constraints:**
- `g` has no side effects.
- `g(e()) = true`
- $0 \leq r \leq n$

**Complexity:**
- $O(\log n)$
```

--------------------------------

### Modint Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Constructs a modint object. The default constructor initializes with 0. The parameterized constructor initializes with a value `y` after taking the modulus.

```APIDOC
## Constructor

```cpp
(1) modint x()
(2) modint x<T>(T y)
```

- (1) Default constructor: Initializes the modint to 0.
- (2) Parameterized constructor: Initializes the modint with the value `y` after applying the modulus. `T` can be an integer type like `int`, `char`, `ull`, `bool`, etc.
```

--------------------------------

### Suffix Array Construction

Source: https://github.com/atcoder/ac-library/blob/master/document_en/string.md

Constructs the suffix array for a given string or vector. Supports different types and an upper bound for integer vectors.

```cpp
vector<int> suffix_array(string s)
vector<int> suffix_array<T>(vector<T> s)
vector<int> suffix_array(vector<int> s, int upper)
```

--------------------------------

### answer

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Retrieves a satisfying truth assignment.

```APIDOC
## answer

### Description
Returns a truth assignment that satisfies all clauses, based on the last call to `satisfiable()`.
If `satisfiable()` has not been called, or if it returned `false`, this method returns a vector of length `n` with undefined elements.

### Signature
```cpp
vector<bool> ts.answer()
```

### Returns
A `vector<bool>` representing a satisfying truth assignment. The size of the vector is `n`.

### Complexity
$O(n)$
```

--------------------------------

### Lazy Segtree Constructor

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Initializes a lazy segment tree. Use the first overload for an empty tree of size n, and the second for a tree initialized with values from a vector.

```cpp
lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<S> v);
```

--------------------------------

### floor_sum

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Calculates the sum of floor values: sum(floor((a*i + b) / m)) for i from 0 to n-1. Returns the answer modulo 2^64 if overflowed. Constraints: 0 <= n < 2^32, 1 <= m < 2^32. Complexity: O(log m).

```APIDOC
## floor_sum

### Description
Calculates $\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor$. It returns the answer in $\bmod 2^{\mathrm{64}}$, if overflowed.

### Signature
```cpp
ll floor_sum(ll n, ll m, ll a, ll b)
```

### Constraints
- $0 
 n 
 2^{32}$
- $1 
 m 
 2^{32}$

### Complexity
- $O(

```

--------------------------------

### LCP Array Construction

Source: https://github.com/atcoder/ac-library/blob/master/document_en/string.md

Computes the Longest Common Prefix (LCP) array given a string and its suffix array. Supports different element types for the string.

```cpp
vector<int> lcp_array(string s, vector<int> sa)
vector<int> lcp_array<T>(vector<T> s, vector<int> sa)
```

--------------------------------

### Apply Map to Element/Range in Lazy Segtree

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Applies a mapping function to an element at a specific position or to all elements within a range. This operation is lazy and has logarithmic time complexity.

```cpp
(1) void seg.apply(int p, F f)
(2) void seg.apply(int l, int r, F f)
```

--------------------------------

### Max Right Query in Lazy Segtree

Source: https://github.com/atcoder/ac-library/blob/master/document_en/lazysegtree.md

Performs a binary search on the segment tree to find the maximum right index 'r' such that a condition 'g' holds for the range [l, r). Requires 'g' to be monotone and satisfy g(e()) = true.

```cpp
(1) int seg.max_right<g>(int l)
(2) int seg.max_right<G>(int l, G g)
```

--------------------------------

### Compiler Warning Flags

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Configures aggressive compiler warnings for better code quality and error detection.

```cmake
add_compile_options(-Wall -Wextra -Wshadow -Wconversion -Wno-sign-conversion -Werror)
```

--------------------------------

### Modint Operations

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Supports standard arithmetic and comparison operations for modint objects, including negation, increment/decrement, addition, subtraction, multiplication, division, and equality checks.

```APIDOC
## Operations

The following operations are supported:

```cpp
-modint;

modint++;
modint--;
++modint;
--modint;

modint + modint;
modint - modint;
modint * modint;
modint / modint;

modint += modint;
modint -= modint;
modint *= modint;
modint /= modint;

modint == modint;
modint != modint;
```

Integer literals can also be used in operations, e.g., `1 + x` is interpreted as `modint(1) + x`, and `y * z` where `y` is a modint and `z` is an integer is interpreted as `y * modint(z)`.

**Constraints**:
- For division `a / b` (or `a /= b`), `gcd(b.val(), mod)` must be 1.

**Complexity**:
- $O(1)$ for all operations except division.
- $O(\log \mathrm{mod})$ for division.
```

--------------------------------

### pow_mod

Source: https://github.com/atcoder/ac-library/blob/master/document_en/math.md

Calculates (x^n) mod m. Constraints: 0 <= n, 1 <= m. Complexity: O(log n).

```APIDOC
## pow_mod

### Description
Calculates $x^n mod m$.

### Signature
```cpp
ll pow_mod(ll x, ll n, int m)
```

### Constraints
- $0 
- $1 

### Complexity
- $O(

```

--------------------------------

### Modint Raw Function for Performance

Source: https://github.com/atcoder/ac-library/blob/master/document_en/modint.md

Illustrates the use of `modint::raw(i)` to create a modint from an integer `i` without applying the modulus. This can speed up operations when it's guaranteed that `i` is already less than the modulus. Behavior is undefined if `i >= mod`.

```cpp
#include <atcoder/modint>
#include <iostream>

using namespace std;
using namespace atcoder;

int main() {
    modint::set_mod(1000000007);
    modint a = 1;
    for (int i = 1; i < 100000; i++) {
        // Using raw for potential performance gain when i < mod
        a += modint::raw(i);
    }
}
```

--------------------------------

### Check Satisfiability

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Determines if there exists a truth assignment that satisfies all added clauses. Can be called multiple times. Complexity: O(n + m), where m is the number of clauses.

```cpp
bool ts.satisfiable()
```

--------------------------------

### add_clause

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Adds a clause to the 2-SAT problem.

```APIDOC
## add_clause

### Description
Adds a clause of the form $(x_i = f) \lor (x_j = g)$ to the 2-SAT problem.

### Signature
```cpp
void ts.add_clause(int i, bool f, int j, bool g)
```

### Parameters
- **i** (int) - The index of the first variable. Constraints: $0 \leq i \lt n$.
- **f** (bool) - The truth value assigned to variable $x_i$.
- **j** (int) - The index of the second variable. Constraints: $0 \leq j \lt n$.
- **g** (bool) - The truth value assigned to variable $x_j$.

### Complexity
$O(1)$ amortized
```

--------------------------------

### Calculate Maximum Flow

Source: https://github.com/atcoder/ac-library/blob/master/document_en/maxflow.md

Calculates the maximum flow from source 's' to sink 't'. Can optionally take a flow limit.

```cpp
Cap graph.flow(int s, int t);
Cap graph.flow(int s, int t, Cap flow_limit);
```

--------------------------------

### set

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Updates an element at a specific position in the segment tree.

```APIDOC
## set

### Description
Assigns a new value `x` to the element at index `p`.

### Signature
```cpp
void seg.set(int p, S x)
```

### Parameters
- `p` (int): The index of the element to update.
- `x` (S): The new value to set.

### Constraints
- `0 <= p < n`

### Complexity
- O(log n)
```

--------------------------------

### min_cost_slope

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Returns the minimum cost flow as a list of changepoints, representing the piecewise linear cost function.

```APIDOC
## min_cost_slope

```cpp
vector<pair<Cap, Cost>> graph.slope(int s, int t);
vector<pair<Cap, Cost>> graph.slope(int s, int t, Cap flow_limit);
```

### Description
Let $g$ be a function such that $g(x)$ is the cost of the minimum cost $s-t$ flow when the amount of the flow is exactly $x$. $g$ is known to be piecewise linear. It returns $g$ as the list of the changepoints, that satisfies the followings.

- The first element of the list is $(0, 0)$.
- `.first` is strictly increasing and `.second` is non-decreasing.
- No three changepoints are on the same line.
- (1) The last element of the list is $(x, g(x))$, where $x$ is the maximum amount of the $s-t$ flow.
- (2) The last element of the list is $(y, g(y))$, where $y = 

### Constraints

Let $x$ be the maximum cost among all edges.

- $s 
- $0 
- You can't call `min_cost_slope` or `min_cost_max_flow` multiple times.
- The total amount of the flow is in `Cap`.
- The total cost of the flow is in `Cost`.
- (Cost : `int`): $0 
- (Cost : `ll`): $0 

### Complexity

- $O(F (n + m) 

```

--------------------------------

### sum

Source: https://github.com/atcoder/ac-library/blob/master/document_en/fenwicktree.md

Calculates the sum of elements in the interval [l, r).

```APIDOC
## sum

```cpp
T fw.sum(int l, int r)
```

It returns `a[l] + a[l + 1] + ... + a[r - 1]`.
If `T` is integer type(`int`, `uint`, `ll`, or `ull`), it returns the answer in $\bmod 2^{\mathrm{bit}}$, if overflowed.

**Constraints**

- $0 \leq l \leq r \leq n$

**Complexity**

- $O(\log n)$
```

--------------------------------

### min_left

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Finds the smallest index `l` such that a condition `f` holds for the range `[l, r)`.

```APIDOC
## min_left

### Description
Performs a binary search on the segment tree to find the smallest index `l` such that the condition `f` is true for the aggregated value of the range `[l, r)`. If `f` is monotone, this finds the minimum `l` for which `f` holds.

### Signature
```cpp
(1) int seg.min_left<f>(int r)
(2) int seg.min_left<F>(int r, F f)
```

### Parameters
- `r` (int): The right boundary of the search range.
- `f` (function or function object): A predicate function that takes an aggregated value of a range and returns a boolean.

### Constraints
- `f` must be side-effect free.
- `f(e())` must be true.
- `0 <= r <= n`

### Complexity
- O(log n)
```

--------------------------------

### Convolution with Modulo

Source: https://github.com/atcoder/ac-library/blob/master/document_en/convolution.md

Calculates the convolution of two vectors modulo m. Returns an empty vector if either input vector is empty. Requires m to be a prime number and satisfy specific conditions related to the input sizes.

```cpp
vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)
```

```cpp
vector<static_modint<m>> convolution<int m>(vector<static_modint<m>> a, vector<static_modint<m>> b)
```

--------------------------------

### Add Edge to MinCostFlow Graph

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Adds a directed edge with specified capacity and cost. Returns an index for the added edge. Constraints: 0 <= from, to < n, 0 <= cap, cost. Complexity: O(1) amortized.

```cpp
int graph.add_edge(int from, int to, Cap cap, Cost cost);
```

--------------------------------

### satisfiable

Source: https://github.com/atcoder/ac-library/blob/master/document_en/twosat.md

Checks if the current set of clauses is satisfiable.

```APIDOC
## satisfiable

### Description
Determines if there exists a truth assignment that satisfies all added clauses. This method can be called multiple times.

### Signature
```cpp
bool ts.satisfiable()
```

### Returns
- `true` if a satisfying assignment exists.
- `false` otherwise.

### Complexity
$O(n + m)$, where $m$ is the number of added clauses.
```

--------------------------------

### Define and Use Edge Type for Max Flow Graph

Source: https://github.com/atcoder/ac-library/blob/master/document_en/appendix.md

Illustrates how to declare variables of the `mf_graph<Cap>::edge` type, which represents edges in a maximum flow graph. This type can be used similarly to built-in types like `int` or `string`.

```cpp
vector<mf_graph<int>::edge> v;
mf_graph<int>::edge e;
```

--------------------------------

### same

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Checks if two vertices belong to the same connected component.

```APIDOC
## same

```cpp
bool d.same(int a, int b)
```

### Description
Returns `true` if vertices `a` and `b` are in the same connected component, `false` otherwise.

### Parameters
- **a** (int) - The first vertex. Constraints: $0 \leq a < n$.
- **b** (int) - The second vertex. Constraints: $0 \leq b < n$.

### Complexity
- $O(\alpha(n))$ amortized
```

--------------------------------

### leader

Source: https://github.com/atcoder/ac-library/blob/master/document_en/dsu.md

Retrieves the representative (leader) of the connected component containing a given vertex.

```APIDOC
## leader

```cpp
int d.leader(int a)
```

### Description
Returns the representative (leader) of the connected component to which vertex `a` belongs.

### Parameters
- **a** (int) - The vertex whose component leader is to be found. Constraints: $0 \leq a < n$.

### Complexity
- $O(\alpha(n))$ amortized
```

--------------------------------

### Edge Structure for MinCostFlow

Source: https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md

Defines the structure for an edge in the MinCostFlow graph, including its endpoints, capacity, current flow, and cost.

```cpp
struct edge<Cap, Cost> {
    int from, to;
    Cap cap, flow;
    Cost cost;
};
```

--------------------------------

### Segtree Max Right Binary Search

Source: https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md

Finds the largest index r such that the product of elements in the range [l, r) satisfies a given condition f. Requires f to be monotone and f(e()) to be true. Time complexity is O(log n).

```cpp
int seg.max_right<f>(int l);
```

```cpp
int seg.max_right<F>(int l, F f);
```

--------------------------------

### Set CMake Policy CMP0048

Source: https://github.com/atcoder/ac-library/blob/master/test/benchmark/CMakeLists.txt

Ensures consistent behavior for the CMP0048 policy, which affects how targets are found.

```cmake
cmake_policy(SET CMP0048 NEW)
```

--------------------------------

### flow

Source: https://github.com/atcoder/ac-library/blob/master/document_en/maxflow.md

Calculates the maximum flow between a source and a sink, optionally with a flow limit.

```APIDOC
## flow

```cpp
(1) Cap graph.flow(int s, int t);
(2) Cap graph.flow(int s, int t, Cap flow_limit);
```

- (1) It augments the flow from $s$ to $t$ as much as possible. It returns the amount of the flow augmented.
- (2) It augments the flow from $s$ to $t$ as much as possible, until reaching the amount of `flow_limit`. It returns the amount of the flow augmented.
- You may call it multiple times. See [Appendix](./appendix.html) for further details.

**Constraints:**

- $s 
eq t$
- $0 

**Complexity:**

- $O((n + m) 
- $O(n^2 m)$ (general), or
- $O(F(n + m))$, where $F$ is the returned value

where $m$ is the number of added edges.
```