Migrated from Lutece 2856 不幸之船

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

巴勒德侯爵有一艘飞船，这艘不幸之船三天两头不是爆炸就是失灵，导致巴勒德侯爵很是火大。

这艘不幸之船有一个名字，我们用字符串 $S$ 来代表它。巴勒德侯爵认为，不幸之船的名字本身就是一种不幸，所以他想在生活中抹去不幸之船的一切踪迹。

现在，巴勒德侯爵要写一本自传。这本自传恰好有 $n$ 个字符，仅包含大小写字母和数字。巴勒德侯爵想知道，有多少本不同的自传，使得这本自传中，没有一个子串是不幸之船的名字 $S$。

由于答案可能会很大，请你输出答案对 $998244353$ 取模后的结果。

Input

第一行一个整数 $n\ (1\le n\le 10^9)$。

第二行一个串，代表 $S\ (1 \le |S| \le 200)$。$S$ 仅包含小写字母，大写字母和数字。

Output

输出一个数，代表结果。

Samples

5
1

844596301

Resources

The 19th UESTC Programming Contest Preliminary