Contando pares


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Authors:
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, calcule el número de pares (i, j), donde i y j pertenecen al conjunto {0, 1, 2, ..., 2^N-1}, tales que 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 solo estarán activos (puestos a 1) los bits que estén activos tanto en a como en b. Ejemplo 10 & 6 = 2, ya que (10)_2 = 1010, (6)_2 = 110 y (2)_2 = 10.

Entrada

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

Subtareas:

  • 1 \leq N \leq 13 (4 puntos)
  • 1 \leq N \leq 2000 (26 puntos)
  • 1 \leq N \leq 10^5 (30 puntos)
  • 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.

Ejemplo de Entrada

2

Ejemplo de Salida

5

Explicacion: Los pares validos son: (0, 1), (0, 2), (0, 3), (1, 3) y (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