<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

208. Toral Tickets
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



On the planet Eisiem passenger tickets for the new mean of transportation are planned to have the form of tores.

Each tore is made of a single rectangular black rubber sheet containing N × M squares. Several squares are marked with white, thus encoding the ticket's source and destination.

When the passenger buys the ticket, the ticket booking machine takes the rubber sheet, marks some squares to identify the route of the passenger, and then provides it to the passenger. The passenger next must glue the ticket.

The ticket must be clued the following way. First two its sides of greater length are glued together, forming a cylinder. Next cylinder base circles, each of which has the length equal to the length of the short side of the original rubber sheet, are glued together. They must be glued in such a way, that the cells, sides of which are glued, first belonged to the same row of the sheet. Note that the inner and the outer part of the sheet can be distinguished.

The resulting tore is the valid ticket.

Note that if the original sheet is square, there are two topologically different ways to make a tore out of a rubber sheet.

Ticket material is so perfect and gluing quality is so fine, that no one is able to find the seam, and this leads to some problems. First, the same tore can be obtained using different sheets. More of that, the same sheet can lead to tores that look a bit different.

Now the transport companies of Eisiem wonder, how many different routes they can organize, so that the following conditions are satisfied:


tickets for different routes are represented by different tores;
if some rubber sheet was marked to make the tore for some route, it cannot be used to make the tore for another route.


Help them to calculate the number of routes they can organize.

Input
The first line of the input file contains N and M (1 ≤ N, M ≤ 20).

Output
Output the number of routes Eisiem transport companies can organize.

Sample test(s)

Input
Test #1

2 2

Test #2

2 3

Output
Test #1

6

Test #2

13
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-23

<|response|>
## 1) Abridged problem statement (concise)

Given an \(N \times M\) grid whose cells are colored black/white, the sheet is glued into a torus in a specified way. After gluing, seams are invisible, and the torus can be moved/rotated in 3D without turning it inside out (inner/outer side distinguishable → **no reflections**).

Two colorings represent the same ticket if one can be transformed into the other by such an allowed symmetry.  
Compute the number of distinct tickets (distinct colorings on the torus up to these symmetries) for \(1 \le N,M \le 20\).

The answer may be as large as \(2^{400}\), so big integers are needed (in C++; Python has them built-in).

---

## 2) Key observations

1. **After gluing, the seam is not observable**  
   So shifting the sheet before gluing does not change the final visible torus. This creates **cyclic translations** in both directions.

2. **Allowed symmetries are orientation-preserving**  
   Inner and outer sides are distinguishable, so you cannot mirror/reflect the surface (that would flip orientation / turn inside-out).

3. **The symmetry group acting on cells is finite and small**
   Model the torus as coordinates \((r,c)\) with:
   - \(r \in \mathbb{Z}_N\)
   - \(c \in \mathbb{Z}_M\)

   Always present:
   - Translations: \((r,c)\mapsto(r+a,\ c+b)\)
   - 180° rotation (on the torus surface) + translation: \((r,c)\mapsto(-r+a,\ -c+b)\)

   If \(N=M\) (square), additional orientation-preserving rotations exist:
   - 90° + translation: \((r,c)\mapsto(c+a,\ -r+b)\)
   - 270° + translation: \((r,c)\mapsto(-c+a,\ r+b)\)

4. **Burnside’s lemma counts distinct colorings under symmetries**
   Number of distinct tickets = number of orbits:
   \[
   \text{ans}=\frac{1}{|G|}\sum_{g\in G} |\mathrm{Fix}(g)|
   \]

5. **Fixed colorings depend only on cycle count**
   Each symmetry \(g\) permutes the \(NM\) cells.  
   A coloring is fixed iff all cells in the same permutation cycle have the same color.  
   If \(g\) has \(k\) cycles, then \(|\mathrm{Fix}(g)|=2^k\).

6. **Constraints allow brute cycle counting per group element**
   - \(NM \le 400\)
   - \(|G|\le 4N^2 \le 1600\)
   For each \(g\), we can compute number of cycles in \(O(NM)\) by simulation.

---

## 3) Full solution approach

### Step A — Define the group \(G\)

Let cells be \((r,c)\).

- For all \(a \in [0,N-1]\), \(b \in [0,M-1]\):
  1) Translation:
     \[
     T_{a,b}(r,c) = (r+a \bmod N,\ c+b \bmod M)
     \]
  2) 180° rotation + translation:
     \[
     R_{a,b}(r,c) = (-r+a \bmod N,\ -c+b \bmod M)
     \]
- If \(N=M\), for all \(a,b \in [0,N-1]\):
  3) 90° rotation + translation:
     \[
     Q_{a,b}(r,c) = (c+a \bmod N,\ -r+b \bmod N)
     \]
  4) 270° rotation + translation:
     \[
     Q^{-1}_{a,b}(r,c) = (-c+a \bmod N,\ r+b \bmod N)
     \]

Group size:
- If \(N \ne M\): \(|G| = 2NM\)
- If \(N = M\): \(|G| = 4N^2 = 4NM\)

### Step B — For each group element, count cycles

Given a mapping `perm(r,c) -> (nr,nc)`, compute cycle count:

- Maintain `visited[N][M] = false`.
- For each cell not visited:
  - Start walking `(r,c) = perm(r,c)` repeatedly, marking visited, until you return to an already visited cell.
  - That completes one cycle; increment `cycles`.

This yields \(k = \#\text{cycles}(g)\) in \(O(NM)\).

### Step C — Apply Burnside

Accumulate:
\[
S = \sum_{g\in G} 2^{\text{cycles}(g)}
\]
Then:
\[
\text{ans} = S / |G|
\]

### Step D — Big integer

- Python: use built-in `int`.
- C++: implement a simple base \(10^9\) big integer supporting:
  - addition
  - division by small integer (the group size)

---

## 4) C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  We need big integers up to about 2^(400) ~ 10^120.
  Implement a minimal big integer in base 1e9:
  - addition
  - division by small int (|G| <= 1600)
*/

static const long long BASE = 1000000000LL;

struct BigInt {
    // digits in base BASE, little-endian: d[0] is least significant
    vector<long long> d;

    BigInt(long long v = 0) {
        if (v == 0) {
            d = {0};
            return;
        }
        while (v > 0) {
            d.push_back(v % BASE);
            v /= BASE;
        }
    }

    // this += other
    BigInt& operator+=(const BigInt& other) {
        d.resize(max(d.size(), other.d.size()) + 1, 0);
        for (size_t i = 0; i < other.d.size(); i++) d[i] += other.d[i];

        // normalize carries
        for (size_t i = 0; i + 1 < d.size(); i++) {
            d[i + 1] += d[i] / BASE;
            d[i] %= BASE;
        }

        // trim leading zeros
        while (d.size() > 1 && d.back() == 0) d.pop_back();
        return *this;
    }

    // this /= v (v is small, positive)
    BigInt& operator/=(long long v) {
        long long carry = 0;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            long long cur = d[i] + carry * BASE;
            d[i] = cur / v;
            carry = cur % v;
        }
        while (d.size() > 1 && d.back() == 0) d.pop_back();
        return *this;
    }

    friend ostream& operator<<(ostream& out, const BigInt& x) {
        out << x.d.back();
        for (int i = (int)x.d.size() - 2; i >= 0; i--) {
            out << setw(9) << setfill('0') << x.d[i];
        }
        return out;
    }
};

int N, M;
BigInt pw2[401]; // pw2[k] = 2^k for k up to NM (<= 400)

// Count cycles of the permutation on an N x M grid defined by perm(r,c).
template <class F>
int count_cycles(F perm) {
    vector<vector<char>> vis(N, vector<char>(M, 0));
    int cycles = 0;

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            if (vis[r][c]) continue;
            cycles++;
            int cr = r, cc = c;
            // follow permutation until we hit a visited cell
            while (!vis[cr][cc]) {
                vis[cr][cc] = 1;
                auto [nr, nc] = perm(cr, cc);
                cr = nr; cc = nc;
            }
        }
    }
    return cycles;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    int NM = N * M;

    // Precompute powers of 2: pw2[k] = 2^k
    pw2[0] = BigInt(1);
    for (int i = 1; i <= NM; i++) {
        pw2[i] = pw2[i - 1];
        pw2[i] += pw2[i - 1]; // doubling
    }

    // Group size:
    // - non-square: translations + 180-rot-with-translation => 2*N*M
    // - square: also 90/270 rotations => 4*N*M
    int group_size = (N == M) ? 4 * N * M : 2 * N * M;

    BigInt total(0); // sum over g of |Fix(g)| = 2^(#cycles(g))

    // Enumerate all translations and 180-degree rotations (always available)
    for (int a = 0; a < N; a++) {
        for (int b = 0; b < M; b++) {

            // Translation: (r,c) -> (r+a, c+b)
            int k1 = count_cycles([&](int r, int c) -> pair<int,int> {
                return {(r + a) % N, (c + b) % M};
            });
            total += pw2[k1];

            // 180-degree rotation + translation:
            // (r,c) -> (-r + a, -c + b) mod (N,M)
            int k2 = count_cycles([&](int r, int c) -> pair<int,int> {
                return {(N - r + a) % N, (M - c + b) % M};
            });
            total += pw2[k2];
        }
    }

    // If square, add 90 and 270 degree rotations (with translations)
    if (N == M) {
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {

                // 90-degree: (r,c) -> (c+a, -r+b)
                int k3 = count_cycles([&](int r, int c) -> pair<int,int> {
                    return {(c + a) % N, (N - r + b) % N};
                });
                total += pw2[k3];

                // 270-degree: (r,c) -> (-c+a, r+b)
                int k4 = count_cycles([&](int r, int c) -> pair<int,int> {
                    return {(N - c + a) % N, (r + b) % N};
                });
                total += pw2[k4];
            }
        }
    }

    // Burnside average
    total /= group_size;
    cout << total << "\n";
    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys

def count_cycles(n, m, perm):
    """
    Count number of cycles in the permutation of an n x m grid
    induced by perm(r,c) -> (nr,nc).
    """
    vis = [[False] * m for _ in range(n)]
    cycles = 0

    for r in range(n):
        for c in range(m):
            if vis[r][c]:
                continue
            cycles += 1
            cr, cc = r, c
            while not vis[cr][cc]:
                vis[cr][cc] = True
                cr, cc = perm(cr, cc)

    return cycles


def solve():
    data = sys.stdin.read().strip().split()
    n, m = map(int, data[:2])
    nm = n * m

    # Precompute powers of 2 (optional; Python pow(2,k) is fine too)
    pw2 = [1] * (nm + 1)
    for i in range(1, nm + 1):
        pw2[i] = pw2[i - 1] * 2

    # Group size
    group_size = 4 * n * m if n == m else 2 * n * m

    total = 0  # sum over group elements of 2^(#cycles)

    # Translations and 180-degree rotations
    for a in range(n):
        for b in range(m):
            k = count_cycles(n, m, lambda r, c: ((r + a) % n, (c + b) % m))
            total += pw2[k]

            k = count_cycles(n, m, lambda r, c: ((n - r + a) % n, (m - c + b) % m))
            total += pw2[k]

    # If square, also 90 and 270 degree rotations
    if n == m:
        for a in range(n):
            for b in range(n):
                k = count_cycles(n, n, lambda r, c: ((c + a) % n, (n - r + b) % n))
                total += pw2[k]

                k = count_cycles(n, n, lambda r, c: ((n - c + a) % n, (r + b) % n))
                total += pw2[k]

    # Burnside lemma
    ans = total // group_size
    print(ans)


if __name__ == "__main__":
    solve()
```

---

If you want, I can also provide a short proof/intuition for why exactly these rotations are the only orientation-preserving symmetries induced by the gluing model (and why reflections are excluded).