Shall we play a game
Source: codechef
Difficulty: 1361

Shall we play a game
Alice and Bob play a game over$N$rounds, starting with an initial score of$0$. Alice takes the first turn.
In the$i_{th}$round ($1 \leq i \leq N$), the current player must either add or subtract$2^{i-1}$from the current score.
As the game progresses, let:$X$be the maximum score reached at any point.$Y$be the minimum score reached at any point.
Alice’s goal is to minimize the final difference$X-Y$, while Bob aims to maximize it.
Assuming both players play optimally, determine the final value of$X-Y$after all$N$rounds. Since this value can be very large, output it modulo$998244353$.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists a single line of input.
The only line of each test case contains an integer$N$— the number of rounds played.
Output Format
For each test case,  output a single line containing one integer — the final value of$X-Y$modulo$998244353$.
Constraints$1 \leq T \leq 10^3$$1 \leq N \leq 10^3$Sample 1:
Explanation:
Test Case 1:
Alice increases/decreases the score by 1, so the final value of$X - Y = 1$.
Test Case 2:
Alice increases/decreases the score by 1. In his turn, Bob increases the score to 3 if the score after the first round is 1 or decreases it to -3, if it is -1. In either case, the final value of$X - Y$is 3.

Sample Input:
3
1
2
10

Sample Output:
1
3
768

C++ solution:
#include <bits/stdc++.h>
using namespace std;

int main() {
    // your code goes here
    long long mod=998244353;
    long long  t;cin>>t;
    while(t--){
        long long n;cin>>n;
        long long ans=0;
        long long maxi=0,mini=0;
        long long d=1;
        if(n%2){
            long long x=1;
            for(long long i=1;i<=n-1;i++){
                x=x%mod;
                x=x*2;
            }
            x=x%mod;
            cout<<x<<endl;
        }
        else{
            long long x1=1,x2=1;
            for(long long i=1;i<=n-2;i++){
                x1=x1%mod;
                x1=x1*2;
            }
            x1=x1%mod;
            long long x=1;
            for(long long i=1;i<=n;i++){
                x2=x2%mod;
                x2=x2*2;
            }
            x2=x2%mod;
            cout<<(x2-x1+mod)%mod<<endl;
        }
    }
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    // "strings"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    scanner.Scan()
    t, _ := strconv.Atoi(scanner.Text())

    for i := 0; i < t; i++ {
        scanner.Scan()
        n, _ := strconv.Atoi(scanner.Text())
        var res int64
        if n%2 == 1 {
            res = mod_pow(2, n-1, 998244353)
        } else {
            res = (3 * mod_pow(2, n-2, 998244353)) % 998244353
        }
        fmt.Printf("%v\n", res)
    }

}

func mod_pow(base int64, exp int, mod int64) int64 {
    var result int64 = 1
    base = base % mod
    for {
        if exp <= 0 {
            break
        }
        if exp%2 == 1 {
            result = (result * base) % mod
        }
        exp = exp >> 1
        base = (base * base) % mod
    }
    return result
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), n;
  
            while(__ -- > 0) {
                n = nextInt() - 1;
                if ((n & 1) == 1) outData.append((getPow2(n) + getPow2(n - 1)) % mod);
                else outData.append(getPow2(n));
                
                outData.append('\n');
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    static final long mod = 998244353;
    static long getPow2(int n) {
        long res = 1, pow = 2;
        while(n > 0) {
            if((n & 1) == 1) res = res * pow % mod;
            pow = pow * pow % mod;
            n >>= 1;
        }
        
        return res;
    }
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
const fs = require('fs');

const VIM = 998244353;

const input = fs.readFileSync(0, 'utf-8').trim().split(/\s+/);

const XIM = parseInt(input[0]); 

let results = [];

for (let i = 0; i < XIM; i++) {
    
    let YIM = parseInt(input[i + 1]);
    
    if (YIM % 2 === 1) {
        
        results.push(BigInt(2) ** BigInt(YIM - 1) % BigInt(VIM));
        
    } 
    else {
        
        results.push((BigInt(3) * (BigInt(2) ** BigInt(YIM - 2) % BigInt(VIM))) % BigInt(VIM));
        
    }
}

console.log(results.join('\n'))

Python solution:
# cook your dish here

mod=998244353 
T = int(input()) 
for _ in range(T): 
    N = int(input()) 
    if N % 2 == 0: 
        exponent = N-2 
        res = (3 * pow (2, exponent, mod)) % mod 
    else: 
        exponent = N - 1 
        res = pow(2, exponent, mod) 
    print(res)

Ruby solution:
MOD = 998244353

def main
  t = gets.to_i
  t.times do
    n = gets.to_i
    if n == 1
      puts 1 % MOD
    elsif n == 2
      puts 3 % MOD
    else
      if n % 2 == 0
        ans = (1 << (n - 1)) + (1 << (n - 2))
      else
        ans = 1 << (n - 1)
      end
      puts ans % MOD
    end
  end
end

main