Задача 847
Джек и боб

Перед Джеком находятся три тарелки. У великана есть $N$ бобов, которые он распределяет между тремя тарелками. Все бобы выглядят одинаково, но среди них есть один магический боб. Джек не знает, который боб магический, но великану это известно.

Джек может задавать великану вопросы вида "Содержит ли это подмножество бобов магический боб?" Для каждого вопроса Джек может выбрать любое подмножество бобов из одной тарелки, и великан всегда ответит ему правдиво.

Если на трех тарелках лежат $a$, $b$ и $c$ бобов соответственно, определим $h(a, b, c)$ как наименьшее количество вопросов, которые должен задать Джек, чтобы гарантированно найти магический боб. Например, $h(1, 2, 3) = 3$ и $h(2, 3, 3) = 4$.

Пусть $H(N)$ будет суммой $h(a, b, c)$ по всем тройкам неотрицательных целых чисел $a$, $b$, $c$ при $1 \leq a + b + c \leq N$.
Известно, что $H(6) = 203$ и $H(20) = 7718$.

Репьюнит $R_n$ - это $n$-значное число, состоящее исключительно из цифр '1'. Например, $R_3 = 111$ и $H(R_3) = 1634144$.

Найдите $H(R_{19})$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net