John discovered a new game. To play this game you need a circle on which $$$k$$$ ($$$k$$$ can be any positive integer) numbers are placed. The player decides at which number he begins his game and is then forced to visit every number on the circle in clockwise order starting from his chosen position. At the beginning of the game, the player's health is $$$0$$$. When he visits a number, that number is added to his health. If at any point the player's health becomes negative, the game is lost.

To test John's understanding of the game, Ana gives him an array of $$$n$$$ integers and a series of $$$q$$$ queries. Each query consists of $$$2$$$ numbers $$$l$$$ and $$$r$$$ and corresponds to the following question: If the circle was filled with the numbers in the subsequence [$$$l$$$, $$$r$$$], would the game be winnable?

Help John answer the queries.

John has a directed acyclic graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Each vertex $$$u$$$, $$$1\leq u\leq n$$$, has a value $$$a_{u}$$$ associated to it.

Let's define the beauty of a simple path $$$P=u_{1}u_{2}...u_{l-1}u_{l}$$$ over the graph $$$G$$$ as: $$$$$$ a_{u_{1}}\& a_{u_{2}}\&...\& a_{u_{l-1}}\& a_{u_{l}}$$$$$$ where $$$\&$$$ denotes the bitwise and operator.

Find the maximal possible beauty of a path $$$P$$$ consisting of exactly $$$k$$$ vertices over the graph $$$G$$$.

John the tractorist is driving his tractor around the fields of his native village.

The field he is currently located on can be described by an $$$n \cdot m$$$ matrix, each cell of which is assigned one of the following characters: '$$$p$$$'-simple dirt, '$$$s$$$'-highway and '$$$a$$$'-arable land.

John must move his tractor from the cell located at the intersection of row $$$y_1, 1\leq y_1 \leq n$$$ and column $$$x_1, 1\leq x_1 \leq m$$$, to the cell $$$y_2, x_2$$$.

It takes John 1 unit of time to pass through a cell with the character '$$$s$$$' assigned to it, 2 units of time to pass through a cell '$$$p$$$' and 3 units of time to pass through a cell '$$$a$$$'.

Driving this far can take a lot of time, so the mayor of the village promised to help John. The mayor can transform at most $$$k$$$ cells of type '$$$p$$$' to cells of type '$$$s$$$'.

Now, John has given you a very important task. You must find the minimal possible time needed for John to drive from cell $$$y_1, x_1$$$ to cell $$$y_2, x_2$$$, considering that the mayor changes the cells in an optimal way.

***Notice that passing the starting cell consumes John's time, and arriving at the destination cell also consumes some of John's time, according to the type of the destination cell.

***Notice that the mayor can change the values of the beginning and destination cells if any of these cells have the value '$$$p$$$' associated with them.

John wants to become the president of Nicolina. We all know that the neighborhood of Nicolina can be viewed as a tree with $$$n$$$ vertices and in each vertice $$$i$$$ lives a person that has the political opinion $$$p_i$$$. To win the election one must be voted by more than $$$\frac{n}{2}$$$ inhabitants that form a continuous path in the tree. John really wants to win so he will choose a political plan $$$x$$$ such that there exists such a path of voters. John will receive a person's vote if and only if $$$x \vert p_i$$$ ($$$x$$$ divides $$$p_i$$$).

The elections are very soon and John needs to start his political campaign. Knowing the political opinions of the inhabitants and the tree that represent Nicolina, John wants to know if there exists a political plan $$$x$$$ such that there exists a continuous path of more than $$$\frac{n}{2}$$$ voters in Nicolina. Of course, John cannot choose $$$x = 1$$$ because the people in the neighborhood will think that he is dishonest.

Since hiring Jonathans is expensive, the city council decided to turn off all the lights.

The city's lights are in the form of a tree of size $$$N$$$. A tree is an undirected graph with exactly one simple path between each pair of vertices.

The lights are to be turned off in order $$$a_1, a_2, ..., a_N$$$, where $$$a_i$$$ $$$(1 \leq i \leq N)$$$ represents the index of the light bulb to be turned off at time $$$i$$$. You have to find, for each $$$i$$$, the maximum length of a simple path consisting only of lit nodes.

* The length of a path is defined as the number of nodes it contains.

John is in the middle of his Operating Systems exam and he just realized that he forgot a command that he needs. To save his grade he decided to randomly type letters in the hopes that he will get some partial score for trying.

The teacher knows the command that John needs for his program to run, so he wonders what is expected number of key strokes after which the necessary comand will be a suffix of the written text.

The expected value can be written in the form $$$\frac{p}{q} $$$. Please output $$$p \cdot q^{-1} \pmod{1000000007} $$$, where $$$q^{-1}$$$ is the modular inverse of $$$q$$$.