Хранители в опасности, и Доктор Манхэттен со своим другом Дэниелом Драйбергом должны срочно их предупредить. Всего в команде хранителей n человек, i -й из которых находится в точке плоскости с координатами ( x _i , y _i ) .

Как всем известно, доктор Манхэттен вычисляет расстояние между двумя хранителями i и j по формуле | x _i - x _j | + | y _i - y _j | . Дэниел, как обычный человек, считает, что расстояние равно .

Сейчас успех операции зависит от того, сколько существует пар ( i , j ) ( 1 ≤ i < j ≤ n ), таких что расстояние между хранителем i и хранителем j , вычисленное Доктором Манхэттеном, равняется расстоянию между ними, вычисленному Дэниелом. Вычислить эту величину попросили именно вас.

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

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