# 着目しているグループの最も大きなインデックスが k
# b_k = b, b1 + b2 + … + b_k = m
def calc(b, m, k)
  @memo[b | m << @shift | k << 2 * @shift] ||= begin
    # r はグループの要素数。まず取り得る最小値とする
    r = [m - k * (b - 1), 1].max
    m -= b * r
    k -= r
    denom = @fac[r] * @fac[b] ** r
    sum = 0
    # このループ1周ごとにグループの要素数 r を1ずつふやしていく
    while m >= b do
      sum += (-(-m / k)...b).inject(0) {|s, c| s + calc(c, m, k)} / denom
      m -= b
      k -= 1
      denom *= (r += 1) * @fac[b]
    end
    # グループの要素数が最大値を取る場合
    # 上で説明したように簡単に計算できる
    sum + @num / (denom * @fac[k] * @fac[m]) * k ** m
  end
end
 
# F(n) を文字列で返す
def f(n)
  # 階乗  @fac[k] = k!
  @fac = (1..[n, 10].max).each_with_object([1]) {|k, fc| fc << k * fc.last}
  @num = @fac[n] * @fac[10]
  @memo = {}
  @shift = n.to_s(2).size
  (-(-n / 10)..n).inject(0) {|s, b| s + b * calc(b, n, 10)}.
  to_s.insert(-n - 1, '.').sub(/\.?0*$/, '')
end
 
puts f(6)
puts f(12)
puts f(100)

IyDnnYDnm67jgZfjgabjgYTjgovjgrDjg6vjg7zjg5fjga7mnIDjgoLlpKfjgY3jgarjgqTjg7Pjg4fjg4Pjgq/jgrnjgYwgawojIGJfayA9IGIsIGIxICsgYjIgKyDigKYgKyBiX2sgPSBtCmRlZiBjYWxjKGIsIG0sIGspCiAgQG1lbW9bYiB8IG0gPDwgQHNoaWZ0IHwgayA8PCAyICogQHNoaWZ0XSB8fD0gYmVnaW4KICAgICMgciDjga/jgrDjg6vjg7zjg5fjga7opoHntKDmlbDjgILjgb7jgZrlj5bjgorlvpfjgovmnIDlsI/lgKTjgajjgZnjgosKICAgIHIgPSBbbSAtIGsgKiAoYiAtIDEpLCAxXS5tYXgKICAgIG0gLT0gYiAqIHIKICAgIGsgLT0gcgogICAgZGVub20gPSBAZmFjW3JdICogQGZhY1tiXSAqKiByCiAgICBzdW0gPSAwCiAgICAjIOOBk+OBruODq+ODvOODlzHlkajjgZTjgajjgavjgrDjg6vjg7zjg5fjga7opoHntKDmlbAgciDjgpIx44Ga44Gk44G144KE44GX44Gm44GE44GPCiAgICB3aGlsZSBtID49IGIgZG8KICAgICAgc3VtICs9ICgtKC1tIC8gaykuLi5iKS5pbmplY3QoMCkge3xzLCBjfCBzICsgY2FsYyhjLCBtLCBrKX0gLyBkZW5vbQogICAgICBtIC09IGIKICAgICAgayAtPSAxCiAgICAgIGRlbm9tICo9IChyICs9IDEpICogQGZhY1tiXQogICAgZW5kCiAgICAjIOOCsOODq+ODvOODl+OBruimgee0oOaVsOOBjOacgOWkp+WApOOCkuWPluOCi+WgtOWQiAogICAgIyDkuIrjgafoqqzmmI7jgZfjgZ/jgojjgYbjgavnsKHljZjjgavoqIjnrpfjgafjgY3jgosKICAgIHN1bSArIEBudW0gLyAoZGVub20gKiBAZmFjW2tdICogQGZhY1ttXSkgKiBrICoqIG0KICBlbmQKZW5kCgojIEYobikg44KS5paH5a2X5YiX44Gn6L+U44GZCmRlZiBmKG4pCiAgIyDpmo7kuZcgIEBmYWNba10gPSBrIQogIEBmYWMgPSAoMS4uW24sIDEwXS5tYXgpLmVhY2hfd2l0aF9vYmplY3QoWzFdKSB7fGssIGZjfCBmYyA8PCBrICogZmMubGFzdH0KICBAbnVtID0gQGZhY1tuXSAqIEBmYWNbMTBdCiAgQG1lbW8gPSB7fQogIEBzaGlmdCA9IG4udG9fcygyKS5zaXplCiAgKC0oLW4gLyAxMCkuLm4pLmluamVjdCgwKSB7fHMsIGJ8IHMgKyBiICogY2FsYyhiLCBuLCAxMCl9LgogIHRvX3MuaW5zZXJ0KC1uIC0gMSwgJy4nKS5zdWIoL1wuPzAqJC8sICcnKQplbmQKCnB1dHMgZig2KQpwdXRzIGYoMTIpCnB1dHMgZigxMDAp