J. Message History
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Gold opens his phone for the first time after 25 hours and immediately receives a barrage of messages from his trainer friends inviting him to rematch battles! In Gold's message history, there are $$$m$$$ distinct friends numbered $$$1$$$ to $$$m$$$ who have sent him messages, arranged in a stack. Gold recalls the starting arrangement of his message history on the previous occasion he checked his phone. He thinks the arrangement may have changed, but he's not sure how.

The arrangement of the friends can only change via a transition, which is defined as taking any element from the stack and moving it to the top of the stack. Note that a transition may move an element that was already on the top of the stack back to the top. Assuming there are exactly $$$t$$$ transitions, how many distinct sequences of transitions could have caused the starting arrangement to change into the one Gold is now seeing? Since this number can be large, return the answer modulo $$$10^9+7$$$.

An example of $$$3$$$ transitions moving $$$3$$$, then $$$1$$$, and then $$$3$$$, transforming the starting arrangement $$$123$$$ as follows: $$$123 \to 312 \to 132 \to 312$$$. This is one of the possible transition sequences (that is, $$$[3, 1, 3]$$$) for sample 1.
Input

The first line contains two integers $$$m$$$ and $$$t$$$ $$$(1 \le m, t \le 5000)$$$.

The second line contains $$$m$$$ integers representing the starting arrangement of the elements.

The third line contains $$$m$$$ integers representing the ending arrangement of the elements.

The elements are listed from the top to the bottom of the stack.

Each "arrangement" is a permutation, containing exactly one of each integer in the range $$$[1, m]$$$.

Output

Output the number of distinct $$$t$$$-length transition sequences that can change the starting arrangement to the ending arrangement, modulo $$$10^9+7$$$.

Examples
Input
3 3
1 2 3
3 1 2
Output
5
Input
5 10
1 5 3 2 4
5 4 3 2 1
Output
76630
Note

In sample 1, the following histories of message notifications can take us from the starting arrangement to the ending one: $$$[1, 1, 3]$$$, $$$[1, 3, 3]$$$, $$$[2, 1, 3]$$$, $$$[3, 1, 3]$$$, $$$[3, 3, 3]$$$. The figure in the statement illustrates the sequence $$$[3, 1, 3]$$$.