Досторические пещеры Эль Толль расположены в Мойя (Барселона). Вы узнали, что в одном из n тайников в пещерах спрятано сокровище. Можно считать, что вероятность найти сокровище в каждом из тайников равна 1 / n.

Вы не можете попасть в пещеру сами, но вы построили робота, который может искать сокровище в пещерах. Каждый день вы можете послать робота обыскать ровно k различных тайников. Если ни в одном из них нет сокровища, то, очевидно, робот вернется ни с чем. В пещерах очень темно, поэтому робот может не найти сокровище, даже если будет обыскивать правильный тайник. Формально, если один из обыскиваемых тайников содержит сокровище, робот найдет его с вероятностью 1 / 2, иначе он вернется ни с чем. Каждый раз, когда робот обыскивает тайник с сокровищем, вероятность его успеха не зависит от всех предыдущих попыток (то есть, вероятность не найти сокровище за x попыток обыскать правильный тайник равна 1 / 2^x).

Каково среднее количество дней, которое понадобится для того, чтобы найти сокровище при оптимальном выборе порядка обыска тайников? Выведите ответ в виде рационального числа по модулю 10⁹ + 7. Формально, пусть ответ имеет вид несократимой дроби P / Q, тогда вам требуется вывести число . Гарантируется, что Q не делится на 10⁹ + 7.