import java.util.*;

class Solution {
    private static int[] fib  = new int[50001];

    public int[] solution(int[] A, int[] B) {
        fib[1] = 1;
        fib[2] = 2;

        int[] res = new int[A.length];

        for (int i=3; i<fib.length; i++) {
            fib[i] = (fib[i-1] + fib[i-2]) % getPow(30);
        }

        for (int i=0; i<A.length; i++) {
            res[i] = fib[A[i]] % getPow(B[i]);
        }

        return res;
    }

    private int getPow(int b) {
        return (int) Math.pow(2, b);
    }
}