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

130. Circle

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


On a circle border there are 2k different points A1, A2, ..., A2k, located contiguously. These points connect k chords so that each of points A1, A2, ..., A2k is the end point of one chord. Chords divide the circle into parts. You have to find N - the number of different ways to connect the points so that the circle is broken into minimal possible amount of parts P.


Input

The first line contains the integer k (1 <= k <= 30).


Output

The first line should contain two numbers N and P delimited by space.


Sample Input

2
Sample Output

2 3
Author	: Natalia L. Andreeva, Alex Y. Suslov, Alexander S. Ivanov
Resource	: 5th Southern Subregional Contest. Saratov 2002
Date	: 2002-10-10

<|response|>
1. Abridged Problem Statement
Given an even number of points (2·k) labeled A1…A2k placed around a circle, you must draw k non‐directed chords that pair up all points. These chords partition the circle into some regions. Find:
  • N – the number of ways to draw the k chords so that the total number of regions is as small as possible.
  • P – that minimal number of regions.

2. Key Observations
• Any crossing of two chords creates extra regions. To minimize regions, no two chords should cross.
• The number of ways to draw k non‐crossing chords on 2·k points on a circle is the k-th Catalan number:
    Cₖ = (1/(k+1))·binomial(2k, k)
• A non‐crossing matching of k chords splits the disk into exactly k+1 regions.

3. Full Solution Approach
1. Read integer k (1 ≤ k ≤ 30).
2. Compute the sequence of Catalan numbers C[0…k] via the standard DP recurrence:
     C[0] = 1
     For n = 1…k:
       C[n] = Σ_{i=0…n−1} (C[i] · C[n−1−i])
3. Then N = C[k], and P = k + 1.
4. Print N and P.

Time complexity is O(k²), which is trivial for k ≤ 30. The largest Catalan number here (C₃₀ ≈ 3.9·10¹⁴) fits in a 64‐bit signed integer.

4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;

void read() { cin >> n; }

void solve() {
    /*
     * Connecting 2k contiguous points with k non-crossing chords minimizes the
     * number of regions, and a set of k chords splits the disk into exactly
     * k + 1 parts when no two chords cross. The count of non-crossing perfect
     * matchings of 2k points on a circle is the k-th Catalan number, built here
     * with the recurrence C[i] = sum_{j<i} C[j] * C[i-1-j]. So N = Catalan(k)
     * and P = k + 1.
     */

    vector<int64_t> C(n + 1, 0);
    C[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            C[i] += C[j] * C[i - j - 1];
        }
    }

    cout << C[n] << " " << n + 1 << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Solution with Detailed Comments
```python
def main():
    import sys
    data = sys.stdin.read().split()
    k = int(data[0])        # Number of chord pairs

    # Prepare a list for Catalan numbers up to index k
    C = [0] * (k + 1)
    C[0] = 1               # Base case

    # Compute Catalan numbers via convolution DP
    for n in range(1, k + 1):
        total = 0
        for i in range(n):
            total += C[i] * C[n - 1 - i]
        C[n] = total

    N = C[k]               # Number of ways
    P = k + 1              # Minimal number of regions

    # Output the result
    print(N, P)

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