2050. Belarusian scientists managed to recreate dinosaurs from their remains, and now you can safely meet dinosaurs walking around somewhere near Mogilev.

Mogilev Zoo urgently needs two stegosauruses for a grandiose show "Spikes and Tails" in which various animals will take part. There's not much time left, and we need to tame the stegosaurus (luckily, the animals bred by scientists are perfectly trainable).

The organizers did not decide to go somewhere for the stegosauruses, because it is not easy to deliver such animals from another city. So they decided to find stegosaurus near the zoo.

They got lucky! They found $$$n$$$ beautiful stegosaurus, and $$$i$$$th of them had $$$a_i$$$ spikes. Now they had to pick any two to put on a show.

Clearly, the stegosaurses had to look good together. So zoo director Alexandrus wants to choose them so that the number of spikes they have is almost the same. Simply put, he wants to choose such stegosaurses $$$i$$$ and $$$j$$$ that $$$|a_i - a_j|$$$ is minimal.

Here $$$|k|$$$ denotes the modulus of the number $$$k$$$, that is, $$$|k| = k$$$ if $$$k \geq 0$$$, and $$$|k| = -k$$$ otherwise. So, $$$|3| = 3$$$, and $$$|-2| = 2$$$.

Help Alexandrus determine how well he can choose stegosaurus, that is, find the minimal $$$|a_i - a_j|$$$.

In this problem there is a test score, i.e. for each test the points are given independently, and then summed up. Tests are conventionally divided into subtasks, and points are awarded for the completion of all tests of a subtask. The subtasks are given in the following table:

Not so long ago Alexandis watched an interesting program on a well-known TV channel, in which it was said that important historical events occur on palindrome dates. Thus, for example, it was argued that... Wait a minute, what are palindromic dates?

As you know, any date can be represented as $$$DD$$$.$$$MM$$$.$$$Y^*$$$, where DD — is the day number, MM — is the month number, and $$$Y^*$$$ — is the current year number. So, for example, $$$5$$$ of April $$$1690$$$ can be represented as 05.04.1690, and, say, $$$29$$$ of December $$$192$$$ can be represented as 29.12.192. More formally, we can say that the day number is written using two digits, with perhaps zeros to the left if the number is less than ten. Similarly, the month number is written with two digits according to the same rules. The year number is written as a positive integer without leading zeros.

A palindrome is such a string that it reads equally from left to right and from right to left. For example, the string abacaba is a palindrome, but the string aaba is not.

But now how do we check if a date is a palindrome? It's pretty simple. We take the date as a string, remove the dots from the string, and then check to see if the string is a palindrome. So, for example, April 5th, $$$1690$$$ is not a palindrome date because the date representation 05.04.1690 with the dots removed looks like 05041690 and that string is not a palindrome. At the same time, say the twenty-ninth of December $$$192$$$ can be represented as 29.12.192, its representation without dots looks like 2912192, this string is a palindrome, and therefore the date is a palindrome.

In case you're still interested, the show on this TV channel claimed that it was on the palindrome date that people first saw Bigfoot, it was on the palindrome date that our planet was visited by aliens from Nibiru, and so on... There was quite a long list, which, frankly, was irrelevant to the task at hand.

Alexandis wondered: how many palindromic dates have there been since the very first day of our era, that is, since the first of January of the first year?

This problem uses the Gregorian calendar. In other words, a year is considered leap year if its number is divided by $$$4$$$. However, if the year number is divided by $$$100$$$ and not divided by $$$400$$$, then the year is not considered a leap year.

In this problem there is a test score, i.e. for each test the points are given independently, and then summed up. Tests are conventionally divided into subtasks, and points are awarded for the completion of all tests of a subtask. The subtasks are given in the following table:

Alexandrik — a well-known security software developer. Today he thought he'd been hacked, so he decided to update the passwords on all his accounts.

To do that, Alexandrik invented a special hard-to-crack string $$$s$$$, which for some reason consists only of the letters a' and b'. And now he wants to choose the largest «perfectly protected» substring from it, for only it will ensure the safety of his precious personal data. Recall that a substring is a contiguous subsegment of a string. For example, for string ababaaa, string bab is a substring because it lies in that string continuously (ababaaa). At the same time, the string abb is not a substring, because although it enters this string (ababaaa), it does not lie in this string continuously. The string bbb is also not a substring, because it does not lie in this string at all.

A string is called «perfectly protected» if it turns out that every character of this string is different from the corresponding character in its «inverted» version (i.e. a string in which the characters of the original string are written in reverse order). So, for example, the string abaabbab is «perfectly protected» because:

abaabbab

babbaabaaba

are distinct in each character. At the same time, the string aaabaabb is not «perfectly protected», because its «inverted» version (babaabaaa) matches the original string in the third and sixth positions.

So, help Alexandrik find the longest substring of his string, which is «perfectly protected».

In this problem there is a subtask scores. Score for a subtask are counted only if all tests for that subtask are passed. The subtasks are listed in the following table:

Alexander asks you to solve the following problem:

He has an array $$$a$$$ of $$$n$$$ positive integers. Now he wants you to answer $$$q$$$ queries. The $$$i$$$-th query contains two positive integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$). Alexander asks you to find the number of divisors of $$$a_{l_i} \cdot a_{l_i + 1} \cdot \ldots \cdot a_{r_i}$$$, that is, the number of divisors of the product of numbers on the segment $$$[l_i, r_i]$$$.

Since the answers can be very large, print them modulo $$$10^9 + 7$$$.

In this problem there is a subtask scores. Score for a subtask are counted only if all tests for that subtask are passed. The subtasks are listed in the following table: