410122: GYM103960 B Fun with Stones

Alice and Bob will play a game with $$$3$$$ piles of stones. They take turns and, on each turn, a player must choose a pile that still has stones and remove a positive number of stones from it. Whoever removes the last stone from the last pile that still had stones wins. Alice makes the first move.

The $$$i$$$-th pile will have a random and uniformly distributed number of stones in the range $$$[L_i, R_i]$$$. What is the probability that Alice wins given that they both play optimally?

The input consists of a line with 6 integers, respectively, $$$L_1, R_1, L_2, R_2, L_3, R_3$$$. For each $$$i$$$, $$$1 \le L_i \le R_i \le 10^{9}$$$.

Print an integer representing the probability that Alice wins modulo $$$10^9+7$$$.

It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0\ (\textrm{mod}\ 10^9+7)$$$, that is, we are interested in the integer $$$p \times q^{-1}\ (\textrm{mod} \ 10^9+7)$$$.

3 3 4 4 5 5

1

4 4 8 8 12 12

0

1 10 1 10 1 10

580000005

5 15 2 9 35 42

1