#BS0030. [HTOI-2] 盲盒

[HTOI-2] 盲盒

题目背景

小A喜欢玩原神。

题目描述

原神新出了一种抽卡方式:开盲盒。

小A每天会买一个盲盒,持续 nn 天。如果他没中,他就会非常沮丧,不会再买盲盒了。

小B得知这件事后,想要帮助小A。具体来说,小A每天买完盲盒后,小B会使用高超的黑客技术随机等概率让接下来的一天小A必中。

现在想要知道,小A买盲盒的期望天数模 998244853998244853 的值。

输入格式

第一行一个正整数 nn

第二行一个 0101 序列,如果第 ii 为是 00 表示小A这天不会中,反之,必中。

输出格式

输出小A买盲盒的期望天数模 998244853998244853 的值。

可以证明,答案一定为有理数,设其为 ab\dfrac{a}{b}a,ba,b 之间互质),则答案 xx 满足 0x9982448520 \le x \le 998244852abx(mod998244853)a \equiv bx \pmod {998244853}。可以证明这样的 xx 唯一存在。

样例 #1

样例输入 #1

2 
01

样例输出 #1

2

提示

对于 30%30\% 的数据,n1000n \le 1000

对于 100%100\% 的数据,n106n \le 10^6