Один очень состоятельный крот знает только целые неотрицательные числа. Он умеет выполнять на своих счётах три действия:

Каждое утро крот выбирает очередную пару целых чисел x и y, таких что 1 ≤ x < y ≤ 2^l − 1, и в течение дня получает из числа x число y, выполняя на своих счётах некоторую последовательность действий. Крот хорошо умеет считать, поэтому всегда обходится самой короткой последовательностью действий, достаточной для получения числа y из числа x.

Сколько в общей сложности действий на счётах выполнит крот, пока не переберёт все пары чисел в диапазоне от 1 до 2^l − 1?

В единственной строке записано целое число l (2 ≤ l ≤ 10¹⁸).

Найдите количество действий на счётах, которое должен будет выполнить крот, и выведите остаток при делении этого числа на 10⁹ + 7.

В первый день крот получит из числа 1 число 2, выполнив первое действие. Во второй день он получит из числа 1 число 3, выполнив второе действие. В третий день он получит из числа 2 число 3, выполнив сначала третье, а затем второе действие.