// Arup Guha
// 5/2/2017
// Solution to 2017 NAIPC Problem C: Stretching Streamers

import java.util.*;

public class stretchingstreamers {

	final public static long MOD = 1000000007L;

	public static int n;
	public static int[] vals;
	public static boolean[][] g;
	public static long[][][] memo;

	public static void main(String[] args)  {

		// Read in input.
		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		vals = new int[n];
		for (int i=0; i<n; i++)
			vals[i] = stdin.nextInt();

		// Store the graph.
		g = new boolean[n][n];
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {
				g[i][j] = gcd(vals[i], vals[j]) > 1;
				g[j][i] = g[i][j];
			}
		}

		// Set up memo table.
		memo = new long[n][n][2];
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				Arrays.fill(memo[i][j], -1);

		// Solve and output.
		System.out.println((mcm(0,n-1,0) + mcm(0,n-1,1))%MOD);
	}

	// Returns the number of solutions from index start to end, when these two are connected based on connect(0 = no, 1 = yes)
	public static long mcm(int start, int end, int connect) {

		// Can't do this.
		if (start > end) return 0;

		// No edge needed.
		if (start == end) return 1;

		// This is a contradiction, so 0 is the answer.
		if (connect == 1 && !g[start][end]) return 0;

		// Last step, so we can return 1 if they can be connected.
		if (end-start == 1 && connect == 1) return g[start][end] ? 1 : 0;

		// Another contradiction.
		if (end-start == 1 && connect == 0) return 0;

		// Save time.
		if (memo[start][end][connect] != -1) return memo[start][end][connect];

		long res = 0;

		// Count ones with no connection between start and end.
		if (connect == 0) {

			// mid is last point we connect to from start.
			for (int mid=end-1; mid>=start+1; mid--) {
				long right = (mcm(mid,end,0) + mcm(mid,end,1))%MOD;
				long left = mcm(start,mid,1);
				res = (res + left*right)%MOD;
			}
		}

		// We have already connected start and end.
		else {

			// Either connect to start or end, but not both.
			res = (res + mcm(start,end-1,0) + mcm(start,end-1,1)+ mcm(start+1,end,0) + mcm(start+1,end,1))%MOD;

			// OR...connect start upto some mid, then mid+1 upto end.
			for (int mid=start+1; mid<end-1; mid++) {
				long left = (mcm(start,mid,0) + mcm(start,mid,1))%MOD;
				long right = (mcm(mid+1,end,0) + mcm(mid+1,end,1))%MOD;
				res = (res + left*right)%MOD;
			}
		}

		// Store and return.
		memo[start][end][connect] = res;
		return res;
	}

	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b,a%b);
	}
}