This problem is from a coding test/contest on Hackerearth which is over now .

I will be asking a subtask of the original problem as I can solve the original problem if I can solve this subtask .

We are given three integers a,b,c .

Constraints : b>0 , b,a <998244353

c<=10^18

Consider an array of size 'c' .

It only consists of only zeroes and ones .

Calculate the probability that the xor of this array is "1" .

Probability of any array element to be zero , is given by a/b .

Example :

c=2

a=1

b=3

(p1=a/b)

Only the following arrays can make xor = 1 ,

1) {0,1} , (probability1) : (1/3)*(2/3) = (2/9)

2) {1,0) , (probability2) : (2/3)*(1/3) = (2/9)

Final answer : 2/9 + 2/9 = 4/9

Answer to be calculated modulo the prime number , 998244353