## ECOO '17 R3 P2 - Family Trees

View as PDF

Points: 7 (partial)
Time limit: 13.0s
Memory limit: 256M

Author:
Problem types

Family trees are trees that show relationships between family members. They begin with a root ancestor and show that ancestor's children, then every child's children, and so on. For example, Bob, the root ancestor, can have two daughters Alice and Eve. Alice can then have two children Jenna and Brian, and Eve can have one daughter Sarah. To help find people in the tree, we give each family member a family ID, formatted as a series of integers separated by dots (e.g. 0.1, 0.2.3, 0.5.1.7 and so on).

A family ID is either:

• 0, which represents the root ancestor.
• X.y, where X is a valid family ID, and where this ID represents the child of .

For the example above, the family IDs are:

Bob:        0
Alice       0.1
Jenna       0.1.1
Brian       0.1.2
Eve         0.2
Sarah       0.2.1

Family IDs can give you an idea of how big a family is. For example, if you know that someone has the ID 0.2.3, then you know there are family members with IDs 0, 0.1, 0.2, 0.2.1, and 0.2.2. Given a list of family IDs, figure out the smallest possible size of the family.

#### Input Specification

The input will contain test cases. Each test case starts with an integer . The next lines each contain a family ID.

For of cases, , and the total input size will not exceed characters.

#### Output Specification

For each test case, your program should output the minimum size of the family, modulo or . *

#### Sample Input

1
0.2.3
3
0
0.2.1
0.1.1

#### Sample Output

6
5

Note: Only cases are shown in this sample.

#### Footnotes

* This means that if the size of the family is you should output , the remainder after dividing by .

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

For each test case, your program should output the minimum size of the family, modulo 1000000007