Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TORNEI13 - 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 é atribuido a cada jogador um valor de 1 a 2N, 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 Hi, 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 atribuido um valor diferente nas duas disposições.

Entrada

A primeira linha contém dois inteiros N e K. Cada uma das próximas 2N 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 (109 + 7).

Restrições

  • 1 ≤ N ≤ 16
  • 1 ≤ KN + 1
  • 0 ≤ coeficiente de habilidade de um jogador ≤ 109
  • Não existem dois jogadores diferentes com a mesma habilidade.

Exemplos

Entrada
2 2
3
4
2
1

Saída
16

Entrada
1 2
7
5

Saída
2

Adicionado por:Marcos Kawakami
Data:2014-02-25
Tempo limite:1s-2s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2013 - Fase 2 Nível 2

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.