Torneio

Juquinha foi convidado para participar do prestigiado torneio de tênis de Rolando Barros, na Nlogônia. O torneio é composto de $N$ rodadas no estilo mata-mata: todo jogador que perde uma partida é eliminado do torneio, e o vencedor desta partida avança para a próxima rodada. Como o número de jogadores ativos cai pela metade a cada rodada, é necessário que o número de jogadores participantes seja uma potência de $2$.

Os jogadores são inicialmente dispostos na chave por sorteio. Em uma disposição é atribuído a cada jogador um valor de $1$ a $2^N$, que corresponde a sua posição na chave do torneio. Jogadores vencedores avançam para a direita da chave, e disputam com o vencedor da sub-chave vizinha. Na imagem acima, caso os jogadores das posições $1$ e $3$ vençam suas partidas na primeira rodada, estes se enfrentarão na segunda rodada.

Juquinha não quer perder a chance de tornar-se um jogador mundialmente famoso, e para isso contratou você para ajudá-lo em suas análises estatísticas. Ele atribuiu a cada jogador um coeficiente de habilidade $H_i$, e sabe que se dois jogadores disputarem uma partida, aquele com maior coeficiente de habilidade certamente será o vencedor. Seu papel é calcular quantas disposições iniciais dos jogadores forçam Juquinha perder na $K$-ésima rodada (ou vencer o torneio, caso $K = N + 1$). Duas disposições são consideradas distintas se para algum jogador foi atribuído um valor diferente nas duas disposições.

Entrada

A primeira linha contém dois inteiros $N$ e $K$. Cada uma das próximas $2^N$ linhas seguintes contêm um único inteiro representando o coeficiente de habilidade de um jogador. O coeficiente de Juquinha é representado pelo primeiro desses inteiros.

Saída

Seu programa deve imprimir uma única linha contendo um único inteiro indicando o número de disposições iniciais que forçam Juquinha a perder na $K$-ésima rodada (ou ganhar o torneio, se $K = N + 1$). Como este número pode ser muito grande, imprima o resto que este número deixa quando dividido por $1\ 000\ 000\ 007$ ($10^9 + 7$).

Restrições

• $1 \leq N \leq 16$
• $1 \leq K \leq N +1$
• $0 \leq$ coeficiente de habilidade de um jogador $\leq 10^9$
• Não existem dois jogadores diferentes com a mesma habilidade.

Informações sobre a pontuação

• Em um conjunto de casos de testes que totaliza $30$ pontos, $N \leq 3$.

Exemplos

Exemplo de entrada 1

2 2
3
4
2
1

Exemplo de saída 1

16

Exemplo de entrada 2

1 2
7
5

Exemplo de saída 2

2