3378 - Sum and Sum 3378 - Sumar y Sumar 3378 - Sum and Sum

Statistics Sub: 77 | AC: 30 | AC%: 38,96 | Score: 2,86
Created by Luis Enrique Garcia Marrero
Added by legar (2015-09-29)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

You are given a function F defined recursively as follow:



Given a list of N positive integer numbers no greater than 10^9 you should make a program to find the number of non-empty subsets of the list such that after concatenate its elements (maintaining given order) the number formed - we call them S - meets the condition F ( S ) = D, for all possible values of D (1 <= D <= 9).
Usted tiene una función F definida recursivamente de la siguiente forma:



Dada una lista de N números enteros positivos no mayores que 10^9 usted debe hacer un programa para encontrar la cantidad de subconjuntos no nulos de la lista tales que luego de concatenar sus elementos (manteniendo el orden dado) el número formado - llamaremos a este número S - cumple la condición F ( S ) = D, para todo posible valor de D (1 <= D <= 9).
You are given a function F defined recursively as follow:



Given a list of N positive integer numbers no greater than 10^9 you should make a program to find the number of non-empty subsets of the list such that after concatenate its elements (maintaining given order) the number formed - we call them S - meets the condition F ( S ) = D, for all possible values of D (1 <= D <= 9).

Input specification

The first line contains an integer N (1 <= N <= 10^5) representing the number of elements in the list. Each of the next N lines describes a different element with an integer between 1 and 10^9, indicating their respective value.
La primera línea contiene un número entero N (1 <= N <= 10^5) que representa la cantidad de elementos en la lista. Cada una de las siguientes N líneas describe un elemento diferente mediante un número entero entre 1 y 10^9, indicando el respectivo valor del mismo.

The first line contains an integer N (1 <= N <= 10^5) representing the number of elements in the list. Each of the next N lines describes a different element with an integer between 1 and 10^9, indicating their respective value.

Output specification

Output nine lines with integers representing the number of non-empty subsets found for each possible values of D (1 <= D <= 9). As the answers can be very large, print the remainder of dividing the solutions by 1000000007 (10^9 + 7).
Usted debe imprimir nueve líneas con enteros que representan la cantidad de subconjuntos no nulos que fueron encontrados para cada posible valor de D (1 <= D <= 9). Como las respuestas pueden ser muy grandes, imprima el resto de dividir las soluciones por 1000000007 (10^9 + 7).

The first line contains an integer N (1 <= N <= 10^5) representing the number of elements in the list. Each of the next N lines describes a different element with an integer between 1 and 10^9, indicating their respective value.

Sample input

5
1
2
3
4
5

Sample output

4
3
4
3
4
4
3
3
3

Hint(s)

http://coj.uci.cu/24h/
http://coj.uci.cu/24h/
http://coj.uci.cu/24h/

Recommendation

We have carefully selected several similar problems: 3377 | 2916 | 3573 | 3599 | 3147 | 1103