Заскучав от постоянного исследования Луны, Wall-B решил исследовать то, из чего он сделан — двоичные числа. Он взял двоичное число и решил посчитать, сколько раз в нем появлялись разные подстроки длины два. Он хранит эти значения в \(c_{00}\), \(c_{01}\), \(c_{10}\) и \(c_{11}\), описывающих, сколько раз в числе встречаются подстроки 00, 01, 10 и 11, соответственно. Например:
\(10111100 \rightarrow c_{00} = 1, \ c_{01} = 1,\ c_{10} = 2,\ c_{11} = 3\)
\(10000 \rightarrow c_{00} = 3,\ c_{01} = 0,\ c_{10} = 1,\ c_{11} = 0\)
\(10101001 \rightarrow c_{00} = 1,\ c_{01} = 3,\ c_{10} = 3,\ c_{11} = 0\)
\(1 \rightarrow c_{00} = 0,\ c_{01} = 0,\ c_{10} = 0,\ c_{11} = 0\)
Wall-B заметил, что может быть несколько двоичных чисел с одинаковыми \(c_{00}\), \(c_{01}\), \(c_{10}\), \(c_{11}\). Поэтому он хочет посчитать, сколько двоичных чисел из отрезка \([A, B]\) имеют данные \(c_{xy}\). К сожалению, его вычислительная мощность недостаточно сильна для обработки таких больших, интересных ему интервалов. Можете ли вы ему помочь? Поскольку это число может быть большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Выведите одно число, описывающее количество чисел из отрезка \([A, B]\), удовлетворяющих условию, по модулю \(10^9 + 7\).
Примечание
Пример 1: Двоичные числа из отрезка \([10,1001]\) это \(10,11,100,101,110,111,1000,1001\). Только число 110 удовлетворяет данным ограничениям: \(c_{00} = 0, c_{01} = 0, c_{10} = 1, c_{11} = 1\).
Пример 2: Никакое число из этого отрезка не удовлетворяет данным условиям.