410122: GYM103960 B Fun with Stones
Description
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?
InputThe 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}$$$.
OutputPrint 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)$$$.
ExamplesInput3 3 4 4 5 5Output
1Input
4 4 8 8 12 12Output
0Input
1 10 1 10 1 10Output
580000005Input
5 15 2 9 35 42Output
1