package q462; import java.math.BigInteger; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Test1 { private static BigInteger patternSum = new BigInteger("0"); private static BigInteger RESULT_THEN_DIV = new BigInteger("1000000007"); private static BigInteger BI_ONE = new BigInteger("1"); public static void main(String[] args) { Scanner scaner = new Scanner(System.in); int n = scaner.nextInt(); int k = scaner.nextInt(); List numList = new ArrayList(); for(int i = 0; i < k; i++){ // 3つ目以降を格納 numList.add(scaner.nextLong()); } if(isEnabled(numList, k, n)){ System.out.println(patternSum.remainder(RESULT_THEN_DIV)); }else{ System.out.println(0); } } /** * 受け取った配列が有効か * @param args 整数の文字列の配列 α1 ~ αk の配列 * @param arrLen 配列の長さ k * @param n N * @return true: 有効
false: 無効 */ private static boolean isEnabled(List numList, int arrLen, int n){ // ソートする // Arrays.sort(args); // System.out.println(Arrays.toString(args)); Collections.sort(numList); long large = 0; long small = 0; // 差 long rem; // ORした結果 long orResult; boolean rtn = true; if(arrLen == 0){ // すべてのパターン数を求める patternSum = findPatternsCount((long) Math.pow(2, n) - 1); }else{ // 0と最初の要素の間は何通りあるか求める patternSum = findPatternsCount(numList.get(0)); for(int i = 1; i < arrLen; i++){ large = numList.get(i); small = numList.get(i - 1); rem = large - small; orResult = small | rem; // 1度立ったものが下がっていなければ一致するはず if(large == orResult){ rtn = true; patternSum = patternSum.multiply(findPatternsCount(rem)); }else{ rtn = false; } } // 最後の要素と(2^n - 1)の間は何通りあるか求める rem = (long) Math.pow(2, n) - 1 - large; patternSum = patternSum.multiply(findPatternsCount(rem)); } return rtn; } /** * 差から2つの間のパターン数を求める * @param rem 差 * @return 差の間は何通りか */ private static BigInteger findPatternsCount(long rem){ int upBitSum = 0; BigInteger rtnFact = BI_ONE; if(rem != 0){ // 2進数に変換 String binStr = Long.toBinaryString(rem); int strLen = binStr.length(); for(int i = 0; i < strLen; i++){ // charをintに変換 upBitSum += Character.getNumericValue(binStr.charAt(i)); } rtnFact = getFact(new BigInteger(String.valueOf(upBitSum))); } return rtnFact; } /** * 階乗を求める * @param n 階乗を求めたい値 * @return 階乗 */ private static BigInteger getFact(BigInteger n){ if (n.equals(new BigInteger("0"))) return BI_ONE; else { BigInteger bi = new BigInteger(String.valueOf(n)); return bi.multiply(getFact(bi.subtract(BI_ONE))); } } }