In the new semester, TTL and YXH learn two new functions in class: the fifirst function f is defifined as the number of ‘1’ in the binary representation of x, for example, f = 1,f = 2,f = 2; The second function g = f, where ‘ & ’ denotes bitwise AND, and ‘ >> ’ denotes bitwise right shift operation. To test how far they grasp the two functions, their teacher assigns a class exercise. In this exercise, an integer k is given, then both TTL and YXH need to choose an interval respectively, denoted as [l1, r1] and [l2, r2]. After that, the teacher asks them to fifind all pairs such that x ∈ [l1, r1], y ∈ [l2, r2], and x ⊕ y ≤ k, then calculate the sum of g(x|y)!
In the new semester, TTL and YXH learn two new functions in class: the fifirst function f(x) is defifined as the number of ‘1’ in the binary representation of x, for example, f(1) = 1,f(3) = 2,f(5) = 2; The second function g(x) = f(x & (x >> 1)), where ‘ & ’ denotes bitwise AND, and ‘ >> ’ denotes bitwise right shift operation. To test how far they grasp the two functions, their teacher assigns a class exercise. In this exercise, an integer k is given, then both TTL and YXH need to choose an interval respectively, denoted as [l1, r1] and [l2, r2]. After that, the teacher asks them to fifind all pairs (x, y) such that x ∈ [l1, r1], y ∈ [l2, r2], and x ⊕ y ≤ k, then calculate the sum of g(x|y)! , where ‘ ⊕ ’ denotes bitwise XOR, ‘ | ’ denotes bitwise OR, and ‘ ! ’ is the factorial notation. If there is no such pair, the answer is 0. TTL and YXH think the problem is too difficult, so they ask smart you for help. Given the integer k and the two intervals [l1, r1] and [l2, r2], can you help them fifigure out the answer? Since the answer is likely to be very large, you just have to fifigure out the answer modulo 998244353.
