«Опять эти задачи про смайлики!» – грустил Серёжа на олимпиаде. Действительно, на этот раз авторы дали бесконечное число задач, пронумерованных натуральными числами (1, 2, 3, ...), и все они были про смайлики. Серёжа много тренировался перед олимпиадой, и выбрал себе лучшую тактику: после задачи с номером x он решает задачу с номером , где – это побитовое исключающее или, а деление производится с округлением вниз. Например, равно 12, тоже равно 12, равно 7.

Серёжа считает задачу с номером x хорошей, если он решит k задач (начиная с x, выбирая их по своей тактике, при этом, возможно он решит некоторые задачи не по одному разу), а (k + 1)-й задачей опять окажется x. Помогите Серёже – для данного k найдите количество хороших задач. Так как ответ может быть большим, выведите его по модулю 10⁹ + 7.