#include <cstdio>
#include <vector>
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define dep(i, u, d) for(int i = u; i >= d; --i)
int ured() {
	int re = 0;
	char ch;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
long long lred() {
	long long re = 0;
	char ch;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
void uwit(int da) {
	int ch[21], cn = 0;
	do {
		ch[++cn] = da - da / 10 * 10;
	} while(da /= 10);
	do {
		putchar('0' ^ ch[cn]);
	} while(--cn);
}
const int _maxn = 10011, _mods = 998244353;
int qinv(int da) {
	int re = 1, up = _mods - 2;
	while(up) {
		if(up & 1) {
			re = 1ll * re * da % _mods;
		}
		da = 1ll * da * da % _mods, up >>= 1;
	}
	return re;
}
int n = 20, p[_maxn], cans[_maxn], fans[_maxn], rans;
long long m;
std :: vector<int> dans;
std :: vector<int> fqbm(int *da, int cn) {
	std :: vector<int> re, lt;
	int dw = -1, dt, ml, rg;
	rep(i, 0, cn - 1) {
		rg = 0;
		rep(j, 1, re . size()) {
			rg = (1ll * da[i - j] * re[j - 1] + rg) % _mods;
		}
		if(rg == da[i]) {
		} else if(dw == -1) {
			dw = i;
			if((dt = da[i] - rg) < 0) {
				dt += _mods;
			}
			rep(j, 0, i) {
				re . push_back(0);
			}
		} else {
			std :: vector<int> nw = re;
			if(re . size() < i - dw + lt . size()) {
				re . resize(i - dw + lt . size());
			}
			if((re[i - dw - 1] += (ml = 1ll * (da[i] - rg + _mods) * qinv(dt) % _mods)) >= _mods) {
				re[i - dw - 1] -= _mods;
			}
			rep(j, 1, lt . size()) {
				re[i - dw + j - 1] = (1ll * (_mods - ml) * lt[j - 1] + re[i - dw + j - 1]) % _mods;
			}
			if(nw . size() < lt . size() - dw - 1) {
				lt = nw, dw = i;
				if((dt = da[i] - rg) < 0) {
					dt += _mods;
				}
			}
		}
	}
	return re;
}
void fcpy(int *fr, int *re, int cn) {
	rep(i, 0, cn - 1) {
		re[i] = fr[i];
	}
}
int cpyy[_maxn], cpyz[_maxn];
void fmul(int *le, int *ri, int *re, int ln, int rn) {
	rep(i, 0, ln + rn - 2) {
		re[i] = 0;
	}
	rep(i, 0, ln - 1) {
		rep(j, 0, rn - 1) {
			re[i + j] = (1ll * le[i] * ri[j] + re[i + j]) % _mods;
		}
	}
}
void fmol(int *fr, int *mo, int cn, int mn) {
	int rg = 0, nv = qinv(mo[mn - 1]);
	dep(i, cn - 1, mn - 1) {
		rg = 1ll * (_mods - nv) * fr[i] % _mods;
		rep(j, 0, mn - 1) {
			fr[i - mn + j + 1] = (1ll * rg * mo[j] + fr[i - mn + j + 1]) % _mods;
		}
	}
}
void fpol(int *da, int *re, long long up, int cn) {
	re[0] = 1;
	if(cn == 1) {
		cpyy[0] = 1ll * (_mods - da[0]) * qinv(da[1]) % _mods;
	} else {
		cpyy[1] = 1;
	}
	while(up) {
		if(up & 1) {
			fcpy(re, cpyz, cn - 1), fmul(cpyy, cpyz, re, cn - 1, cn - 1), fmol(re, da, (cn << 1) - 3, cn);
		}
		fcpy(cpyy, cpyz, cn - 1), fmul(cpyz, cpyz, cpyy, cn - 1, cn - 1), fmol(cpyy, da, (cn << 1) - 3, cn);
		up >>= 1;
	}
}
const int _tabl[20] = {45, 4455, 407430, 36934785, 350210541, 427185456, 991901155, 110899952, 89411672, 401287887, 811189931, 286603985, 426843378, 418261776, 744223671, 302153364, 34240762, 689891595, 101012015, 748341487};
int main() {
	n = 20, m = lred() - 1;
	rep(i, 0, n - 1) {
		p[i] = _tabl[i];
	}
	dans = fqbm(p, n);
	rep(i, 1, dans . size()) {
		if(dans[i - 1]) {
			cans[dans . size() - i] = _mods - dans[i - 1];
		}
	}
	cans[dans . size()] = 1, fpol(cans, fans, m, dans . size() + 1);
	rep(i, 0, dans . size() - 1) {
		rans = (1ll * p[i] * fans[i] + rans) % _mods;
	}
	uwit(rans), putchar('\n');
	return 0;
}