时间限制： 1.0 秒

空间限制： 512 MB

题目描述

$1,2,4,6$ 这四个数字有一个神奇的性质：如果将其分别取以 2 为底的幂，得到的分别是 $2,4,16,64$，仍是由这四个数字组成的。

我们从数字串 1 开始，每秒钟它的每一位都会独立地变成 2 的幂。例如，在前几秒钟，数字串会依次变成：

1. 2
2. 4
3. 16
4. 264
5. 46416
6. 166416264
7. 264641626446416
8. 46416641626446416166416264
9. 166416264641626446416166416264264641626446416

显然，这些数字串都仅包含 $1,2,4,6$ 这四个数字。

输入整数 $n$ 和数字串 $S$，请你求出 $S$ 在第 $n$ 秒钟的数字串共出现了几次？由于答案可能很大，只需要你输出它对 $998244353$ 取模的结果。

输入格式

从标准输入读入数据。

包含两行，第一行为一个数 $n$，第二行为一个串 $S$。

输出格式

输出到标准输出。

仅有一行，含有一个整数，表示所求的答案。

9
26

5

样例 1 解释

第 9 秒的数字串为 166416264641626446416166416264264641626446416，其中出现了 5 次 26。

2020
16

292008622

子任务

对于所有的数据，保证 $0 \leq n \leq 10^9$，$1 \leq |S| \leq 10^5$，且 $S$ 只包含 1、2、4、6 这四种字符。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

可能存在答案为 0 的情况，但是对所有测试点皆输出 0 不会得分。