An expedition group flew from planet ACM-1 to Earth in order to study the bipedal species (its representatives don't even have antennas on their heads!).

The flying saucer, on which the brave pioneers set off, consists of three sections. These sections are connected by a chain: the 1-st section is adjacent only to the 2-nd one, the 2-nd one — to the 1-st and the 3-rd ones, the 3-rd one — only to the 2-nd one. The transitions are possible only between the adjacent sections.

The spacecraft team consists of n aliens. Each of them is given a rank — an integer from 1 to n. The ranks of all astronauts are distinct. The rules established on the Saucer, state that an alien may move from section a to section b only if it is senior in rank to all aliens who are in the segments a and b (besides, the segments a and b are of course required to be adjacent). Any alien requires exactly 1 minute to make a move. Besides, safety regulations require that no more than one alien moved at the same minute along the ship.

Alien A is senior in rank to alien B, if the number indicating rank A, is more than the corresponding number for B.

At the moment the whole saucer team is in the 3-rd segment. They all need to move to the 1-st segment. One member of the crew, the alien with the identification number CFR-140, decided to calculate the minimum time (in minutes) they will need to perform this task.

Help CFR-140, figure out the minimum time (in minutes) that all the astronauts will need to move from the 3-rd segment to the 1-st one. Since this number can be rather large, count it modulo m.

Input

The first line contains two space-separated integers: n and m (1 ≤ n, m ≤ 109) — the number of aliens on the saucer and the number, modulo which you should print the answer, correspondingly.

Output

Print a single number — the answer to the problem modulo m.

Examples

Input

1 10


Output

2


Input

3 8


Output

2

Note

In the first sample the only crew member moves from segment 3 to segment 2, and then from segment 2 to segment 1 without any problems. Thus, the whole moving will take two minutes.

To briefly describe the movements in the second sample we will use value <image>, which would correspond to an alien with rank i moving from the segment in which it is at the moment, to the segment number j. Using these values, we will describe the movements between the segments in the second sample: <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>; In total: the aliens need 26 moves. The remainder after dividing 26 by 8 equals 2, so the answer to this test is 2.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Codeforces {

    private static final Scanner sc = new Scanner(System.in);
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final long MOD = (long) (1e9 + 7);

    public static int[] LPS(String p){
        int[] lps = new int[p.length()];

        int i=1;
        int j=0;
        while (i < p.length()){
            if (p.charAt(i) == p.charAt(j)){
                lps[i] = j+1;
                i++;
                j++;
            }
            else{
                if (j == 0){
                    lps[i] = 0;
                    i++;
                }
                else{
                    j = lps[j-1];
                }
            }
        }
        return lps;
    }

    public static void KMP(String text,String pattern){
        int[] lps = LPS(pattern);
        int i = 0;
        int j = 0;
        ArrayList<Integer> matches = new ArrayList<>();
        while (i < text.length()){
            if (text.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
            }
            else{
                if (j != 0){
                    j = lps[j-1];
                }
                else {
                    i++;
                }
            }
            if (j == pattern.length()) {
                matches.add(i - j);
                j = lps[j-1];
            }
        }
        for (int x : matches){
            System.out.println("Match at : " + x);
        }
    }

    private static class SegmentTree{
        private long[] st;
        private int size;
        private int n;
        private long[] a;
        SegmentTree(long[] a,int n){
            this.size = 4*n;
            this.n = n;
            this.a = a;
            st = new long[size];
            //Arrays.fill(st,Integer.MIN_VALUE);
            buildSegmentTree(0,0,n-1);
            //printSegmentTree();
        }
        public long buildSegmentTree(int index,int l,int r){
            if (l == r){
                st[index] = a[l];
                return a[l];
            }
            int mid = (r+l) >> 1;
            return st[index] = buildSegmentTree(2*index+1,l,mid) + buildSegmentTree(2*index+2,mid+1,r);
        }
        public void printSegmentTree(){
            for (long x : st){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        public long query(int ql,int qr){
            return getQuery(0,0,n-1,ql-1,qr-1);
        }
        private long getQuery(int index,int sl,int sr,int ql,int qr){
            //System.out.println("#" + index);
            if (qr < sl || ql > sr)
                return 0;
            if (ql <= sl && qr >= sr)
                return st[index];
            int mid = (sr + sl) >> 1;
            return getQuery(2*index+1,sl,mid,ql,qr) + getQuery(2*index+2,mid+1,sr,ql,qr);
        }
        public void update(int i,long newVal){
            //long diff = newVal - a[i];
            a[i] = newVal;
            updateSegmentTree(0,i,0,n-1,newVal);
        }
        private void updateSegmentTree(int index,int i,int sl,int sr,long diff){
            if (sl == sr){
                st[index] = diff;
                return;
            }
            int mid = (sl + sr) >> 1;
            if (i <= mid)
                updateSegmentTree(2*index+1,i,sl,mid,diff);
            else
                updateSegmentTree(2*index+2,i,mid+1,sr,diff);
            st[index] = st[2*index+1] + st[2*index+2];
        }
    }

    public static class Pair<T1,T2>{
        T1 first;
        T2 second;
        Pair(T1 a,T2 b){
            this.first = a;
            this.second = b;
        }

        @Override
        public String toString() {
            return "[" + first + ", " + second + "]";
        }
    }

    public static long GCD(long a,long b){
        if (b == 0)
            return a;
        return GCD(b,a%b);
    }

    static int highestPowerOf2(int n) {
        int p = (int)(Math.log(n) /
                Math.log(2));
        return (int)Math.pow(2, p);
    }

    public static int binSearch(long[] a,long x){
        int l = 0;
        int r = a.length - 1;
        while (l <= r){
            int mid = l + (r-l)/2;
            if (a[mid]==x)
                return 1;
            else if (a[mid] < x)
                l = mid+1;
            else
                r = mid-1;
        }
        return -1;
    }

    public static int upperBound(long[] arr,long key){
        int start=0;int end=arr.length-1;
        int idx=-1;
        int mid;
        while(start<=end){
            int i=(start+end)/2;
            if(arr[i]<key){
                start=i+1;
            }
            else if(arr[i]>key){
                end=i-1;
            }
            else{
                idx=i;
                start=i+1;
            }
        }

        return idx;    }

    public static int lowerBound(long[] arr,long key){
        int start=0;int end=arr.length-1;
        int idx=-1;
        int mid;
        while(start<=end){
            int i=(start+end)/2;
            if(arr[i]<key){
                start=i+1;
            }
            else if(arr[i]>key){
                end=i-1;
            }
            else{
                idx=i;
                end=i-1;
            }
        }
        return idx;
    }

    public static int searchInsert(long[] nums, long target) {
        int s=0,e=nums.length-1;
        int mid;
        if(target<nums[0]){
            return 0;
        }
        while(s<=e){
            mid=(s+e)/2;
            if(nums[mid]>target){
                e=mid-1;
            }
            else if(nums[mid]==target){
                return mid;
            }
            else{
                s=mid+1;
            }
        }
        return s;
    }

    static boolean isPrime(long n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;

        if (n % 2 == 0 || n % 3 == 0)
            return false;

        for (long i = 5; i <= Math.sqrt(n) + 1; i += 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }

    public static long fastExpo(long a,long n,long mod){
        if (n == 0)
            return 1;
        else{
            long x = fastExpo(a,n/2,mod);
            if ((n&1) == 1){
                return (((a*x)%mod)*x)%mod;
            }
            else{
                return (((x%mod)*(x%mod))%mod)%mod;
            }
        }
    }

    public static long modInverse(long n,int p){
        return fastExpo(n,p-2,p);
    }

    public static long nCr(int n,int r,long[] fact,int mod){
        long val =  (((fact[n] * modInverse(fact[r],mod))%mod)*modInverse(fact[n-r],mod))%mod;
        return val;
    }

    public static void factorial(long[] fact,int n,int mod){
        for (int i=1;i<=n;i++){
            fact[i] = (fact[i-1] * i)%mod;
        }
    }

    public static int log2(long val){
        return (int) Math.floor(Math.log(val)/Math.log(2));
    }

    public static boolean isSubSequence(String s,String t){
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()){
            if (s.charAt(i) == t.charAt(j))
                j++;
            i++;
        }
        return j == t.length();
    }

    public static ArrayList<Long> getAllFactors(long x){
        ArrayList<Long> ans = new ArrayList<>();
        for (long i = 1; i <= Math.sqrt(x); i++) {
            if (x%i == 0){
                if (x/i == i){
                    ans.add(i);
                }
                else{
                    ans.add(i);
                    ans.add(x/i);
                }
            }
        }
        return ans;
    }

    public static boolean isPerfectSquare(long x){
        double val = Math.sqrt(x);
        return val*val == (double)x;
    }

    public static ArrayList<Integer> buildSieve(int n){
        boolean[] sieve = new boolean[n+1];
        Arrays.fill(sieve,true);
        sieve[0] = sieve[1] = false;
        for (int i = 2; i <= Math.sqrt(n+1) ; i++) {
            if (sieve[i]){
                for (int j = 2*i; j < n+1; j += i) {
                    sieve[j] = false;
                }
            }
        }
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 0; i < sieve.length; i++) {
            if (sieve[i]){
                primes.add(i);
            }
        }
        return primes;
    }

    public static int getLowBit(int n){
        int x = 0;
        while ((n&1) != 1){
            x++;
            n >>= 1;
        }
        return 1 << x;
    }

    static boolean isDiophantinePossible(int a, int b, int c) {
        return (c % GCD(a, b) == 0);
    }

    public static void solve() throws IOException {
        long n = sc.nextLong();
        long m = sc.nextLong();
        long ans = fastExpo(3,n,m);
        System.out.println(((ans-1)%m + m ) %m);
    }
    public static void main(String[] args) throws IOException {
        int t;
//        t = sc.nextInt();
        t = 1;
        while (t-- > 0){
            solve();
        }
        System.gc();
    }
}