<|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.

382. Cantor Function
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard





The Cantor function f(x) (see picture) is defined as the function on [0, 1] as follows:

If x belongs to Cantor set ( where ni are different positive integers), then .
f is continuous and monotonous function.

In 2004, Gorin and Kukushkin showed that  is rational. You are to find In and output it as irreducible fraction.

Input
First line contains one integer number n (0 ≤ n ≤ 50).

Output
You should output In in the form p/q, where p and q are the numerator and the denominator of In respectively. Note that p and q must be natural and (p, q) must be equal to 1. You should output p and q without leading zeroes.

Example(s)
sample input
sample output
0
1/1

sample input
sample output
1
1/2

sample input
sample output
2
3/10

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

Given the Cantor (Devil’s staircase) function \(f(x)\) on \([0,1]\), compute for \(0 \le n \le 50\):

\[
I_n=\int_{0}^{1} f(x)^n \, dx
\]

It is known that \(I_n\) is rational. Output it as an irreducible fraction `p/q`.

---

## 2) Key observations needed to solve the problem

### Self-similarity of the Cantor function
The Cantor function satisfies:

1. For \(x\in[0,1]\):
   \[
   f(x/3)=\frac{f(x)}{2}
   \]
2. For \(x\in[1/3,2/3]\):
   \[
   f(x)=\frac12
   \]
3. For \(x\in[0,1]\):
   \[
   f(x/3+2/3)=\frac12+\frac{f(x)}2=\frac{1+f(x)}2
   \]

### Split the integral into three parts
Split \([0,1]\) into \([0,1/3]\), \([1/3,2/3]\), \([2/3,1]\). Each part can be rewritten in terms of integrals of powers of \(f\), i.e. the values \(I_k\).

### Result: a recurrence for \(I_n\)
After substitutions and a binomial expansion, you get a recurrence that expresses \(I_n\) using \(I_0,\dots,I_{n-1}\). Hence we can compute sequentially from \(I_0=1\).

### Big integers are required
For \(n\le 50\), numerators/denominators grow beyond 64-bit, so we need arbitrary precision integers (C++: custom bigint / boost multiprecision; Python: built-in `int`).

---

## 3) Full solution approach based on the observations

Let:
\[
I_n=\int_0^1 f(x)^n\,dx
\]

### Compute each interval’s contribution

**A) Interval \([0,1/3]\)**  
Substitute \(u=3x\), \(dx=du/3\), and use \(f(u/3)=f(u)/2\):
\[
\int_0^{1/3} f(x)^n dx
=\frac{1}{3}\int_0^1\left(\frac{f(u)}2\right)^n du
=\frac{1}{3\cdot 2^n}I_n
\]

**B) Interval \([1/3,2/3]\)**  
Here \(f(x)=1/2\), length \(1/3\):
\[
\int_{1/3}^{2/3} f(x)^n dx
=\frac{1}{3}\left(\frac12\right)^n
=\frac{1}{3\cdot 2^n}
\]

**C) Interval \([2/3,1]\)**  
Substitute \(u=3x-2\), \(dx=du/3\), and \(f(x)=(1+f(u))/2\):
\[
\int_{2/3}^1 f(x)^n dx
=\frac{1}{3}\int_0^1\left(\frac{1+f(u)}2\right)^n du
=\frac{1}{3\cdot 2^n}\int_0^1 (1+f(u))^n du
\]
Expand:
\[
(1+f(u))^n=\sum_{k=0}^n \binom{n}{k} f(u)^k
\]
So:
\[
\int_{2/3}^1 f(x)^n dx
=\frac{1}{3\cdot 2^n}\sum_{k=0}^n\binom{n}{k} I_k
\]

### Combine and simplify
Sum A+B+C:

\[
I_n=\frac{1}{3\cdot 2^n}I_n + \frac{1}{3\cdot 2^n}
+\frac{1}{3\cdot 2^n}\sum_{k=0}^n\binom{n}{k}I_k
\]

Multiply by \(3\cdot 2^n\):
\[
3\cdot 2^n I_n = I_n + 1 + \sum_{k=0}^n\binom{n}{k}I_k
\]
Note the sum includes \(k=n\) term which equals \(I_n\), so move terms:
\[
(3\cdot 2^n - 2)I_n = 1 + \sum_{k=0}^{n-1}\binom{n}{k}I_k
\]

Base:
\[
I_0=\int_0^1 1\,dx=1
\]

### Algorithm
Compute \(I_0,\dots,I_n\) in order as rational numbers.

To do this efficiently, keep each \(I_k=p_k/q_k\) reduced. For each \(m\):

\[
I_m = \frac{1+\sum_{k=0}^{m-1}\binom{m}{k}I_k}{3\cdot 2^m -2}
\]

In C++ big-integer rational addition is easiest if we maintain:
- `common = lcm(q_0, ..., q_{m-1})`
- build the RHS numerator over `common` once
- then do one final reduction by gcd.

Complexity is tiny for \(n\le 50\).

---

## 4) C++ implementation with detailed comments

Below is a clean C++ solution using **Boost.Multiprecision** (much shorter than implementing bigint by hand, and perfectly fine within constraints).

```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

// Compute gcd for cpp_int (Euclid).
static cpp_int gcd_cpp(cpp_int a, cpp_int b) {
    while (b != 0) {
        cpp_int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

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

    int n;
    cin >> n;

    // Precompute binomial coefficients C(i,j) for i<=50
    // They fit in 64-bit easily.
    vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }

    // Store I_k as reduced fraction p[k]/q[k].
    vector<cpp_int> p(n + 1), q(n + 1);
    p[0] = 1; q[0] = 1; // I_0 = 1

    // common = lcm of denominators q[0..m-1] while building I_m
    cpp_int common = 1;

    for (int m = 1; m <= n; m++) {
        // Build RHS = 1 + sum_{k=0..m-1} C(m,k)*I_k as num/common.
        cpp_int num = common; // "1" = common/common

        for (int k = 0; k < m; k++) {
            // term = C(m,k) * p[k]/q[k]
            // Convert to denominator = common:
            // contribution = (common/q[k]) * p[k] * C(m,k)
            num += (common / q[k]) * p[k] * cpp_int(C[m][k]);
        }

        // I_m = num / ( common * (3*2^m - 2) )
        cpp_int factor = cpp_int(3) * (cpp_int(1) << m) - 2;
        cpp_int den = common * factor;

        // Reduce once
        cpp_int g = gcd_cpp(num, den);
        p[m] = num / g;
        q[m] = den / g;

        // Update common = lcm(common, q[m]) = common / gcd(common,q[m]) * q[m]
        cpp_int h = gcd_cpp(common, q[m]);
        common = (common / h) * q[m];
    }

    cout << p[n] << "/" << q[n] << "\n";
    return 0;
}
```

---

## 5) Python implementation with detailed comments

Python’s `int` is arbitrary precision, so this becomes very straightforward.

```python
import math
from math import comb

def solve():
    n = int(input().strip())

    # I_k = p[k]/q[k] reduced
    p = [0] * (n + 1)
    q = [0] * (n + 1)
    p[0], q[0] = 1, 1  # I_0 = 1

    # common = lcm of previous denominators for fast summation
    common = 1

    for m in range(1, n + 1):
        # Build numerator of:
        # 1 + sum_{k=0..m-1} C(m,k) * I_k
        # over denominator = common
        num = common  # "1" => common/common

        for k in range(m):
            num += (common // q[k]) * p[k] * comb(m, k)

        # I_m = num / (common * (3*2^m - 2))
        den = common * (3 * (1 << m) - 2)

        # Reduce
        g = math.gcd(num, den)
        p[m] = num // g
        q[m] = den // g

        # Update common = lcm(common, q[m])
        common = common // math.gcd(common, q[m]) * q[m]

    print(f"{p[n]}/{q[n]}")

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

This matches the samples:
- \(n=0\) → `1/1`
- \(n=1\) → `1/2`
- \(n=2\) → `3/10`