import java.math.*;
import java.util.*;

public class NopanVikat {
    public static long[][] tulo(long[][] a, long[][] b) {
        long[][] c = new long[6][6];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                long t = 0;
                for (int k = 0; k < 6; k++) {
                    t += (a[i][k]*b[k][j])%100000;
                }
                c[i][j] = t%100000;
            }
        }
        return c;
    }

    public static long[][] laske(BigInteger n) {
        BigInteger b0 = BigInteger.ZERO;
        BigInteger b1 = BigInteger.ONE;
        BigInteger b2 = b1.add(b1);
        if (n.equals(b1)) return new long[][] {{0,1,0,0,0,0},
                                               {0,0,1,0,0,0},
                                               {0,0,0,1,0,0},
                                               {0,0,0,0,1,0},
                                               {0,0,0,0,0,1},
                                               {1,1,1,1,1,1}};
        if (n.remainder(b2).equals(b0)) {
            long[][] p = laske(n.divide(b2));
            return tulo(p,p);
        } else {
            return tulo(laske(n.subtract(b1)), laske(b1));
        }
    }

    public static long nopat(BigInteger n) {
         if (n.equals(BigInteger.ZERO)) return 1;
         long[][] tulos = laske(n);
         long t = 0;
         int[] alku = {1, 1, 2, 4, 8, 16};
         for (int k = 0; k < 6; k++) {
             t += (tulos[0][k]*alku[k])%100000;
         }
         return t%100000;
    }

    public static void main(String[] args) {
        BigInteger n = BigInteger.valueOf(10).pow(100);
        System.out.println(nopat(n));
    }
}