RNG 2

시간 제한2초메모리 제한512 MB

요약

0부터 K까지의 정수를 원소로 하는 길이 N 배열 중 전체 XOR이 0이 아닌 배열의 개수를 30011로 나눈 나머지를 구한다.

문제

길이가 $N$ 이고 모든 원소가 $0$ 이상 $K$ 이하의 정수인 배열을 생각하자. 이런 배열 중에서 모든 원소를 비트 단위 XOR로 묶은 값이 $0$ 보다 큰 것이 몇 개인지 세는 프로그램을 작성하시오.

같은 값이 여러 번 나와도 되고, 나열한 순서가 다르면 서로 다른 배열로 센다.

첫째 줄에 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. ( $1 \le N \le 20000$ , $1 \le K \le 50000$ )

첫째 줄에 조건을 만족하는 배열의 개수를 $30011$ 로 나눈 나머지를 출력한다.