package contest191129; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; // 指スマってきいたんだけどこのゲーム(いろんな名前があるらしい) public class E3 { InputStream is; PrintWriter out; String INPUT = ""; boolean win(int j, int k, int l, int m) { if(j + k == 0)return false; if(j > 0 && l > 0 && m == 0 && j+l == 5)return true; if(j > 0 && m > 0 && l == 0 && j+m == 5)return true; if(k > 0 && l > 0 && m == 0 && k+l == 5)return true; if(k > 0 && m > 0 && l == 0 && k+m == 5)return true; return false; } void solve() { int n = ni(), K = ni(); int[] a = na(4); boolean[][][][] win = new boolean[5][5][5][5]; for(int i = 0;i < 5;i++) { for(int j = 0;j < 5;j++) { for(int k = 0;k < 5;k++) { for(int l = 0;l < 5;l++) { win[i][j][k][l] = win(i, j, k, l); } } } } int[][][][][][] nexsh = new int[5][5][5][5][][]; int[][][][][][] nexsi = new int[5][5][5][5][][]; for(int j = 0;j < 5;j++) { for(int k = 0;k <= j;k++) { for(int l = 0;l < 5;l++) { for(int m = 0;m <= l;m++) { if(j + k == 0)continue; if(l + m == 0)continue; if(win[j][k][l][m])continue; // 必勝ならおわり nexsh[j][k][l][m] = new int[15][]; int p = 0; boolean allose = true; if(j > 0 && l > 0){ int nl = (j+l)%5; if(!win[nl][m][j][k]) { allose = false; nexsh[j][k][l][m][p++] = new int[] {Math.max(nl, m), Math.min(nl, m), j, k}; } } if(j > 0 && m > 0){ int nm = (j+m)%5; if(!win[l][nm][j][k]) { allose = false; nexsh[j][k][l][m][p++] = new int[] {Math.max(l, nm), Math.min(l, nm), j, k}; } } if(k > 0 && l > 0){ int nl = (k+l)%5; if(!win[nl][m][j][k]) { allose = false; nexsh[j][k][l][m][p++] = new int[] {Math.max(nl, m), Math.min(nl, m), j, k}; } } if(k > 0 && m > 0){ int nm = (k+m)%5; if(!win[l][nm][j][k]) { allose = false; nexsh[j][k][l][m][p++] = new int[] {Math.max(l, nm), Math.min(l, nm), j, k}; } } { int s = j+k; for(int t = 0;t <= s;t++) { if(t == j || t == k)continue; if(t >= 5 || s-t >= 5)continue; if(!win(l, m, t, s-t)) { allose = false; nexsh[j][k][l][m][p++] = new int[] {l, m, Math.max(t, s-t), Math.min(t, s-t)}; } } s -= 5; if(s > 0) { // 自滅はしない for(int t = 0;t <= s;t++) { if(!win(l, m, t, s-t)) { allose = false; nexsh[j][k][l][m][p++] = new int[] {l, m, Math.max(t, s-t), Math.min(t, s-t)}; } } } } if(allose) { // 必敗なら取れる手すべてを適当にとる // tr(j, k, l, m, dp[j][k][l][m]); if(j > 0 && l > 0){ int nl = (j+l)%5; nexsh[j][k][l][m][p++] = new int[] {Math.max(nl, m), Math.min(nl, m), j, k}; } if(j > 0 && m > 0){ int nm = (j+m)%5; nexsh[j][k][l][m][p++] = new int[] {Math.max(l, nm), Math.min(l, nm), j, k}; } if(k > 0 && l > 0){ int nl = (k+l)%5; nexsh[j][k][l][m][p++] = new int[] {Math.max(nl, m), Math.min(nl, m), j, k}; } if(k > 0 && m > 0){ int nm = (k+m)%5; nexsh[j][k][l][m][p++] = new int[] {Math.max(l, nm), Math.min(l, nm), j, k}; } { int s = j+k; for(int t = 0;t <= s;t++) { if(t == j || t == k)continue; if(t >= 5 || s-t >= 5)continue; nexsh[j][k][l][m][p++] = new int[] {l, m, Math.max(t, s-t), Math.min(t, s-t)}; } s -= 5; if(s > 0) { for(int t = 0;t <= s;t++) { nexsh[j][k][l][m][p++] = new int[] {l, m, Math.max(t, s-t), Math.min(t, s-t)}; } } } } nexsh[j][k][l][m] = Arrays.copyOf(nexsh[j][k][l][m], p); // tr(j, k, l, m, nexsh[j][k][l][m]); } } } } for(int j = 0;j < 5;j++) { for(int k = 0;k <= j;k++) { for(int l = 0;l < 5;l++) { for(int m = 0;m <= l;m++) { if(j + k == 0)continue; if(l + m == 0)continue; nexsi[j][k][l][m] = new int[15][]; int p = 0; if(j > 0 && l > 0){ int nl = (j+l)%5; nexsi[j][k][l][m][p++] = new int[] {Math.max(nl, m), Math.min(nl, m), j, k}; } if(j > 0 && m > 0){ int nm = (j+m)%5; nexsi[j][k][l][m][p++] = new int[] {Math.max(l, nm), Math.min(l, nm), j, k}; } if(k > 0 && l > 0){ int nl = (k+l)%5; nexsi[j][k][l][m][p++] = new int[] {Math.max(nl, m), Math.min(nl, m), j, k}; } if(k > 0 && m > 0){ int nm = (k+m)%5; nexsi[j][k][l][m][p++] = new int[] {Math.max(l, nm), Math.min(l, nm), j, k}; } { int s = j+k; for(int t = 0;t <= s;t++) { if(t == j || t == k)continue; if(t >= 5 || s-t >= 5)continue; nexsi[j][k][l][m][p++] = new int[] {l, m, Math.max(t, s-t), Math.min(t, s-t)}; } s -= 5; if(s > 0) { for(int t = 0;t <= s;t++) { nexsi[j][k][l][m][p++] = new int[] {l, m, Math.max(t, s-t), Math.min(t, s-t)}; } } } nexsi[j][k][l][m] = Arrays.copyOf(nexsi[j][k][l][m], p); // if(j == 0)tr(j, k, l, m, nexsi[j][k][l][m]); } } } } int[][][][] dp = new int[5][5][5][5]; if(a[0] < a[1]) {int d = a[0]; a[0] = a[1]; a[1] = d;} if(a[2] < a[3]) {int d = a[2]; a[2] = a[3]; a[3] = d;} if(n == 0) { dp[a[0]][a[1]][a[2]][a[3]] = 1; if(K % 2 == 0)K--; }else { dp[a[2]][a[3]][a[0]][a[1]] = 1; if(K % 2 == 1)K--; } long ans = 0; int mod = 1000000007; for(int i = 0;i <= K;i++) { for(int j = 0;j < 5;j++) { for(int k = 0;k <= j;k++) { if(((n^i)&1) == 1){ ans += dp[0][0][j][k]; } dp[0][0][j][k] = 0; } } if(i == K)break; int[][][][] ndp = new int[5][5][5][5]; if(((n^i)&1) == 1){ // hasitaka for(int j = 0;j < 5;j++) { for(int k = 0;k <= j;k++) { for(int l = 0;l < 5;l++) { for(int m = 0;m <= l;m++) { if(dp[j][k][l][m] == 0)continue; if(nexsh[j][k][l][m] == null)continue; for(int[] ne : nexsh[j][k][l][m]) { ndp[ne[0]][ne[1]][ne[2]][ne[3]] += dp[j][k][l][m]; if(ndp[ne[0]][ne[1]][ne[2]][ne[3]] >= mod)ndp[ne[0]][ne[1]][ne[2]][ne[3]] -= mod; } } } } } }else { // iot for(int j = 0;j < 5;j++) { for(int k = 0;k <= j;k++) { for(int l = 0;l < 5;l++) { for(int m = 0;m <= l;m++) { if(dp[j][k][l][m] == 0)continue; if(nexsi[j][k][l][m] == null)continue; for(int[] ne : nexsi[j][k][l][m]) { ndp[ne[0]][ne[1]][ne[2]][ne[3]] += dp[j][k][l][m]; if(ndp[ne[0]][ne[1]][ne[2]][ne[3]] >= mod)ndp[ne[0]][ne[1]][ne[2]][ne[3]] -= mod; } } } } } } dp = ndp; } out.println(ans%mod); } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new E3().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }