H. The first Node bender
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

you already know who made this problem right ;)

You are given an undirected graph with $$$n+2$$$ vertices. The ordinary vertices are numbered from $$$1$$$ to $$$n$$$, and the two special vertices are called $$$x$$$ and $$$y$$$.

There are no edges between two ordinary vertices, and there is no edge between $$$x$$$ and $$$y$$$. The edges incident to the special vertices are described by two binary strings $$$a_x$$$ and $$$a_y$$$:

  • vertex $$$i$$$ is adjacent to $$$x$$$ if and only if $$$a_x[i]=\texttt{1}$$$;
  • vertex $$$i$$$ is adjacent to $$$y$$$ if and only if $$$a_y[i]=\texttt{1}$$$.

A walk of length $$$k$$$ is a sequence of vertices $$$w_0,w_1,\ldots,w_k$$$ such that every two consecutive vertices are connected by an edge. Vertices and edges may occur more than once in a walk.

You must answer $$$q$$$ queries. In a query, you are given two ordinary vertices $$$u$$$ and $$$v$$$, and an integer $$$k$$$. Find the number of different walks of length exactly $$$k$$$ that start at $$$u$$$ and finish at $$$v$$$.

And as the author of this problem is always kinda tired (even though he is the first Node bender), you got to do this mission.

Because the answer can be large, print it modulo $$$10^9+7$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the number of ordinary vertices and the number of queries.

The second line contains a binary string $$$a_x$$$ of length $$$n$$$. Its $$$i$$$-th character is $$$\texttt{1}$$$ if and only if vertex $$$i$$$ is adjacent to $$$x$$$.

The third line contains a binary string $$$a_y$$$ of length $$$n$$$. Its $$$i$$$-th character is $$$\texttt{1}$$$ if and only if vertex $$$i$$$ is adjacent to $$$y$$$.

Each of the next $$$q$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$k$$$ ($$$1 \le u,v \le n$$$, $$$1 \le k \le 10^5$$$) — the starting vertex, the finishing vertex, and the required length of the walk.

Output

For each query, print one integer — the number of walks satisfying the query, modulo $$$10^9+7$$$.

Example
Input
3 5
110
011
1 1 1
1 1 2
1 2 2
2 2 2
2 1 4
Output
0
1
1
2
3
Note

In the example, vertex $$$1$$$ is adjacent only to $$$x$$$, vertex $$$2$$$ is adjacent to both $$$x$$$ and $$$y$$$, and vertex $$$3$$$ is adjacent only to $$$y$$$.

For the query $$$u=2$$$, $$$v=2$$$, $$$k=2$$$, the two walks are $$$$$$ 2\to x\to2 \qquad\text{and}\qquad 2\to y\to2. $$$$$$

For the query $$$u=2$$$, $$$v=1$$$, $$$k=4$$$, the three walks are $$$$$$ 2\to x\to1\to x\to1, $$$$$$ $$$$$$ 2\to x\to2\to x\to1, $$$$$$ and $$$$$$ 2\to y\to2\to x\to1. $$$$$$