题目描述

一个数字被称为好数字需满足下列条件： ①它有$2×n$个数位，$n$是正整数(允许有前导$0$)。 ②构成它的每个数字都在给定的数字集合$S$中。 ③它前$n$位之和与后$n$位之和相等或者它奇数位之和与偶数位之和相等 例如，对于$n=2$，$S=\{1,2\}$，合法的好数字有$8$个：$1111，1122，1212，1221，2112，2121，2211，2222$。 已知$n$，求合法的好数字个数$\bmod 999983$。

输入

第一行一个数$n$。 接下来一个长度不超过$10$的字符串，表示给定的数字集合。

输出

一行一个数字表示合法的好数字个数$\bmod 999983$。

输入样例

2
0987654321

输出样例

1240

提示

【数据规模】 对于20%的数据，$n≤7$。 对于100%的数据，$n≤1000,|S|≤10$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。