스파이

스파이 민겸이는 이웃 나라와의 평화를 위해 $N$일간 임무를 수행한다.

민겸이는 정보 수집과 감시 두 가지 임무를 수행한다. 각 임무는 수족관, 시청, 학교에서 수행할 수 있다. 두 임무는 성격이 크게 다르기 때문에 하루에 한 가지 임무만 수행할 수 있다. 수족관, 시청, 학교는 멀리 떨어져 있어서 하루에 한 장소에서만 임무를 수행할 수 있다. 또한 민겸이는 매일 최소 하나의 임무를 반드시 수행해야 한다.

다시 말해, 민겸이는 하루에 위 표의 6가지 행동 중 하나를 선택해 할 수 있다.

민겸이는 각 장소에서 임무를 수행할 때 임무 완수를 위한 진척도를 얻는다. 그러나 민겸이는 스파이이기 때문에 같은 장소에서 오래 근무하면 사람들의 눈에 띄어 얻을 수 있는 진척도가 낮아진다. 전날 임무를 수행한 장소와 같은 장소를 고르면 그 날은 원래 진척도의 절반만 얻는다. 이때 장소가 같다면 임무가 달라도 얻는 진척도가 원래의 절반이 됨에 유의하자.

민겸이의 기여도는 얻은 진척도의 합이다. 각 장소에서 각 임무를 수행했을 때 얻을 수 있는 진척도가 주어질 때, 민겸이가 $M$ 이상의 기여도를 얻을 수 있는 임무 수행 방법이 몇 가지인지 구하라.

첫째 줄에 민겸이가 임무를 수행하는 총 일수 $N$과 민겸이가 얻고 싶은 최소 기여도 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 민겸이가 정보 수집 임무를 수족관, 시청, 학교에서 수행했을 때 얻을 수 있는 진척도가 순서대로 공백으로 구분되어 주어진다.

셋째 줄에 민겸이가 감시 임무를 수족관, 시청, 학교에서 수행했을 때 얻을 수 있는 진척도가 순서대로 공백으로 구분되어 주어진다.

민겸이가 기여도를 $M$ 이상 얻을 수 있는 임무 수행 방법이 몇 가지인지 출력한다.

답이 매우 커질 수 있으므로, 답을 $10^9 + 7$로 나눈 나머지를 출력한다.

• $1 ≤ N ≤ 10^{12}$
• $1 ≤ M ≤ 25$
• 주어지는 모든 진척도는 $0$ 이상 $10$ 이하의 짝수이다.
• 주어지는 모든 수는 정수이다.