Fafa and Ancient Alphabet

Ancient Egyptians은 신전의 벽에 글을 쓰기 위해 매우 많은 기호의 집합 을 사용한 것으로 알려져 있다. Fafa and Fifa은 신전 중 하나에 가서, 신전 벽에 하나가 다른 하나의 아래에 적힌 길이가 같은 비어 있지 않은 두 단어 S1 and S2을 발견했다. 이 신전은 매우 오래되었기 때문에 단어의 일부 기호가 지워져 있었다. 집합 의 각 기호는 지워진 임의의 위치에 있을 확률이 서로 같다.

Fifa는 Fafa에게 S1이 S2보다 사전순으로 클 확률을 계산해 보라고 했다. Fafa가 이 과제를 해결하도록 도와줄 수 있는가?

임을 알고 있다. 즉, 이집트인의 알파벳에는 서로 다른 문자 m개가 있었으며, 이 문제에서는 이 문자들을 알파벳 순서에 따라 1부터 m까지의 정수로 나타낸다. 길이가 같은 단어 x와 단어 y에 대해, 어떤 위치까지 두 단어가 같고 그다음 위치에서 단어 x의 문자가 단어 y의 문자보다 크다면 단어 x는 단어 y보다 사전순으로 크다.

이 확률이 어떤 분수 와 같음을 증명할 수 있다. 여기서 P and Q은 서로소인 정수이고, 이다. 정답으로 의 값을 출력한다. 즉, 109 + 7보다 작은 음이 아닌 정수 중 을 만족하는 값을 출력한다. 여기서 은 a와 b를 m으로 나눈 나머지가 같다는 뜻이다.

첫째 줄에 두 정수 n와 m (1 ≤ n, m ≤ 105)가 주어진다. 이는 각각 두 단어 각각의 길이와 알파벳 의 크기이다.

둘째 줄에 n개의 정수 a1, a2, ..., an (0 ≤ ai ≤ m)이 주어지며, 이는 S1의 기호들이다. ai = 0이면 위치 i의 기호가 지워졌다는 뜻이다.

셋째 줄에는 S1과 같은 형식으로 S2을 나타내는 n개의 정수가 주어진다.

P and Q이 서로소이고 가 문제의 정답일 때, 값 을 출력한다.

첫 번째 예제에서 첫 번째 단어는 (1) 또는 (2)로 바뀔 수 있다. 두 번째 선택지만이 이 단어를 두 번째 단어보다 사전순으로 크게 만든다. 따라서 문제의 정답은 , 즉 500000004이다. 그 이유는 이기 때문이다.

두 번째 예제에서는 두 번째 단어의 zero를 무엇으로 대체하더라도 첫 번째 단어를 사전순으로 더 크게 만들 수 없다. 따라서 문제의 정답은 , 즉 0이다.