Sum Root to Leaf Numbers

You are given an arbitrary binary tree consisting of N nodes, each associated with an integer value from 1 to 9. Each root-to-leaf path can be considered a number formed by concatenating node values. Your task is to find the total sum of all these numbers.

Example:

Tree structure:
      1
     /  \
    2    3

The root to leaf paths are:
- 1->2 representing the number 12
- 1->3 representing the number 13

The total sum of these paths is: 12 + 13 = 25

Input:

The first line of the input contains an integer ‘T’ denoting the number of test cases. Each test case consists of one line containing the elements of the tree in level order form separated by a single space. Use -1 for missing nodes.

Output:

For each test case, return the total sum of all the possible root to leaf paths, with each result given on a separate line.

Example:

Input:

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

Output:

1397

Constraints:

• 1 <= T <= 50
• 1 <= N <= 3000
• 1 <= nodeValue <= 9

Where N is the number of nodes in the tree, and nodeValue is the data contained in each node. Time limit: 1 sec.

Note: Return the result modulo (10^9 + 7) to handle large outputs.