卡牌胜负

题目描述

写着 $1, 2, \dots, 9$ 的卡牌各有 $K$ 张,共计 $9K$ 张。

将这些卡牌随机洗牌后,分给高桥君和青木君各 $4$ 张正面朝上的卡牌和 $1$ 张背面朝上的卡牌。

分给高桥君的卡牌用字符串 $S$ 表示,分给青木君的卡牌用字符串 $T$ 表示。

$S, T$ 是 $5$ 个字符的字符串,前 $4$ 个字符由 1, 2, $\dots$, 9 组成,表示正面朝上的卡牌上写的数字。 最后 $1$ 个字符是 #,表示背面朝上的卡牌。

将 $5$ 张手牌的分值定义为:设 $c_i$ 为该手牌中包含的 $i$ 的张数,则分值为 $\displaystyle \sum_{i=1}^9 i \times 10^{c_i}$。

如果高桥君的手牌分值高于青木君的手牌分值,则高桥君获胜。

求高桥君获胜的概率。

输入格式

输入按以下格式从标准输入给出:

$K$
$S$
$T$

输出格式

用小数输出高桥君获胜的概率。

与期望答案的绝对误差或相对误差不超过 $10^{-5}$ 即判为正确。

样例

2
1144#
2233#

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
9988#
1122#

1.0

6
1122#
2228#

0.001932367149758454

只有当高桥君的手牌为 11222、青木君的手牌为 22281 时高桥君才获胜。

高桥君获胜的概率是 $\frac2{1035}$。

100000
3226#
3597#

0.6296297942426154

数据范围

• $2 \le K \le 10^5$
• $|S| = |T| = 5$
• $S, T$ 的第 $1$ 到第 $4$ 个字符是 1, 2, $\dots$, 9 中的某一个
• 1, 2, $\dots$, 9 分别最多在 $S$ 和 $T$ 中共出现 $K$ 次
• $S, T$ 的第 $5$ 个字符是 #