题目描述

我们有 $9K$ 张卡片。每个 $i = 1, 2, \\dots, 9$ 的卡片上都写着 $i$。
我们随机洗牌并将五张卡片发给高桥和青木，其中四张面朝上，一张面朝下。
给你一个代表发给高桥的卡片的字符串 $S$，和一个代表发给青木的卡片的字符串 $T$。
$S$ 和 $T$ 都是长度为五的字符串。每个字符串的前四个字符是 1, 2, $\\dots$, 或 9，表示正面朝上的卡片上的数字。字符串的最后一个字符是 #，表示卡片正面朝下。
我们定义五张卡片手牌的得分为 $\\displaystyle \\sum_{i=1}^9 i \\times 10^{c_i}$，其中 $c_i$ 是数字 $i$ 出现的次数。
当高桥的手牌得分高于青木的手牌得分时，高桥获胜。
计算高桥获胜的概率。

约束条件

• $2 ≤ K ≤ 10^5$
• $|S| = |T| = 5$
• $S$ 和 $T$ 的前四个字符是 1, 2, $\\dots$, 或 9。
• $S$ 和 $T$ 中的数字 1, 2, $\\dots$, 和 9 加在一起共不超过 $K$ 次。
• $S$ 和 $T$ 的最后一个字符都是 #。

输入

从标准输入读入数据，输入格式如下：

$K$ $S$ $T$

输出

输出高桥获胜的概率，保留小数点后 16 位。如果答案与我们的答案的绝对或相对误差不超过 $10^{-5}$，则判定为正确。

示例输入 1

2
1144#
2233#

示例输出 1

0.4444444444444444

例如，如果高桥的手牌是 11449，青木的手牌是 22338，则高桥的得分为 $100+2+3+400+5+6+7+8+90=621$，青木的得分为 $1+200+300+4+5+6+7+80+9=612$，高桥获胜。
高桥获胜的情况是高桥正面朝下的牌的数字大于青木正面朝下的牌的数字，因此高桥的获胜概率为 $\\frac49$。

示例输入 2

2
9988#
1122#

示例输出 2

1.0

示例输入 3

6
1122#
2228#

示例输出 3

0.001932367149758454

只有当高桥的手牌是 11222，青木的手牌是 22281 时，高桥才能获胜，概率为 $\\frac2{1035}$。

示例输入 4

100000
3226#
3597#

示例输出 4

0.6296297942426154