Василий совсем недавно узнал об удивительных свойствах числа π. В одной из статей, которые он прочитал, была высказана гипотеза, что, какую бы последовательность цифр мы не взяли, рано или поздно эта последовательность встретится среди знаков числа π. Таким образом, если взять, например, роман «Война и мир», и закодировать его произвольным образом с помощью цифр, то мы обязательно найдем роман среди знаков числа π.
Василий был просто восхищен этим, поскольку это означает, что все книги, песни и программы уже написаны и зашифрованы в знаках числа π. Василия, конечно, немного насторожило то, что это только гипотеза, поэтому он решил проверить ее самостоятельно.
Для этого Василий скачал из интернета архив с последовательностью знаков числа π с некоторой позиции, и стал проверять разные строки из цифр на наличие в скачанном архиве. Короткие строки цифр Василий находил быстро, но когда он брал длинные строчки, оказывалось, что их в архиве нет. Василий решил взять за определение, что строка длины d встречается наполовину, если в ней есть подстрока длины хотя бы 
, которая есть в архиве.
Для полноты картины Василий взял 2 больших числа x, y (x ≤ y), имеющих одинаковое количество цифр в десятичной записи, и теперь хочет найти количество чисел, находящихся в отрезке от x до y, которые встречаются в архиве наполовину. Помогите Василию вычислить остаток от деления этого значения на 109 + 7.