#P17839. [ONTAK 2021]KOR

[ONTAK 2021]KOR

公司的会议

公司员工组成一棵有 NN 层的满二叉树,共 2N−12^N-1 人,按堆式编号。员工 ii 的两个直接下属为 2i2i 和 2i+12i+1。每人最初支持 A 或 B。

每个非叶员工都要与自己的两个直接下属开一次会。会议结束时,这三个人全部改为支持会议开始时三人中的多数意见。所有会议串行进行,会议的每一种排列顺序等概率出现。

求全部会议结束后,根节点员工支持 A 的概率。

输入格式

第一行 NN,第二行一个长度为 2N−12^N-1 的 A/B 字符串,第 ii 个字符表示员工 ii 的初始意见。

输出格式

输出一个概率,小数点后必须恰好有 1010 位数字。本题包按绝对误差不超过 10−1010^{-10} 判定该测试点通过。

数据范围

2≤N≤122\le N\le12。

原赛按精度给予部分分;本题包采用独立测试点计分,每个测试点须达到原赛满分精度。

样例

3
AABBBBA
0.5000000000