Contando pares

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Authors:

frankr, FrankHG

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Dado un entero positivo $n$ ~n~, calcule el número de pares $(i, j)$ ~(i, j)~, donde $i$ ~i~ y $j$ ~j~ pertenecen al conjunto ${0, 1, 2, ..., 2^N-1}$ ~{0, 1, 2, ..., 2^N-1}~, tales que $j > i$ ~j > i~ y j & i == i.

El operador & es el operador and o conjunción a nivel de bits, si R = a & b, entonces en $R$ ~R~ solo estarán activos (puestos a $1$ ~1~) los bits que estén activos tanto en $a$ ~a~ como en $b$ ~b~. Ejemplo 10 & 6 = 2, ya que $(10)_2 = 1010, (6)_2 = 110$ ~(10)_2 = 1010, (6)_2 = 110~ y $(2)_2 = 10$ ~(2)_2 = 10~.

Entrada

En la primera línea aparecerá el entero $N$ ~N~.

Subtareas:

$1 \leq N \leq 13$ ~1 \leq N \leq 13~ (4 puntos)
$1 \leq N \leq 2000$ ~1 \leq N \leq 2000~ (26 puntos)
$1 \leq N \leq 10^5$ ~1 \leq N \leq 10^5~ (30 puntos)
$1 \leq N \leq 10^9$ ~1 \leq N \leq 10^9~ (40 puntos)

Salida

Imprima un único entero que es la cantidad de pares descritos, pero como esta cantidad puede ser muy grande imprima solo el resto con $10^9 + 7$ ~10^9 + 7~.

Ejemplo de Entrada

Ejemplo de Salida

Explicacion: Los pares validos son: $(0, 1), (0, 2), (0, 3), (1, 3)$ ~(0, 1), (0, 2), (0, 3), (1, 3)~ y $(2, 3)$ ~(2, 3)~.

Comments

0

josed commented on May 28, 2019, 1:44 p.m.

Prueben ahora

0

leocar commented on May 28, 2019, 1:23 p.m.

No deja enviar las soluciones