Sum Root to Leaf Path Problem

You are given an arbitrary binary tree consisting of N nodes where each node is associated with an integer value from 1 to 9. Each root-to-leaf path in the tree represents a number formed by concatenating the values from root to leaf.

Example:

       1
      /  \
     2    3

The root to leaf path 1->2 represents the number 12.
The root to leaf path 1->3 represents the number 13.

Your task is to calculate the total sum of all the possible root-to-leaf paths in the tree.

Input:

1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

25

Constraints:

• 1 ≤ T ≤ 50 - the number of test cases.
• 1 ≤ N ≤ 3000 - number of nodes in the tree.
• 1 ≤ nodeValue ≤ 9 - node values are between 1 and 9.

Note:

The output may be very large, return the answer modulo (109 + 7).

Example Explanation:

The total sum of all the root-to-leaf paths is 12 (from path 1->2) + 13 (from path 1->3) = 25. Hence, the output is 25.

In the input, nodes are represented in level order, using -1 for null nodes.