#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 50;

struct Bigint {
	char s[N];
	Bigint(char _[]) {
		int len = strlen(_ + 1);
		for (int i = 1; i <= len; i++) s[i] = _[i];
	}
	Bigint operator * (int b) {
		int a[N], c[N], lena = strlen(s + 1), lenc = lena;
		memset(a, 0, sizeof(a));
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= lena; i++) a[i] = s[lena - i + 1] - '0';
		for (int i = 1; i <= lena; i++) c[i] = a[i] * b;
		for (int i = 1; i <= lenc; i++) {
			c[i + 1] += c[i] / 10;
			c[i] %= 10;
		}
		while (c[lenc + 1] >= 10) {
			++lenc;
			c[lenc + 1] += c[lenc] / 10;
			c[lenc] %= 10;
		}
		char S[N];
		memset(S, 0, sizeof(S));
		for (int i = 1; i <= lenc; i++) S[i] = c[lenc - i + 1] + '0';
		Bigint r = Bigint(S);
		return r;
	}
} ;

Bigint dp[10005]; // 报错 no matching function for call to Bigint::Bigint().
// 有且仅有这一行报错


int n;

int main() {
	scanf("%d", &n);
//	for (int i = 1; i <= n; i++) 
//		for (int j = 1; j <= )
	return 0;
}