import java.io.*;

/*
 PROG: paren
 LANG: JAVA
 ID: jtogether1
 */

public class paren {
	public static void main(String[] Args) throws IOException {
		// Use BufferedReader rather than RandomAccessFile; it's much faster
		BufferedReader in = new BufferedReader(new FileReader("paren.in"));
		// input file name goes above
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
				"paren.out")));

		int numparen = Integer.parseInt(in.readLine());
		long[] digit = new long[numparen];
		long modthingy = 0;
		for (int x = 1; x < 10; x++) {
			modthingy = modthingy * 10 + x;
		}
		modthingy = modthingy * 100 + 10;

		for (int x = 0; x < numparen; x++) {
			digit[x] = 0 - Integer.parseInt(in.readLine());
			int y = x;
			long value = 0;
			if (digit[y] == -1) {
				while (digit[y] != 0) {
					if (digit[y] > 0) {
						value += digit[y];
						digit[y] = -1;
					}
					y--;
				}

				digit[y] = value * 2 % modthingy;
				if (digit[y] == 0) {
					digit[y] = 1;
				}
			}
		}

		for (int x = 1; x < numparen; x++) {
			if (digit[x] > 0) {
				digit[0] = (digit[0] + digit[x]) % modthingy;
			}
		}

		out.println(digit[0] % modthingy);
		out.close(); // close the output file
		System.exit(0); // don't omit this!
	}
}