Alice is playing with some stones.

Now there are three numbered heaps of stones. The first of them contains $$$a$$$ stones, the second of them contains $$$b$$$ stones and the third of them contains $$$c$$$ stones.

Each time she can do one of two operations:

1. take one stone from the first heap and two stones from the second heap (this operation can be done only if the first heap contains at least one stone and the second heap contains at least two stones);
2. take one stone from the second heap and two stones from the third heap (this operation can be done only if the second heap contains at least one stone and the third heap contains at least two stones).

She wants to get the maximum number of stones, but she doesn't know what to do. Initially, she has $$$0$$$ stones. Can you help her?

Alice got many presents these days. So she decided to pack them into boxes and send them to her friends.

There are $$$n$$$ kinds of presents. Presents of one kind are identical (i.e. there is no way to distinguish two gifts of the same kind). Presents of different kinds are different (i.e. that is, two gifts of different kinds are distinguishable). The number of presents of each kind, that Alice has is very big, so we can consider Alice has an infinite number of gifts of each kind.

Also, there are $$$m$$$ boxes. All of them are for different people, so they are pairwise distinct (consider that the names of $$$m$$$ friends are written on the boxes). For example, putting the first kind of present into the first box but not into the second box, is different from putting the first kind of present into the second box but not into the first box.

Alice wants to pack presents with the following rules:

• She won't pack more than one present of each kind into the same box, so each box should contain presents of different kinds (i.e. each box contains a subset of $$$n$$$ kinds, empty boxes are allowed);
• For each kind at least one present should be packed into some box.

Now Alice wants to know how many different ways to pack the presents exists. Please, help her and calculate this number. Since the answer can be huge, output it by modulo $$$10^9+7$$$.

See examples and their notes for clarification.

In order to do some research, $$$n^2$$$ labs are built on different heights of a mountain. Let's enumerate them with integers from $$$1$$$ to $$$n^2$$$, such that the lab with the number $$$1$$$ is at the lowest place, the lab with the number $$$2$$$ is at the second-lowest place, $$$\ldots$$$, the lab with the number $$$n^2$$$ is at the highest place.

To transport water between the labs, pipes are built between every pair of labs. A pipe can transport at most one unit of water at a time from the lab with the number $$$u$$$ to the lab with the number $$$v$$$ if $$$u \gt v$$$.

Now the labs need to be divided into $$$n$$$ groups, each group should contain exactly $$$n$$$ labs. The labs from different groups can transport water to each other. The sum of units of water that can be sent from a group $$$A$$$ to a group $$$B$$$ is equal to the number of pairs of labs ($$$u, v$$$) such that the lab with the number $$$u$$$ is from the group $$$A$$$, the lab with the number $$$v$$$ is from the group $$$B$$$ and $$$u \gt v$$$. Let's denote this value as $$$f(A,B)$$$ (i.e. $$$f(A,B)$$$ is the sum of units of water that can be sent from a group $$$A$$$ to a group $$$B$$$).

For example, if $$$n=3$$$ and there are $$$3$$$ groups $$$X$$$, $$$Y$$$ and $$$Z$$$: $$$X = \{1, 5, 6\}, Y = \{2, 4, 9\}$$$ and $$$Z = \{3, 7, 8\}$$$. In this case, the values of $$$f$$$ are equal to:

• $$$f(X,Y)=4$$$ because of $$$5 \rightarrow 2$$$, $$$5 \rightarrow 4$$$, $$$6 \rightarrow 2$$$, $$$6 \rightarrow 4$$$,
• $$$f(X,Z)=2$$$ because of $$$5 \rightarrow 3$$$, $$$6 \rightarrow 3$$$,
• $$$f(Y,X)=5$$$ because of $$$2 \rightarrow 1$$$, $$$4 \rightarrow 1$$$, $$$9 \rightarrow 1$$$, $$$9 \rightarrow 5$$$, $$$9 \rightarrow 6$$$,
• $$$f(Y,Z)=4$$$ because of $$$4 \rightarrow 3$$$, $$$9 \rightarrow 3$$$, $$$9 \rightarrow 7$$$, $$$9 \rightarrow 8$$$,
• $$$f(Z,X)=7$$$ because of $$$3 \rightarrow 1$$$, $$$7 \rightarrow 1$$$, $$$7 \rightarrow 5$$$, $$$7 \rightarrow 6$$$, $$$8 \rightarrow 1$$$, $$$8 \rightarrow 5$$$, $$$8 \rightarrow 6$$$,
• $$$f(Z,Y)=5$$$ because of $$$3 \rightarrow 2$$$, $$$7 \rightarrow 2$$$, $$$7 \rightarrow 4$$$, $$$8 \rightarrow 2$$$, $$$8 \rightarrow 4$$$.

Please, divide labs into $$$n$$$ groups with size $$$n$$$, such that the value $$$\min f(A,B)$$$ over all possible pairs of groups $$$A$$$ and $$$B$$$ ($$$A \neq B$$$) is maximal.

In other words, divide labs into $$$n$$$ groups with size $$$n$$$, such that minimum number of the sum of units of water that can be transported from a group $$$A$$$ to a group $$$B$$$ for every pair of different groups $$$A$$$ and $$$B$$$ ($$$A \neq B$$$) as big as possible.

Note, that the example above doesn't demonstrate an optimal division, but it demonstrates how to calculate the values $$$f$$$ for some division.

If there are many optimal divisions, you can find any.

Alice got a new doll these days. It can even walk!

Alice has built a maze for the doll and wants to test it. The maze is a grid with $$$n$$$ rows and $$$m$$$ columns. There are $$$k$$$ obstacles, the $$$i$$$-th of them is on the cell $$$(x_i, y_i)$$$, which means the cell in the intersection of the $$$x_i$$$-th row and the $$$y_i$$$-th column.

However, the doll is clumsy in some ways. It can only walk straight or turn right at most once in the same cell (including the start cell). It cannot get into a cell with an obstacle or get out of the maze.

More formally, there exist $$$4$$$ directions, in which the doll can look:

1. The doll looks in the direction along the row from the first cell to the last. While moving looking in this direction the doll will move from the cell $$$(x, y)$$$ into the cell $$$(x, y + 1)$$$;
2. The doll looks in the direction along the column from the first cell to the last. While moving looking in this direction the doll will move from the cell $$$(x, y)$$$ into the cell $$$(x + 1, y)$$$;
3. The doll looks in the direction along the row from the last cell to first. While moving looking in this direction the doll will move from the cell $$$(x, y)$$$ into the cell $$$(x, y - 1)$$$;
4. The doll looks in the direction along the column from the last cell to the first. While moving looking in this direction the doll will move from the cell $$$(x, y)$$$ into the cell $$$(x - 1, y)$$$.

Standing in some cell the doll can move into the cell in the direction it looks or it can turn right once. Turning right once, the doll switches it's direction by the following rules: $$$1 \to 2$$$, $$$2 \to 3$$$, $$$3 \to 4$$$, $$$4 \to 1$$$. Standing in one cell, the doll can make at most one turn right.

Now Alice is controlling the doll's moves. She puts the doll in of the cell $$$(1, 1)$$$ (the upper-left cell of the maze). Initially, the doll looks to the direction $$$1$$$, so along the row from the first cell to the last. She wants to let the doll walk across all the cells without obstacles exactly once and end in any place. Can it be achieved?

Alice is playing a game with her good friend, Marisa.

There are $$$n$$$ boxes arranged in a line, numbered with integers from $$$1$$$ to $$$n$$$ from left to right. Marisa will hide a doll in one of the boxes. Then Alice will have $$$m$$$ chances to guess where the doll is. If Alice will correctly guess the number of box, where doll is now, she will win the game, otherwise, her friend will win the game.

In order to win, Marisa will use some unfair tricks. After each time Alice guesses a box, she can move the doll to the neighboring box or just keep it at its place. Boxes $$$i$$$ and $$$i + 1$$$ are neighboring for all $$$1 \leq i \leq n - 1$$$. She can also use this trick once before the game starts.

So, the game happens in this order: the game starts, Marisa makes the trick, Alice makes the first guess, Marisa makes the trick, Alice makes the second guess, Marisa makes the trick, $$$\ldots$$$, Alice makes $$$m$$$-th guess, Marisa makes the trick, the game ends.

Alice has come up with a sequence $$$a_1, a_2, \ldots, a_m$$$. In the $$$i$$$-th guess, she will ask if the doll is in the box $$$a_i$$$. She wants to know the number of scenarios $$$(x, y)$$$ (for all $$$1 \leq x, y \leq n$$$), such that Marisa can win the game if she will put the doll at the $$$x$$$-th box at the beginning and at the end of the game, the doll will be at the $$$y$$$-th box. Help her and calculate this number.

Alice recently found some cactuses growing near her house! After several months, more and more cactuses appeared and soon they blocked the road. So Alice wants to clear them.

A cactus is a connected undirected graph. No edge of this graph lies on more than one simple cycle. Let's call a sequence of different nodes of the graph $$$x_1, x_2, \ldots, x_k$$$ a simple cycle, if $$$k \geq 3$$$ and all pairs of nodes $$$x_1$$$ and $$$x_2$$$, $$$x_2$$$ and $$$x_3$$$, $$$\ldots$$$, $$$x_{k-1}$$$ and $$$x_k$$$, $$$x_k$$$ and $$$x_1$$$ are connected with edges. Edges $$$(x_1, x_2)$$$, $$$(x_2, x_3)$$$, $$$\ldots$$$, $$$(x_{k-1}, x_k)$$$, $$$(x_k, x_1)$$$ lies on this simple cycle.

There are so many cactuses, so it seems hard to destroy them. But Alice has magic. When she uses the magic, every node of the cactus will be removed independently with the probability $$$\frac{1}{2}$$$. When a node is removed, the edges connected to it are also removed.

Now Alice wants to test her magic. She has picked a cactus with $$$n$$$ nodes and $$$m$$$ edges. Let $$$X[S]$$$ (where $$$S$$$ is a subset of the removed nodes) be the number of connected components in the remaining graph after removing nodes of set $$$S$$$. Before she uses magic, she wants to know the variance of random variable $$$X$$$, if all nodes of the graph have probability $$$\frac{1}{2}$$$ to be removed and all $$$n$$$ of these events are independent. By the definition the variance is equal to $$$E[(X - E[X])^2]$$$, where $$$E[X]$$$ is the expected value of $$$X$$$. Help her and calculate this value by modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9 + 7$$$ (a prime number). It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, find such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.