U166151 20210628num

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

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

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

对于 $20\%$ 的数据，$n\le7$。 对于 $100\%$ 的.据, $n\le1000,|S| \le 10$。