Due to COVID19 all employees of chemical factory are quarantined in home. So, company is organized by automated robots. There are $N$ Containers in company, which are labelled with $1$ to $N$ numbers. There are Total $N$ robots in Company, which are labelled $1$ to $N$. 
Each Robot adds $1$ litter Chemical in containers whose labels are multiple of robots’ label. (E.g. robot labelled 2 will add Chemical in containers labelled 2, 4, 6, ….). 
Robots follow few rules mentioned below:
- Chemical with $pH<7$ is acidic.
- Chemical with $pH=7$ is neutral.
- Chemical with $pH>7$ is basic.
- Mixture of $1$ litter acid and $1$ litter base makes neutral solution.
- If Container is empty or pH of Chemical in container is equal to 
- $7$ then robot adds $1$ litter acidic Chemical.
- If pH of Chemical in container is less than $7$ then robots adds $1$ litter basic Chemical.
Now Chemical is packed in $4$ ways:
- Containers with exactly $2$ litter acid and $1$ litter base are packed at $P1$ cost. 
- Containers with acidic Chemical are packed at $P2$ cost. (Here Don’t consider containers with exactly $2$ litter acid and $1$ litter base as we counted them in above rule)
- Containers with $pH=7$ Chemical is packed at $P3$ cost.
- Containers with Basic Chemical are packed at $P4$ cost.
Now $1$ employee given task to find packing cost of containers with labels in range $[ k1, k2]$ (Inclusive). Help him out. As Cost can be large find cost in modulo of $100000007$

-----Input:-----
- The first line of the input contains a single integer T denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains $3$ space separated Integers $N$, $K1$ and $K2$.
- The second and last line contains $4$ space separated Integers $P1$, $P2$, $P3$ and $P4$

-----Output:-----
For each test case, print total cost of packing of containers modulo 100000007.

-----Constraints-----
- $1 \leq T \leq 50000$
- $1 \leq P1, P2, P3, P4 \leq 2*10^7$
- $2 \leq N \leq 2*10^7$
- $1 \leq K1, K2 \leq N$

-----Subtasks-----Subtask #1 (20 points):
- $1 \leq T \leq 10$
- $1 \leq P1, P2, P3, P4 \leq 2*10^7$
- $2 \leq N \leq 1000$
- $1 \leq K1, K2 \leq N$Subtask #2 (80 points) :
- Original Constraint

-----Sample Input:-----
1
4 1 4
2 2 2 2

-----Sample Output:-----
8

-----Explanation:-----
Let’s use notation, 
0 for acidic Chemical, 
1 for Chemical with pH=7, 
2 for basic Chemical,
3 for Containers with exactly 2 litter acid and 1 litter base,
-1 for empty containers
Initially 4 containers are empty so
[-1, -1, -1, -1]
Robot 1 adds 1 litter acid in all containers.
[0, 0, 0, 0]
Robot 2 adds base in containers labelled 2, 4
[0, 1, 0, 1]
Robot 3 adds base in containers labelled 3
[0, 1, 1, 1]
Robot 4 adds acid in containers labelled 4 because it contains Chemical with pH=7. After adding acid, it also contains exactly 2 litter acid and 1 litter base, so denoting it with 3.
[0, 1, 1, 3]
Corresponding cost of packing container
[P2, P3, P3, P1]
Now, calculate total cost,
Cost = P2+P3+P3+P1 = 2+2+2+2 = 8

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't = int(input())\n\nfor _ in range(t):\n    n, k1, k2 = map(int, input().split())\n    p1, p2, p3, p4 = map(int, input().split())\n    sum = 0\n    cont = [[[0, 0], -1] for _ in range(n)]\n    for i in range(1, n+1):\n        con = [x for x in range(1, n+1) if x%i == 0]\n        \n        for ele in con:\n            if cont[ele-1][1] == -1:\n                cont[ele-1][1] = 0\n                cont[ele-1][0][0] += 1\n                \n            elif cont[ele-1][1] == 0:\n                cont[ele-1][0][1] += 1\n                cont[ele-1][1] = 1\n            \n            elif cont[ele-1][1] ==  1:\n                if cont[ele-1][0] == [1, 1]:\n                    cont[ele-1][1] = 3\n                else:\n                    cont[ele-1][1] = 0\n                cont[ele-1][0][0] += 1\n            \n            elif cont[ele-1][1] == 3:\n                cont[ele-1][0][1] += 1\n                cont[ele-1][1] = 1\n    \n    for ele in cont[k1-1:k2]:\n        # print(ele[1])\n        if ele[1] == 0:\n            sum += p2\n        elif ele[1] == 2:\n            sum += p4\n        elif ele[1] == 3:\n            sum += p1\n        elif ele[1] == 1:\n            sum+= p3\n    print(sum)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13935