---

Problem 847

---

Jack’s Bean

Jack has three plates in front of him. The giant has $N$ beans that he distributes to the three plates. All the beans look the same, but one of them is a magic bean. Jack doesn’t know which one it is, but the giant knows.

Jack can ask the giant questions of the form: “Does this subset of the beans contain the magic bean?” In each question Jack may choose any subset of beans from a single plate, and the giant will respond truthfully.

If the three plates contain $a$, $b$ and $c$ beans respectively, we let $h(a, b, c)$ be the minimal number of questions Jack needs to ask in order to guarantee he locates the magic bean. For example, $h(1, 2, 3) = 3$ and $h(2, 3, 3) = 4$.

Let $H(N)$ be the sum of $h(a, b, c)$ over all triples of non-negative integers $a$, $b$, $c$ with $1 \leq a + b + c \leq N$.

You are given: $H(6) = 203$ and $H(20) = 7718$.

A repunit, $R_n$, is a number made up with $n$ digits all ‘$1$’. For example, $R_3 = 111$ and $H(R_3) = 1634144$.

Find $H(R_{19})$. Give your answer modulo $1\ 000\ 000\ 007$.

---

杰克的魔法豆子

杰克面前有三个盘子，巨人将$N$颗豆子分在三个盘子中。这些豆子看起来都一样，但其中有一颗是魔法豆子。杰克不知道哪一颗才是魔法豆子，但巨人知道。

杰克可以从任意一个盘子中选择任意一部分豆子，并向巨人提问：“在这些豆子中有魔法豆子吗？”巨人总是如实回答。

若三个盘子中分别由$a$、$b$、$c$颗豆子，记$h(a, b, c)$为杰克能够保证找到魔法豆子最少需要提问的次数。例如，$h(1, 2, 3) = 3$，$h(2, 3, 3) = 4$。

记$H(N)$为所有满足$1\le a+b+c \le N$的非负整数三元组$a$、$b$、$c$对应的$h(a,b,c)$之和。

已知：$H(6) = 203$，$H(20) = 7718$。

循环单位数$R_n$是指由$n$个数字$1$组成的数。例如，$R_3 = 111$，$H(R_3) = 1634144$。

求$H(R_{19})$，并将你的答案对$1\ 000\ 000\ 007$取余。

---