∑MathAdvanced

Burnside's Lemma

Key Points

•
Burnside's Lemma says the number of distinct objects up to a symmetry group equals the average number of objects fixed by each symmetry.
•
For colorings of n positions with k colors under a permutation g, the fixed colorings equal k raised to the number of cycles in g.
•
Counting necklaces under rotation $C_{n}$ gives $\frac{1}{n}$ times the sum over r of $k^{g c d (n, r)}$ , which can be optimized using Euler’s totient function.
•
Counting bracelets (rotations + reflections, the dihedral group $D_{n}$ ) adds reflection cases that depend on whether n is odd or even.
•
Pólya’s Enumeration Theorem generalizes Burnside by packaging cycle counts into a cycle index polynomial.
•
In practice, you implement Burnside by iterating group elements, computing cycle decompositions, and summing $k^{#cycles}$ .
•
Using modular arithmetic, divide by |G| via a modular inverse when counting under a prime modulus.
•
Common pitfalls include miscounting reflection fixes, confusing gcd with cycle counts, and forgetting to average over all group elements.

Prerequisites

→Greatest common divisor (GCD) — Rotation cycle counts for C_n use gcd(n, r) and the divisor–totient identity.
→Euler’s totient function — Optimizing the rotation sum requires grouping by totients over divisors.
→Permutations and cycle decomposition — Fixed colorings equal k^{#cycles(g)}, so you must compute cycle counts.
→Fast modular exponentiation — Efficiently compute k^e modulo a prime for large exponents.
→Basic group theory — Understanding group actions, orbits, stabilizers, and the structure of cyclic/dihedral groups.
→Modular arithmetic and inverses — Required to divide by |G| under a prime modulus in code.
→Trial division factorization — Needed for computing φ(d) when using the divisor-sum optimization.

Detailed Explanation

Tap terms for definitions

01Overview

Burnside’s Lemma (also known as the Cauchy–Frobenius Lemma) is a counting tool in combinatorics that helps us count how many distinct objects exist when we treat objects related by symmetries as the same. Imagine you want to count colored patterns on a bracelet, but you consider two patterns identical if one can be rotated or flipped to match the other. Direct counting tends to overcount because many different raw descriptions actually represent the same pattern under symmetry. Burnside’s Lemma resolves this by turning the problem into an average: for each symmetry in the group, count how many objects are unchanged (fixed) by that symmetry, then average these counts over the whole group. The result is exactly the number of distinct equivalence classes (orbits) under the group action.

02Intuition & Analogies

Think of a group of friends passing around a decorated circular cake. Each friend performs a symmetry move: rotate the cake by some angle or reflect it in a mirror. Ask: for a given move, how many cake decorations look exactly the same after the move? If few decorations survive a complicated move, that move contributes a small number to the average; if many decorations survive a simple move (like identity), it contributes a large number. Burnside tells us that if you average these “survival counts” over the full set of moves, you obtain the number of fundamentally different decoration designs up to those moves. Another analogy: imagine taking photos of a patterned tile from different orientations. Every orientation is a group action. For each orientation, count how many designs would look indistinguishable in the photo after reorienting; then average over all orientations. Why does averaging work? Symmetry creates equivalence classes (“orbits”). Each object appears as fixed by exactly as many symmetries as the size of its stabilizer; when you sum over symmetries and swap summations, every object contributes precisely its stabilizer size, and by the orbit–stabilizer relationship, that balances to an exact count of orbits. The magic is simply fair averaging across all symmetries.

03Formal Definition

Let a finite group G act on a finite set X. For g

\in

G, let

X^{g}

= \{x

\in

X : g

\cdot

x = x}

be the set of points fixed by g. Burnside’s Lemma states that the number of orbits X/G is given by \[

∣ X / G ∣

\frac{1}{∣ G ∣}

\sum_{g \in G}

∣ X^{g} ∣

. \] In colorings problems, take X to be the set of functions from positions \{1,

\dots

,n\} to a color set of size k, and let G be a permutation group on positions. If a permutation g has c(g) cycles in its disjoint cycle decomposition, then a coloring is fixed by g if and only if all positions in each cycle share the same color, yielding exactly

k^{c (g)}

fixed colorings. Therefore \[

∣ X / G ∣

\frac{1}{∣ G ∣}

\sum_{g \in G}

k^{c (g)}

. \] For the rotation group

C_{n}

, the rotation by r steps has c =

g cd

(n,r) cycles, giving the classic necklace formula. For the dihedral group

D_{n}

(rotations + reflections), reflections introduce two cases depending on whether n is odd or even.

04When to Use

Use Burnside’s Lemma whenever you need to count objects up to symmetries, especially when symmetries form a manageable finite group. Typical situations include counting distinct necklaces or bracelets under rotations and reflections, coloring vertices/edges/faces of regular polygons and polyhedra under their symmetry groups, and counting labelings of small graphs up to automorphisms. It’s also useful in puzzle state counting (e.g., states up to rotations), tilings under wallpaper or dihedral symmetries for small fundamental domains, and pattern counting in strings and arrays where cyclic shifts or reversals are considered equivalent. Burnside is most effective when you can compute fixed-point counts efficiently for each group element, which often reduces to counting cycles of permutations and raising k to that count. When the group is large but highly structured (like cyclic or dihedral), number-theoretic shortcuts (gcd identities, Euler’s totient) or Pólya’s Enumeration Theorem help collapse the sum. If the group is huge without exploitable structure, Burnside may be computationally impractical, and alternative approaches or approximations might be preferable.

⚠️Common Mistakes

Confusing orbits with cycles: cycles refer to cycle decomposition of a single permutation; orbits are equivalence classes under the whole group. Burnside counts orbits by averaging fixed sets, not by taking cycles of one permutation. - Forgetting to average: summing fixed counts without dividing by |G| overcounts by a factor of the group size. - Miscounting reflection fixes for bracelets: the exponent differs for odd vs even n; mixing these up is a frequent off-by-one error. - Using gcd where cycle counts are required: gcd(n,r) is specific to pure rotations on n positions; for general permutations, you must actually compute the number of cycles. - Ignoring modular division details: when working modulo a prime M, divide by |G| using the modular inverse (|G|^{M-2} \bmod M); if M is not coprime with |G|, you cannot simply invert. - Building the wrong group: ensure your permutation list actually forms the intended group (e.g., include all reflections in D_n). - Performance pitfalls: recomputing gcds or cycle counts naively across many test cases; prefer precomputation, divisor enumeration, and fast exponentiation.

Key Formulas

Burnside’s Lemma (Cauchy–Frobenius)

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣

Explanation: The number of equivalence classes (orbits) of X under G equals the average number of elements fixed by each group element. Use it by computing, for each symmetry, how many objects are unchanged.

Colorings under a permutation group

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum k^{c (g)}

Explanation: When X is k-colorings of n positions and g has c(g) cycles, the fixed colorings are $k^{c (g)}$ . Average over all group elements to get the number of distinct colorings.

Necklaces under rotations C_n

N_{n ec k l a ce} (n, k) = \frac{1}{n} r = 0 \sum n - 1 k^{g c d (n, r)}

Explanation: For rotation by r, positions split into gcd(n,r) cycles, and each cycle must be monochromatic, giving $k^{g c d (n, r)}$ fixed colorings. Averaging over n rotations yields the count of distinct necklaces.

GCD–totient identity for rotations

r = 0 \sum n - 1 k^{g c d (n, r)} = d ∣ n \sum φ (d) k^{\frac{n}{d}} = d ∣ n \sum φ (\frac{n}{d}) k^{d}

Explanation: Rotations with the same gcd(n,r) contribute equally and are counted by Euler’s totient. This identity speeds up necklace counting by summing over divisors instead of all r.

Bracelets under dihedral group D_n

N_{b r a ce l e t} (n, k) = \frac{1}{2 n} (r = 0 \sum n - 1 k^{g c d (n, r)} + {n k^{\frac{n + 1}{2}}, \frac{n}{2} k^{\frac{n}{2}} + \frac{n}{2} k^{\frac{n}{2} + 1}, n odd n even)

Explanation: Add reflection contributions: for odd n, each reflection fixes $k^{(n + 1) /2}$ ; for even n, half fix $k^{n /2}$ and half fix $k^{n /2 + 1}$ . Divide by 2n since $∣ D_{n} ∣$ =2n.

Cycle index polynomial

Z_{G} (s_{1}, s_{2}, \dots) = \frac{1}{∣ G ∣} g \in G \sum j \geq 1 \prod s_{j}^{c_{j} (g)}

Explanation: Encodes the cycle structure of the group action. Substituting $s_{j}$ $\leftarrow$ $\sum_{i}$ x_ $i^{j}$ counts colorings weighted by color variables; substituting $s_{j}$ $\leftarrow$ k gives Burnside’s count.

Arithmetic series (for complexity bounds)

i = 1 \sum n i = \frac{n ( n + 1 )}{2}

Explanation: Useful when summing per-element work across permutations or cycles. It bounds the cost of scanning arrays and cycle decompositions.

Asymptotic shorthand

O (n lo g n), O (n n), O (n τ (n))

Explanation: We describe algorithm growth with big-O notation. For example, $ $τ$ (n)$ is the divisor count; $n $n$ $ often appears in trial division factorizations up to $ $n$ $.

Complexity Analysis

A direct Burnside implementation over a permutation group G acting on n positions computes the cycle count c(g) for each g. Cycle decomposition via a visited array is O(n) per permutation. Summing

k^{c (g)}

with fast exponentiation is O(log k) per permutation. Therefore, time is O(

∣ G ∣

·(n + log k)), and space is O(n) for visited storage plus O(1) for accumulators. For cyclic necklaces under

C_{n}

, the naive Burnside sum over rotations takes O(n·log k) time using powmod and O(1) space. Using the divisor–totient identity reduces time to O(τ(n)·log k + D(n)) where τ(n) is the number of divisors and D(n) is the cost to enumerate divisors (typically O(√n)). If Euler’s totient values

φ (d)

are computed by trial division factorization for each divisor d, the additional cost is roughly O(∑_{d

|n} \sqrtd) \leq O(τ(n)\cdot\sqrtn); for a single query this is acceptable, and for many queries, precomputing φ up to a limit with a sieve yields O(N log log N) preprocessing. For bracelets (D_n), we reuse the rotational sum and add O(1) terms for reflections, keeping complexity similar to C_n. In modular arithmetic with a prime modulus M, division by |

G| is done with a modular inverse in O(log M) via fast exponentiation; total overhead is negligible compared to group iteration. Memory usage in all presented approaches is small: O(1) for number-theoretic variants, and O(n) for generic permutation-based Burnside (dominated by the visited array). For very large groups without structure, iterating all elements becomes infeasible; in such cases, exploit conjugacy classes (elements with identical cycle types) to aggregate counts and reduce time by a factor equal to average class size.

Code Examples

Necklaces under rotations C_n using Burnside (naive and totient-optimized)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Count distinct necklaces of length n with k colors under rotations (C_n)
5 // Provides two methods: naive Burnside over all rotations, and optimized using divisors and Euler's totient.
6 
7 static const long long MOD = 1'000'000'007LL; // prime modulus for safe division via modular inverse
8 
9 long long mod_pow(long long a, long long e, long long mod = MOD) {
10     long long r = 1 % mod;
11     a %= mod;
12     while (e > 0) {
13         if (e & 1) r = (__int128)r * a % mod;
14         a = (__int128)a * a % mod;
15         e >>= 1;
16     }
17     return r;
18 }
19 
20 long long mod_inv(long long a, long long mod = MOD) {
21     // Fermat's little theorem: mod must be prime and gcd(a,mod)=1
22     return mod_pow((a % mod + mod) % mod, mod - 2, mod);
23 }
24 
25 long long gcdll(long long a, long long b) {
26     while (b) { long long t = a % b; a = b; b = t; }
27     return a;
28 }
29 
30 // Euler's totient via trial division factorization (works well for a single n and its divisors)
31 long long phi_ll(long long x) {
32     long long result = x;
33     for (long long p = 2; p * p <= x; ++p) {
34         if (x % p == 0) {
35             while (x % p == 0) x /= p;
36             result = result / p * (p - 1);
37         }
38     }
39     if (x > 1) result = result / x * (x - 1);
40     return result;
41 }
42 
43 // Enumerate all positive divisors of n
44 vector<long long> divisors(long long n) {
45     vector<long long> d;
46     for (long long i = 1; i * i <= n; ++i) {
47         if (n % i == 0) {
48             d.push_back(i);
49             if (i * i != n) d.push_back(n / i);
50         }
51     }
52     sort(d.begin(), d.end());
53     return d;
54 }
55 
56 // Naive Burnside over all rotations: (1/n) * sum_{r=0}^{n-1} k^{gcd(n,r)}
57 long long necklaces_naive(long long n, long long k) {
58     long long sum = 0;
59     for (long long r = 0; r < n; ++r) {
60         long long g = gcdll(n, r);
61         sum = (sum + mod_pow(k, g)) % MOD;
62     }
63     // divide by n via modular inverse
64     return (sum * mod_inv(n % MOD)) % MOD;
65 }
66 
67 // Optimized using the divisor-totient identity: (1/n) * sum_{d|n} phi(d) * k^{n/d}
68 long long necklaces_totient(long long n, long long k) {
69     long long sum = 0;
70     for (long long d : divisors(n)) {
71         long long term = (phi_ll(d) % MOD) * mod_pow(k, n / d) % MOD;
72         sum += term;
73         if (sum >= MOD) sum -= MOD;
74     }
75     return (sum * mod_inv(n % MOD)) % MOD;
76 }
77 
78 int main() {
79     ios::sync_with_stdio(false);
80     cin.tie(nullptr);
81 
82     // Example usage: multiple queries
83     // Input: t then t lines of n k
84     int t; if (!(cin >> t)) return 0;
85     while (t--) {
86         long long n, k; cin >> n >> k;
87         long long ans1 = necklaces_naive(n, k);
88         long long ans2 = necklaces_totient(n, k);
89         cout << ans2 << "\n"; // print optimized answer
90         // Uncomment to verify both methods match (debug/testing):
91         // cerr << "naive=" << ans1 << ", opt=" << ans2 << "\n";
92     }
93     return 0;
94 }
95

We count rotationally distinct necklaces of length n with k colors using Burnside. The naive method sums k^{gcd(n,r)} over all rotations r and divides by n. The optimized method groups rotations by their gcd using the identity involving Euler’s totient: sum_{r} k^{gcd(n,r)} = sum_{d|n} φ(d) k^{n/d}. Both return the same count; the totient version is faster for large n.

Time: Naive: O(n · log MOD) for exponentiations. Optimized: O(√n + τ(n) · (log MOD + factor(d))) where factor(d) is trial division to compute φ(d); typically around O(√n · log MOD).Space: O(1) extra space besides the divisors list, which is O(τ(n)).

Bracelets under dihedral group D_n (rotations + reflections)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 static const long long MOD = 1'000'000'007LL;
5 
6 long long mod_pow(long long a, long long e, long long mod = MOD) {
7     long long r = 1 % mod; a %= mod;
8     while (e) { if (e & 1) r = (__int128)r * a % mod; a = (__int128)a * a % mod; e >>= 1; }
9     return r;
10 }
11 long long mod_inv(long long a, long long mod = MOD) { return mod_pow((a%mod+mod)%mod, mod-2, mod); }
12 
13 long long gcdll(long long a, long long b) { while (b) { long long t=a%b; a=b; b=t; } return a; }
14 
15 // Sum over rotations: S = sum_{r=0}^{n-1} k^{gcd(n,r)}
16 long long rotation_sum(long long n, long long k) {
17     long long S = 0;
18     for (long long r = 0; r < n; ++r) {
19         S += mod_pow(k, gcdll(n, r));
20         if (S >= MOD) S -= MOD;
21     }
22     return S;
23 }
24 
25 // Count distinct bracelets: divide by |D_n| = 2n
26 long long bracelets(long long n, long long k) {
27     long long S = rotation_sum(n, k);
28     long long reflSum = 0;
29     if (n % 2 == 1) {
30         // n reflections; each fixes k^{(n+1)/2}
31         reflSum = (n % MOD) * mod_pow(k, (n + 1) / 2) % MOD;
32     } else {
33         // n even: n/2 reflections through opposite beads (fix k^{n/2+1})
34         // and n/2 through opposite gaps (fix k^{n/2})
35         long long half = (n / 2) % MOD;
36         long long a = half * mod_pow(k, n / 2 + 1) % MOD;
37         long long b = half * mod_pow(k, n / 2) % MOD;
38         reflSum = (a + b) % MOD;
39     }
40     long long total = (S + reflSum) % MOD;
41     long long denom = (2 % MOD) * (n % MOD) % MOD;
42     return total * mod_inv(denom) % MOD;
43 }
44 
45 int main(){
46     ios::sync_with_stdio(false);
47     cin.tie(nullptr);
48 
49     // Input: t then t lines of n k
50     int t; if (!(cin >> t)) return 0;
51     while (t--) {
52         long long n, k; cin >> n >> k;
53         cout << bracelets(n, k) << "\n";
54     }
55     return 0;
56 }
57

The dihedral group D_n has 2n elements: n rotations and n reflections. We compute the rotation contribution as before, then add reflection contributions. For odd n, each reflection fixes k^{(n+1)/2} colorings; for even n, half fix k^{n/2} and half fix k^{n/2+1}. Divide the total by 2n to get the number of distinct bracelets.

Time: O(n · log MOD) per query due to the rotation sum; can be reduced using the divisor–totient trick for rotations.Space: O(1).

Generic Burnside over an explicit permutation group (cycle counting)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Generic Burnside implementation: given a list of permutations (the group action on n points),
5 // count k-colorings up to the group using (1/|G|) * sum k^{#cycles(perm)}.
6 
7 static const long long MOD = 1'000'000'007LL;
8 
9 long long mod_pow(long long a, long long e) {
10     long long r = 1 % MOD; a %= MOD;
11     while (e) { if (e & 1) r = (__int128)r * a % MOD; a = (__int128)a * a % MOD; e >>= 1; }
12     return r;
13 }
14 long long mod_inv(long long a) { return mod_pow((a%MOD+MOD)%MOD, MOD-2); }
15 
16 // Count cycles in a permutation given as a vector p with p[i] in [0..n-1]. Assumes p is a bijection.
17 int count_cycles(const vector<int>& p) {
18     int n = (int)p.size();
19     vector<int> vis(n, 0);
20     int cycles = 0;
21     for (int i = 0; i < n; ++i) {
22         if (!vis[i]) {
23             ++cycles;
24             int x = i;
25             while (!vis[x]) { vis[x] = 1; x = p[x]; }
26         }
27     }
28     return cycles;
29 }
30 
31 // Build dihedral group D_n acting on vertices 0..n-1 of an n-gon
32 vector<vector<int>> build_dihedral(int n) {
33     vector<vector<int>> G;
34     // Rotations r: i -> (i + r) mod n
35     for (int r = 0; r < n; ++r) {
36         vector<int> p(n);
37         for (int i = 0; i < n; ++i) p[i] = (i + r) % n;
38         G.push_back(move(p));
39     }
40     // Reflections: i -> (-i) mod n, then rotate by r to get all n reflections
41     for (int r = 0; r < n; ++r) {
42         vector<int> p(n);
43         for (int i = 0; i < n; ++i) p[i] = (r - i) % n < 0 ? (r - i + n) % n : (r - i) % n;
44         G.push_back(move(p));
45     }
46     return G;
47 }
48 
49 long long burnside_count_colorings(const vector<vector<int>>& group, long long k) {
50     long long sum = 0;
51     for (const auto& p : group) {
52         int c = count_cycles(p);
53         sum += mod_pow(k, c);
54         if (sum >= MOD) sum -= MOD;
55     }
56     long long inv = mod_inv((long long)group.size() % MOD);
57     return sum * inv % MOD;
58 }
59 
60 int main(){
61     ios::sync_with_stdio(false);
62     cin.tie(nullptr);
63 
64     // Example: number of distinct colorings of a square (n=4) with k colors under D_4
65     int n = 4; long long k; if (!(cin >> k)) return 0;
66     auto G = build_dihedral(n); // |G| = 8
67     cout << burnside_count_colorings(G, k) << "\n";
68 
69     // You can similarly pass any explicit permutation group acting on n points.
70     return 0;
71 }
72

We accept an explicit list of permutations representing the group action on n positions. For each permutation, we compute the number of disjoint cycles, c, and add k^{c}. Dividing by |G| yields the number of colorings up to the group. The example builds the dihedral group D_4 acting on the vertices of a square and returns the number of distinct colorings with k colors.

Time: O(|G| · (n + log MOD)) due to cycle counting and exponentiation for each permutation.Space: O(n) for the visited array during cycle counting; O(|G|·n) if you materialize the whole group.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Count distinct necklaces of length n with k colors under rotations (C_n)
5	// Provides two methods: naive Burnside over all rotations, and optimized using divisors and Euler's totient.
6
7	static const long long MOD = 1'000'000'007LL; // prime modulus for safe division via modular inverse
8
9	long long mod_pow(long long a, long long e, long long mod = MOD) {
10	long long r = 1 % mod;
11	a %= mod;
12	while (e > 0) {
13	if (e & 1) r = (__int128)r * a % mod;
14	a = (__int128)a * a % mod;
15	e >>= 1;
16	}
17	return r;
18	}
19
20	long long mod_inv(long long a, long long mod = MOD) {
21	// Fermat's little theorem: mod must be prime and gcd(a,mod)=1
22	return mod_pow((a % mod + mod) % mod, mod - 2, mod);
23	}
24
25	long long gcdll(long long a, long long b) {
26	while (b) { long long t = a % b; a = b; b = t; }
27	return a;
28	}
29
30	// Euler's totient via trial division factorization (works well for a single n and its divisors)
31	long long phi_ll(long long x) {
32	long long result = x;
33	for (long long p = 2; p * p <= x; ++p) {
34	if (x % p == 0) {
35	while (x % p == 0) x /= p;
36	result = result / p * (p - 1);
37	}
38	}
39	if (x > 1) result = result / x * (x - 1);
40	return result;
41	}
42
43	// Enumerate all positive divisors of n
44	vector<long long> divisors(long long n) {
45	vector<long long> d;
46	for (long long i = 1; i * i <= n; ++i) {
47	if (n % i == 0) {
48	d.push_back(i);
49	if (i * i != n) d.push_back(n / i);
50	}
51	}
52	sort(d.begin(), d.end());
53	return d;
54	}
55
56	// Naive Burnside over all rotations: (1/n) * sum_{r=0}^{n-1} k^{gcd(n,r)}
57	long long necklaces_naive(long long n, long long k) {
58	long long sum = 0;
59	for (long long r = 0; r < n; ++r) {
60	long long g = gcdll(n, r);
61	sum = (sum + mod_pow(k, g)) % MOD;
62	}
63	// divide by n via modular inverse
64	return (sum * mod_inv(n % MOD)) % MOD;
65	}
66
67	// Optimized using the divisor-totient identity: (1/n) * sum_{d\|n} phi(d) * k^{n/d}
68	long long necklaces_totient(long long n, long long k) {
69	long long sum = 0;
70	for (long long d : divisors(n)) {
71	long long term = (phi_ll(d) % MOD) * mod_pow(k, n / d) % MOD;
72	sum += term;
73	if (sum >= MOD) sum -= MOD;
74	}
75	return (sum * mod_inv(n % MOD)) % MOD;
76	}
77
78	int main() {
79	ios::sync_with_stdio(false);
80	cin.tie(nullptr);
81
82	// Example usage: multiple queries
83	// Input: t then t lines of n k
84	int t; if (!(cin >> t)) return 0;
85	while (t--) {
86	long long n, k; cin >> n >> k;
87	long long ans1 = necklaces_naive(n, k);
88	long long ans2 = necklaces_totient(n, k);
89	cout << ans2 << "\n"; // print optimized answer
90	// Uncomment to verify both methods match (debug/testing):
91	// cerr << "naive=" << ans1 << ", opt=" << ans2 << "\n";
92	}
93	return 0;
94	}
95

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Generic Burnside implementation: given a list of permutations (the group action on n points),
5	// count k-colorings up to the group using (1/\|G\|) * sum k^{#cycles(perm)}.
6
7	static const long long MOD = 1'000'000'007LL;
8
9	long long mod_pow(long long a, long long e) {
10	long long r = 1 % MOD; a %= MOD;
11	while (e) { if (e & 1) r = (__int128)r * a % MOD; a = (__int128)a * a % MOD; e >>= 1; }
12	return r;
13	}
14	long long mod_inv(long long a) { return mod_pow((a%MOD+MOD)%MOD, MOD-2); }
15
16	// Count cycles in a permutation given as a vector p with p[i] in [0..n-1]. Assumes p is a bijection.
17	int count_cycles(const vector<int>& p) {
18	int n = (int)p.size();
19	vector<int> vis(n, 0);
20	int cycles = 0;
21	for (int i = 0; i < n; ++i) {
22	if (!vis[i]) {
23	++cycles;
24	int x = i;
25	while (!vis[x]) { vis[x] = 1; x = p[x]; }
26	}
27	}
28	return cycles;
29	}
30
31	// Build dihedral group D_n acting on vertices 0..n-1 of an n-gon
32	vector<vector<int>> build_dihedral(int n) {
33	vector<vector<int>> G;
34	// Rotations r: i -> (i + r) mod n
35	for (int r = 0; r < n; ++r) {
36	vector<int> p(n);
37	for (int i = 0; i < n; ++i) p[i] = (i + r) % n;
38	G.push_back(move(p));
39	}
40	// Reflections: i -> (-i) mod n, then rotate by r to get all n reflections
41	for (int r = 0; r < n; ++r) {
42	vector<int> p(n);
43	for (int i = 0; i < n; ++i) p[i] = (r - i) % n < 0 ? (r - i + n) % n : (r - i) % n;
44	G.push_back(move(p));
45	}
46	return G;
47	}
48
49	long long burnside_count_colorings(const vector<vector<int>>& group, long long k) {
50	long long sum = 0;
51	for (const auto& p : group) {
52	int c = count_cycles(p);
53	sum += mod_pow(k, c);
54	if (sum >= MOD) sum -= MOD;
55	}
56	long long inv = mod_inv((long long)group.size() % MOD);
57	return sum * inv % MOD;
58	}
59
60	int main(){
61	ios::sync_with_stdio(false);
62	cin.tie(nullptr);
63
64	// Example: number of distinct colorings of a square (n=4) with k colors under D_4
65	int n = 4; long long k; if (!(cin >> k)) return 0;
66	auto G = build_dihedral(n); // \|G\| = 8
67	cout << burnside_count_colorings(G, k) << "\n";
68
69	// You can similarly pass any explicit permutation group acting on n points.
70	return 0;
71	}
72