Несмотря на популярность своего бесконечного отеля, Гилберт решил вместо этого попробовать управлять очень большим конечным отелем.

Чтобы сократить расходы, Гилберт решил питать отель от собственного электрогенератора. Каждый этаж будет отправлять ток на один этаж выше, а самый верхний этаж будет отправлять ток обратно на первый этаж. Таким образом, Гилберт может поставить генератор на любой этаж - он любит свободу выбора - и все равно обеспечить током весь отель.

К сожалению, рабочие неправильно поняли планы постройки отеля. Закончив работу, они сообщили Гилберту, что теперь каждый этаж отправляет ток на другой этаж в случайном порядке. Это ставит под угрозу возможность Гилберта поставить генератор на любой этаж, потому что некоторые этажи могут остаться без света.

Например, рассмотрим диаграмму одного возможного варианта течения тока в трехэтажном отеле:

Если генератор находится на первом этаже, тогда все этажи получат электричество. Однако, если его поставить на второй или третий этаж, то первый этаж останется без света. Заметьте, что каждый этаж может получать ток от любого количества этажей, однако он может отправлять ток только на единственный другой этаж.

Чтобы решить проблему возможного отсутствия электричества, Гилберт решил переложить проводку на минимальном возможном количестве этажей. Переложить проводку на этаже означает изменить, куда он отправляет ток. В рассмотренном выше примере проблему можно решить переложив проводку на втором этаже так, чтобы он отправлял ток на первый этаж вместо третьего.

Пусть F(n) будет суммой минимальных возможных количеств этажей, на которых надо переложить проводку, необходимых для всех возможных схем распределения тока в отеле с n этажами. Например, F(3) = 6, F(8) = 16276736 и F(100) mod 135707531 = 84326147.

Найдите F(12344321) mod 135707531.