Cerca elegante
Note el límite de tiempo y memoria inusual para este problema
Todo el mundo sabe que Alicia tiene la cerca más elegante en toda la ciudad. Está construida a partir de secciones elegantes. Las secciones elegantes son rectángulos puestos uno al lado del otro en el suelo. La sección tiene una altura entera y un ancho entero .
Estamos buscando rectángulos elegantes en esta cerca elegante. Un rectángulo es elegante si:
- sus lados son horizontales o verticales y tienen longitudes enteras.
- la distancia entre el rectángulo y el suelo es entera.
- la distancia entre el rectángulo y el lado izquierdo de la primera sección es entera.
- está completamente dentro de las secciones.
¿Cuál es el número de rectángulos elegantes?
Este número puede ser muy grande, así que estamos interesados en su módulo
Subtareas
- Subtarea 1 (12 puntos): y y para todo .
- Subtarea 2 (13 puntos): para todo .
- Subtarea 3 (15 puntos): para todo .
- Subtarea 4 (15 puntos): para todo .
- Subtarea 5 (18 puntos): .
- Subtarea 6 (27 puntos): Sin restricciones adicionales.
Entrada
La primera línea contiene un entero (), el número de secciones.
La segunda línea contiene enteros separados por espacios, el -ésimo es ().
La tercera línea contiene enteros separados por espacios, el -ésimo es ().
Salida
Imprima un solo entero, el número de rectángulos elegantes módulo . Por tanto el rango de la salida es
Ejemplo
Entrada ejemplo 1
2
1 2
1 2
Salida ejemplo 1
12
Nota
La cerca tiene secciones, una sección de de altura de ancho, y otra de de altura y de ancho, respectivamente. Hay rectángulos elegantes de dimensiones: Hay rectángulos elegantes de dimensiones: Hay rectángulos elegantes de dimensiones: Hay rectángulos elegantes de dimensiones: Hay rectángulos elegantes de dimensiones:
Comments