Submission #19559728


Source Code Expand

Copy
import java.io.EOFException;
import java.io.File;
import java.io.FileDescriptor;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.UncheckedIOException;
import java.lang.ArithmeticException;
import java.lang.AutoCloseable;
import java.lang.Class;
import java.lang.Double;
import java.lang.Exception;
import java.lang.IllegalAccessException;
import java.lang.Integer;
import java.lang.Long;
import java.lang.Math;
import java.lang.NoSuchFieldException;
import java.lang.NumberFormatException;
import java.lang.Object;
import java.lang.SecurityException;
import java.lang.String;
import java.lang.System;
import java.lang.invoke.CallSite;
import java.lang.invoke.LambdaMetafactory;
import java.lang.invoke.MethodHandle;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.MethodType;
import java.lang.reflect.Field;
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.Charset;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.OptionalLong;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;


public class Main {
    public static void main(String[] args) throws Exception {
        ExtendedScanner sc = new ExtendedScanner();
        FastPrintStream pw = new FastPrintStream();
        solve(sc, pw);
        sc.close();
        pw.flush();
        pw.close();
    }

    static final ModArithmetic ma = ModArithmetic1000000007.INSTANCE;
    static final int max = 100000;

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = sc.ints(n);
        int[] cnt = new int[max + 1];
        for (int e : a) cnt[e]++;
        int m = 0;
        for (int c : cnt) if (c > 0) m++;
        int[] x = new int[m];
        for (int i = 0, j = 0; i <= max; i++) {
            if (cnt[i] > 0) x[j++] = i;
        }
        long[] pow = ma.rangePower(2, n);
        long[] pdp = new long[1 << 17];
        long[] cdp = new long[1 << 17];
        pdp[0] = 1;
        for (int i = 0; i < m; i++) {
            int val = x[i];
            long p = pow[cnt[val] - 1];
            for (int j = 0; j < 1 << 17; j++) {
                cdp[j] = ma.mul(ma.add(pdp[j], pdp[j ^ val]), p);
            }
            long[] tmp = pdp; pdp = cdp; cdp = tmp;
        }
        pw.println(pdp[k]);
    }
}

class Const {
    public static final long   LINF   = 1L << 59;
    public static final int    IINF   = (1  << 30) - 1;
    public static final double DINF   = 1e150;
    
    public static final double SMALL  = 1e-12;
    public static final double MEDIUM = 1e-9;
    public static final double LARGE  = 1e-6;

    public static final long MOD1000000007 = 1000000007;
    public static final long MOD998244353  = 998244353 ;
    public static final long MOD754974721  = 754974721 ;
    public static final long MOD167772161  = 167772161 ;
    public static final long MOD469762049  = 469762049 ;

    public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1};
    public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1};
    public static final int[] dx4 = {1, 0, -1, 0};
    public static final int[] dy4 = {0, 1, 0, -1};
}


/**
 * @author https://atcoder.jp/users/suisen
 */
final class ExtendedScanner extends FastScanner {
    public ExtendedScanner() {super();}
    public ExtendedScanner(InputStream in) {super(in);}
    public int[] ints(final int n) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> nextInt());
        return a;
    }
    public int[] ints(final int n, final IntUnaryOperator f) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
        return a;
    }
    public int[][] ints(final int n, final int m) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m));
        return a;
    }
    public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m, f));
        return a;
    }
    public long[] longs(final int n) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> nextLong());
        return a;
    }
    public long[] longs(final int n, final LongUnaryOperator f) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
        return a;
    }
    public long[][] longs(final int n, final int m) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m));
        return a;
    }
    public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m, f));
        return a;
    }
    public char[][] charArrays(final int n) {
        final char[][] c = new char[n][];
        Arrays.setAll(c, $ -> nextChars());
        return c;
    }
    public double[] doubles(final int n) {
        final double[] a = new double[n];
        Arrays.setAll(a, $ -> nextDouble());
        return a;
    }
    public double[][] doubles(final int n, final int m) {
        final double[][] a = new double[n][];
        Arrays.setAll(a, $ -> doubles(m));
        return a;
    }
    public String[] strings(final int n) {
        final String[] s = new String[n];
        Arrays.setAll(s, $ -> next());
        return s;
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
class FastPrintStream implements AutoCloseable {
    private static final int INT_MAX_LEN = 11;
    private static final int LONG_MAX_LEN = 20;

    private int precision = 9;

    private static final int BUF_SIZE = 1 << 14;
    private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
    private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
    private final byte[] buf = new byte[BUF_SIZE];
    private int ptr = 0;
    private final Field strField;
    private final CharsetEncoder encoder;

    private final OutputStream out;

    public FastPrintStream(OutputStream out) {
        this.out = out;
        Field f;
        try {
            f = String.class.getDeclaredField("value");
            f.setAccessible(true);
        } catch (NoSuchFieldException | SecurityException e) {
            f = null;
        }
        this.strField = f;
        this.encoder = StandardCharsets.US_ASCII.newEncoder();
    }

    public FastPrintStream(File file) throws IOException {
        this(new FileOutputStream(file));
    }

    public FastPrintStream(String filename) throws IOException {
        this(new File(filename));
    }

    public FastPrintStream() {
        this(new FileOutputStream(FileDescriptor.out));
    }

    public FastPrintStream println() {
        if (ptr == BUF_SIZE) internalFlush();
        buf[ptr++] = (byte) '\n';
        return this;
    }

    public FastPrintStream println(Object o) {
        return print(o).println();
    }

    public FastPrintStream println(String s) {
        return print(s).println();
    }

    public FastPrintStream println(char[] s) {
        return print(s).println();
    }

    public FastPrintStream println(char c) {
        return print(c).println();
    }

    public FastPrintStream println(int x) {
        return print(x).println();
    }

    public FastPrintStream println(long x) {
        return print(x).println();
    }

    public FastPrintStream println(double d, int precision) {
        return print(d, precision).println();
    }

    public FastPrintStream println(double d) {
        return print(d).println();
    }

    private FastPrintStream print(byte[] bytes) {
        int n = bytes.length;
        if (ptr + n > BUF_SIZE) {
            internalFlush();
            try {
                out.write(bytes);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        } else {
            System.arraycopy(bytes, 0, buf, ptr, n);
            ptr += n;
        }
        return this;
    }

    public FastPrintStream print(Object o) {
        return print(o.toString());
    }

    public FastPrintStream print(String s) {
        if (strField == null) {
            return print(s.getBytes());
        } else {
            try {
                Object value = strField.get(s);
                if (value instanceof byte[]) {
                    return print((byte[]) value);
                } else {
                    return print((char[]) value);
                }
            } catch (IllegalAccessException e) {
                return print(s.getBytes());
            }
        }
    }

    public FastPrintStream print(char[] s) {
        try {
            return print(encoder.encode(CharBuffer.wrap(s)).array());
        } catch (CharacterCodingException e) {
            byte[] bytes = new byte[s.length];
            for (int i = 0; i < s.length; i++) {
                bytes[i] = (byte) s[i];
            }
            return print(bytes);
        }
    }

    public FastPrintStream print(char c) {
        if (ptr == BUF_SIZE) internalFlush();
        buf[ptr++] = (byte) c;
        return this;
    }

    public FastPrintStream print(int x) {
        if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
        if (-10 < x && x < 10) {
            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            buf[ptr++] = (byte) ('0' + x);
            return this;
        }
        int d;
        if (x < 0) {
            if (x == Integer.MIN_VALUE) {
                buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
                buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
                buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
                return this;
            }
            d = len(x = -x);
            buf[ptr++] = '-';
        } else {
            d = len(x);
        }
        int j = ptr += d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(long x) {
        if ((int) x == x) return print((int) x);
        if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
        int d;
        if (x < 0) {
            if (x == Long.MIN_VALUE) {
                buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
                buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
                buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
                buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
                buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
                return this;
            }
            d = len(x = -x);
            buf[ptr++] = '-';
        } else {
            d = len(x);
        }
        int j = ptr += d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(double d, int precision) {
        if (d < 0) {
            print('-');
            d = -d;
        }
        d += Math.pow(10, -precision) / 2;
        print((long) d).print('.');
        d -= (long) d;
        for(int i = 0; i < precision; i++){
            d *= 10;
            print((int) d);
            d -= (int) d;
        }
        return this;
    }

    public FastPrintStream print(double d) {
        return print(d, precision);
    }

    public void setPrecision(int precision) {
        this.precision = precision;
    }

    private void internalFlush() {
        try {
            out.write(buf, 0, ptr);
            ptr = 0;
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    public void flush() {
        try {
            out.write(buf, 0, ptr);
            out.flush();
            ptr = 0;
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    public void close() {
        try {
            out.close();
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    private static int len(int x) {
        return
            x >= 1000000000 ? 10 :
            x >= 100000000  ?  9 :
            x >= 10000000   ?  8 :
            x >= 1000000    ?  7 :
            x >= 100000     ?  6 :
            x >= 10000      ?  5 :
            x >= 1000       ?  4 :
            x >= 100        ?  3 :
            x >= 10         ?  2 : 1;
    }

    private static int len(long x) {
        return
            x >= 1000000000000000000L ? 19 :
            x >= 100000000000000000L ? 18 :
            x >= 10000000000000000L ? 17 :
            x >= 1000000000000000L ? 16 :
            x >= 100000000000000L ? 15 :
            x >= 10000000000000L ? 14 :
            x >= 1000000000000L ? 13 :
            x >= 100000000000L ? 12 :
            x >= 10000000000L ? 11 : 10;
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
class FastScanner implements AutoCloseable {
    private final ByteBuffer tokenBuf = new ByteBuffer();
    public final InputStream in;
    private final byte[] rawBuf = new byte[1 << 14];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(InputStream in) {
        this.in = in;
    }

    public FastScanner() {
        this(new FileInputStream(FileDescriptor.in));
    }

    private int readByte() {
        if (ptr < buflen) return rawBuf[ptr++];
        ptr = 0;
        try {
            buflen = in.read(rawBuf);
            if (buflen > 0) {
                return rawBuf[ptr++];
            } else {
                throw new EOFException();
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    private int readByteUnsafe() {
        if (ptr < buflen) return rawBuf[ptr++];
        ptr = 0;
        try {
            buflen = in.read(rawBuf);
            if (buflen > 0) {
                return rawBuf[ptr++];
            } else {
                return -1;
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    private int skipUnprintableChars() {
        int b = readByte();
        while (b <= 32 || b >= 127) b = readByte();
        return b;
    }

    private void loadToken() {
        tokenBuf.clear();
        for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {
            tokenBuf.append(b);
        }
    }

    public final boolean hasNext() {
        for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {
            if (b == -1) return false;
        }
        --ptr;
        return true;
    }

    public final String next() {
        loadToken();
        return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
    }

    public final String nextLine() {
        tokenBuf.clear();
        for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {
            if (b == -1) break;
            tokenBuf.append(b);
        }
        return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
    }

    public final char nextChar() {
        return (char) skipUnprintableChars();
    }

    public final char[] nextChars() {
        loadToken();
        return tokenBuf.toCharArray();
    }

    public final long nextLong() {
        long n = 0;
        boolean isNegative = false;
        int b = skipUnprintableChars();
        if (b == '-') {
            isNegative = true;
            b = readByteUnsafe();
        }
        if (b < '0' || '9' < b) throw new NumberFormatException();
        while ('0' <= b && b <= '9') {
            // -9223372036854775808 - 9223372036854775807
            if (n >= 922337203685477580L) {
                if (n > 922337203685477580L) {
                    throw new ArithmeticException("long overflow");
                }
                if (isNegative) {
                    if (b >= '9') {
                        throw new ArithmeticException("long overflow");
                    }
                    n = -n - (b + '0');
                } else {
                    if (b >= '8') {
                        throw new ArithmeticException("long overflow");
                    }
                    n = n * 10 + b - '0';
                }
                b = readByteUnsafe();
                if ('0' <= b && b <= '9') {
                    throw new ArithmeticException("long overflow");
                } else if (b <= 32 || b >= 127) {
                    return n;
                } else {
                    throw new NumberFormatException();
                }
            }
            n = n * 10 + b - '0';
            b = readByteUnsafe();
        }
        if (b <= 32 || b >= 127) return isNegative ? -n : n;
        throw new NumberFormatException();
    }
    public final int nextInt() {
        long value = nextLong();
        if ((int) value != value) {
            throw new ArithmeticException("int overflow");
        }
        return (int) value;
    }
    public final double nextDouble() {
        return Double.parseDouble(next());
    }
    public final void close() {
        try {
            in.close();
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    @SuppressWarnings("UnusedReturnValue")
    private static final class ByteBuffer {
        private static final int DEFAULT_BUF_SIZE = 1 << 12;
        private byte[] buf;
        private int ptr = 0;
        private ByteBuffer(@SuppressWarnings("SameParameterValue") int capacity) {
            this.buf = new byte[capacity];
        }
        private ByteBuffer() {
            this(DEFAULT_BUF_SIZE);
        }
        private ByteBuffer append(int b) {
            if (ptr == buf.length) {
                int newLength = buf.length << 1;
                byte[] newBuf = new byte[newLength];
                System.arraycopy(buf, 0, newBuf, 0, buf.length);
                buf = newBuf;
            }
            buf[ptr++] = (byte) b;
            return this;
        }
        private char[] toCharArray() {
            char[] chs = new char[ptr];
            for (int i = 0; i < ptr; i++) {
                chs[i] = (char) buf[i];
            }
            return chs;
        }
        private byte[] getRawBuf() {
            return buf;
        }
        private int size() {
            return ptr;
        }
        private void clear() {
            ptr = 0;
        }
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
abstract class ModArithmetic {
    public abstract long getMod();
    public abstract long mod(long a);
    public abstract long add(long a, long b);
    public abstract long sub(long a, long b);
    public abstract long mul(long a, long b);
    public final long div(long a, long b) {return mul(a, inv(b));}
    public final long inv(long a) {
        a = mod(a);
        long b = getMod();
        long u = 1, v = 0;
        while (b >= 1) {
            long t = a / b;
            a -= t * b;
            long tmp1 = a; a = b; b = tmp1;
            u -= t * v;
            long tmp2 = u; u = v; v = tmp2;
        }
        if (a != 1) throw new ArithmeticException("divide by zero");
        return mod(u);
    }
    public final long fma(long a, long b, long c) {return add(mul(a, b), c);}
    public final long pow(long a, long b) {
        long pow = 1;
        for (a = mod(a); b > 0; b >>= 1, a = mul(a, a)) {
            if ((b & 1) == 1) pow = mul(pow, a);
        }
        return pow;
    }

    public final long add(long a, long b, long c) {return mod(a + b + c);}
    public final long add(long a, long b, long c, long d) {return mod(a + b + c + d);}
    public final long add(long a, long b, long c, long d, long e) {return mod(a + b + c + d + e);}
    public final long add(long a, long b, long c, long d, long e, long f) {return mod(a + b + c + d + e + f);}
    public final long add(long a, long b, long c, long d, long e, long f, long g) {return mod(a + b + c + d + e + f + g);}
    public final long add(long a, long b, long c, long d, long e, long f, long g, long h) {return mod(a + b + c + d + e + f + g + h);}
    public final long add(long... xs) {long s = 0; for (long x : xs) s += x; return mod(s);}
    public final long mul(long a, long b, long c) {return mul(a, mul(b, c));}
    public final long mul(long a, long b, long c, long d) {return mul(a, mul(b, mul(c, d)));}
    public final long mul(long a, long b, long c, long d, long e) {return mul(a, mul(b, mul(c, mul(d, e))));}
    public final long mul(long a, long b, long c, long d, long e, long f) {return mul(a, mul(b, mul(c, mul(d, mul(e, f)))));}
    public final long mul(long a, long b, long c, long d, long e, long f, long g) {return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, g))))));}
    public final long mul(long a, long b, long c, long d, long e, long f, long g, long h) {return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, mul(g, h)))))));}
    public final long mul(long... xs) {long s = 1; for (long x : xs) s = mul(s, x); return s;}
    /**
     * @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
     */
    public final long[] gcdInv(long a) {
        final long m = getMod();
        a = mod(a);
        if (a == 0) return new long[]{m, 0};
        long s = m, t = a;
        long m0 = 0, m1 = 1;
        while (t > 0) {
            long u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            long tmp;
            tmp = s; s = t; t = tmp;
            tmp = m0; m0 = m1; m1 = tmp;
        }
        if (m0 < 0) m0 += m / s;
        return new long[]{s, m0};
    }
    public final OptionalLong sqrt(long a) {
        a = mod(a);
        if (a == 0) return OptionalLong.of(0);
        if (a == 1) return OptionalLong.of(1);
        long p = getMod();
        if (pow(a, (p - 1) >> 1) != 1) {
            return OptionalLong.empty();
        }
        if ((p & 3) == 3) {
            return OptionalLong.of(pow(a, (p + 1) >> 2));
        }
        if ((p & 7) == 5) {
            if (pow(a, (p - 1) >> 2) == 1) {
                return OptionalLong.of(pow(a, (p + 3) >> 3));
            } else {
                return OptionalLong.of(mul(pow(2, (p - 1) >> 2), pow(a, (p + 3) >> 3)));
            }
        }
        long S = 0, Q = p - 1;
        while ((Q & 1) == 0) {
            ++S;
            Q >>= 1;
        }
        long z = 1;
        while (pow(z, (p - 1) >> 1) != p - 1) ++z;
        long c = pow(z, Q), R = pow(a, (Q + 1) / 2), t = pow(a, Q), M = S;
        while (t != 1) {
            long cur = t;
            int i;
            for (i = 1; i < M; i++) {
                cur = mul(cur, cur);
                if (cur == 1) break;
            }
            long b = pow(c, 1L << (M - i - 1));
            c = mul(b, b); R = mul(R, b); t = mul(t, b, b); M = i;
        }
        return OptionalLong.of(R);
    }

    public final int primitiveRoot() {
        final int m = Math.toIntExact(getMod());
        if (m == 2) return 1;
        if (m == 167772161) return 3;
        if (m == 469762049) return 3;
        if (m == 754974721) return 11;
        if (m == 998244353) return 3;
        int[] divs = new int[20];
        divs[0] = 2;
        int cnt = 1;
        int x = (m - 1) / 2;
        while (x % 2 == 0) x /= 2;
        for (int i = 3; (long) i * i <= x; i += 2) {
            if (x % i == 0) {
                divs[cnt++] = i;
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) {
            divs[cnt++] = x;
        }
        for (int g = 2; ; g++) {
            boolean ok = true;
            for (int i = 0; i < cnt; i++) {
                if (pow(g, (m - 1) / divs[i]) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return g;
        }
    }

    /** array operations */

    public final long[] rangeInv(int n) {
        final long MOD = getMod();
        long[] invs = new long[n + 1];
        if (n == 0) return invs;
        invs[1] = 1;
        for (int i = 2; i <= n; i++) {
            invs[i] = mul(MOD - MOD / i, invs[(int) (MOD % i)]);
        }
        return invs;
    }
    public final long[] arrayInv(long[] a) {
        int n = a.length;
        long[] l = new long[n + 1];
        long[] r = new long[n + 1];
        l[0] = r[n] = 1;
        for (int i = 0; i < n; i++) l[i + 1] = mul(l[i], a[i    ]);
        for (int i = n; i > 0; i--) r[i - 1] = mul(r[i], a[i - 1]);
        long invAll = inv(l[n]);
        long[] invs = new long[n];
        for (int i = 0; i < n; i++) {
            invs[i] = mul(l[i], r[i + 1], invAll);
        }
        return invs;
    }
    public final long[] factorial(int n) {
        long[] ret = new long[n + 1];
        ret[0] = 1;
        for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], i);
        return ret;
    }
    public final long[] factorialInv(int n) {
        long facN = 1;
        for (int i = 2; i <= n; i++) facN = mul(facN, i);
        long[] invs = new long[n + 1];
        invs[n] = inv(facN);
        for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], i);
        return invs;
    }
    public final long[] rangePower(long a, int n) {
        a = mod(a);
        long[] pows = new long[n + 1];
        pows[0] = 1;
        for (int i = 1; i <= n; i++) pows[i] = mul(pows[i - 1], a);
        return pows;
    }
    public final long[] rangePowerInv(long a, int n) {
        a = mod(a);
        long[] invs = new long[n + 1];
        invs[n] = inv(pow(a, n));
        for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], a);
        return invs;
    }

    /** combinatric operations */

    public final long[][] combTable(int n) {
        long[][] comb = new long[n + 1][];
        for (int i = 0; i <= n; i++) {
            comb[i] = new long[i + 1];
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; j++) {
                comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]);
            }
        }
        return comb;
    }
    public final long naiveComb(long n, int r) {
        if (r < 0 || r > n) return 0;
        long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = mul(num, mod(n - i));
            den = mul(den, i + 1);
        }
        return div(num, den);
    }
    public final long naivePerm(long n, long r) {
        if (r < 0 || r > n) return 0;
        long res = 1;
        for (long i = 0; i < r; i++) res = mul(res, n - i);
        return res;
    }
    public final long naiveFactorial(int n) {
        return naivePerm(n, n);
    }
}

final class ModArithmetic1000000007 extends ModArithmetic {
    public static final ModArithmetic INSTANCE = new ModArithmetic1000000007();
    private ModArithmetic1000000007(){}
    public static final long MOD = Const.MOD1000000007;
    public long getMod() {return MOD;}
    public long mod(long a) {return (a %= MOD) < 0 ? a + MOD : a;}
    public long add(long a, long b) {return (a += b) >= MOD ? a - MOD : a;}
    public long sub(long a, long b) {return (a -= b) < 0 ? a + MOD : a;}
    public long mul(long a, long b) {return (a * b) % MOD;}
}

Submission Info

Submission Time
Task F - Limited Xor Subset
User suisen
Language Java (OpenJDK 11.0.6)
Score 500
Code Size 28484 Byte
Status AC
Exec Time 301 ms
Memory 38572 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 116 ms 37240 KB
sample_02.txt AC 94 ms 37268 KB
sample_03.txt AC 116 ms 37192 KB
subtask_1_1.txt AC 114 ms 37216 KB
subtask_1_10.txt AC 132 ms 37232 KB
subtask_1_11.txt AC 126 ms 37272 KB
subtask_1_12.txt AC 132 ms 37052 KB
subtask_1_13.txt AC 128 ms 37364 KB
subtask_1_14.txt AC 123 ms 37360 KB
subtask_1_15.txt AC 118 ms 37060 KB
subtask_1_16.txt AC 108 ms 37268 KB
subtask_1_17.txt AC 108 ms 37152 KB
subtask_1_18.txt AC 133 ms 38220 KB
subtask_1_19.txt AC 133 ms 38216 KB
subtask_1_2.txt AC 121 ms 37340 KB
subtask_1_20.txt AC 297 ms 37272 KB
subtask_1_21.txt AC 301 ms 37204 KB
subtask_1_22.txt AC 95 ms 37264 KB
subtask_1_23.txt AC 100 ms 37124 KB
subtask_1_24.txt AC 97 ms 37288 KB
subtask_1_25.txt AC 132 ms 38572 KB
subtask_1_26.txt AC 99 ms 37400 KB
subtask_1_27.txt AC 103 ms 37244 KB
subtask_1_28.txt AC 107 ms 37192 KB
subtask_1_29.txt AC 103 ms 37240 KB
subtask_1_3.txt AC 123 ms 37228 KB
subtask_1_30.txt AC 103 ms 37104 KB
subtask_1_4.txt AC 118 ms 37240 KB
subtask_1_5.txt AC 121 ms 37220 KB
subtask_1_6.txt AC 136 ms 38376 KB
subtask_1_7.txt AC 118 ms 37152 KB
subtask_1_8.txt AC 151 ms 37296 KB
subtask_1_9.txt AC 217 ms 37048 KB