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

Thankyou community of codeforces , I finally solved it!

I solved it by finding the recurrence relation , say , a(n) is the probability, that sequence of length n has xor equal to 1 .

Then , a(n)=a(n−1)∗c+z , where c=2∗p1−1 , z=1-p1

Closed form for this can be found here : https://www.wolframalpha.com/input/?i=g%28n%29+%3D+g%28n-1%29*c++%2B+z+