Kajaria has an empty bag and 2 types of tiles - 
tiles of type $1$ have the number $X$ written and those of type $2$ have the number $Y$ written on them. He has an infinite supply of both type of tiles.
In one move, Kajaria adds exactly $1$ tile to the bag. He adds a tile of type $1$ with probability $p$ and a tile of type $2$ with probability $(1 - p)$.
If $2$ tiles in the bag have the same number written on them (say $Z$), they are merged into a single tile of twice that number ($2Z$).
Find the expected number of moves to reach the first tile with number $S$ written on it.
Notes on merging: 
- Consider that the bag contains tiles $(5, 10, 20, 40)$ and if the new tile added is $5$, then it would merge with the existing $5$ and the bag would now contain $(10, 10, 20, 40)$. The tiles $10$ (already present) and $10$ (newly formed) would then merge in the same move to form $(20, 20, 40)$, and that will form $(40, 40)$, which will form $(80)$.
Kajaria guarantees that:
- $X$ and $Y$ are not divisible by each other.
- A tile with number $S$ can be formed.

-----Input-----
- First line contains a single integer $T$ - the total no. of testcases
- Each testcase is described by $2$ lines:
- $X, Y, S$ - $3$ space-separated natural numbers
- $u, v$ - $2$ space-separated natural numbers describing the probability $p$
The value of $p$ is provided as a fraction in its lowest form $u/v$ ($u$ and $v$ are co-prime)

-----Output-----
- For each testcase, if the expected number of moves can be expressed as a fraction $p/q$ in its lowest form, print $(p * q^{-1})$ modulo $10^9 + 7$, where $q^{-1}$ denotes the modular inverse of $q$ wrt $10^9 + 7$.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $2 \leq X, Y \leq 5 * 10^{17}$
- $1 \leq S \leq 10^{18}$
- $1 \leq u < v \leq 10^{9}$

-----Sample Input-----
1
5 3 96
1 3

-----Sample Output-----
48

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
t=int(input())
MOD=1000000007
def mod(n, m=MOD):
 n%=m
 while n<0: n+=m
 return n

def power(n, p):
 res=1
 while p:
  if p%2: res=mod(res*n)
  p//=2
  n=mod(n*n)
 return res

while t:
 ma=input().split()
 x=int(ma[0])
 y=int(ma[1])
 s=int(ma[2])
 ma=input().split()
 u=int(ma[0])
 v=int(ma[1])
 if s%x==0 and ((s // x) & ((s // x) - 1) == 0):
  inv=power(u, MOD-2)
  print(mod(mod(mod(s//x)*v)*inv))
 else:
  inv=power(v-u, MOD-2)
  print(mod(mod(mod(s//y)*v)*inv))
 t-=1


M = 10**9+7

for _ in range(int(input())):
 x,y,s = [int(s) for s in input().split()]
 u,v = [int(s) for s in input().split()]
 if (s%x==0) and (((s//x)&(s//x -1))==0):
  w = s//x
 else:
  w = s//y
  u = v-u
 ans = ((((w%M) * (v%M))%M)*pow(u,M-2,M))%M
 print(ans)

M = 10**9+7

for _ in range(int(input())):
 x,y,s = [int(s) for s in input().split()]
 u,v = [int(s) for s in input().split()]
 if (s%x==0) and (((s//x)&(s//x -1))==0):
  w = s//x
 else:
  w = s//y
  u = v-u
 ans = ((((w%M) * (v%M))%M)*pow(u,M-2,M))%M
 print(ans)

# cook your dish here
t=int(input())
MOD=1000000007
def mod(n, m=MOD):
 n%=m
 while n<0: n+=m
 return n

def power(n, p):
 res=1
 while p:
  if p%2: res=mod(res*n)
  p//=2
  n=mod(n*n)
 return res

while t:
 ma=input().split()
 x=int(ma[0])
 y=int(ma[1])
 s=int(ma[2])
 ma=input().split()
 u=int(ma[0])
 v=int(ma[1])
 if s%x==0 and ((s // x) & ((s // x) - 1) == 0):
  inv=power(u, MOD-2)
  print(mod(mod(mod(s//x)*v)*inv))
 else:
  inv=power(v-u, MOD-2)
  print(mod(mod(mod(s//y)*v)*inv))
 t-=1