Gronhölm P36866


Statement
 

pdf   zip

thehtml

Con las reformas del nuevo EEES, los sistemas de enseñanza y evaluación estan cambiando constantemente. Ahora, los expertos del ICE han llegado a la conclusión de que el método óptimo de trabajo es el método Gronhölm: Cada fila de alumnos trabaja independientemente, y dentro de cada una, un estudiante puede escoger trabajar solo o con un compañero adyacente. En ningún caso no puede haber más de dos estudiantes por grupo. Se impone, también, que no puede haber dos filas con la misma disposición. Por ejemplo, la figura siguiente muestra un posible método de trabajo en una aula con 3 filas de 7 alumnos.

Entrada

La entrada contendrá múltiples casos, cada uno indicando 1≤ f≤ 10000, el número de filas de la clase, y 1≤ n≤ 50000, la cantidad de alumnos por fila. Podéis asumir que la clase está llena (es lo que tiene la asistencia obligatoria...).

Salida

Para cada caso, escribid el número de maneras de disponer la clase siguiendo el método Gronhölm, módulo 30000001.

Public test cases
  • Input

    1 1
    1 2
    1 5
    

    Output

    1
    2
    8
    
  • Input

    2 1
    2 3
    2 4
    

    Output

    0
    6
    20
    
  • Information
    Author
    Enric S. Cusell
    Language
    Spanish
    Other languages
    Catalan
    Official solutions
    C++
    User solutions