A ticketing tree is a binary tree where every node holds a single decimal digit (0-9). Each path from the root to a leaf spells a decimal number, reading digits from the root down to the leaf (the root digit is the most significant). For example, a path 4 -> 9 -> 5 spells 495.
Sum the numbers spelled by all root-to-leaf paths and report the sum modulo 1000000007. A leaf is a node with no children.
Input format
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is a digit (0-9) or null for a missing child. Children of null nodes are omitted.
Output format
A single integer: the sum of all root-to-leaf numbers, taken modulo 1000000007.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each node value is a single digit between 0 and 9.