There are b blocks of digits. Each one consisting of the same n digits, which are given to you in the input. Wet Shark must choose exactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit 1 from the first block and digit 2 from the second block, he gets the integer 12. 

Wet Shark then takes this number modulo x. Please, tell him how many ways he can choose one digit from each block so that he gets exactly k as the final result. As this number may be too large, print it modulo 109 + 7.

Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3 ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.

Input

The first line of the input contains four space-separated integers, n, b, k and x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 109, 0 ≤ k < x ≤ 100, x ≥ 2) — the number of digits in one block, the number of blocks, interesting remainder modulo x and modulo x itself.

The next line contains n space separated integers ai (1 ≤ ai ≤ 9), that give the digits contained in each block.

Output

Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals k modulo x.

Examples

Input

12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5


Output

3


Input

3 2 1 2
6 2 2


Output

0


Input

3 2 1 2
3 1 2


Output

6

Note

In the second sample possible integers are 22, 26, 62 and 66. None of them gives the remainder 1 modulo 2.

In the third sample integers 11, 13, 21, 23, 31 and 33 have remainder 1 modulo 2. There is exactly one way to obtain each of these integers, so the total answer is 6.
import java.util.Arrays;

import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
public class R341_4 {
	static int mod=(int)1e9+7;
	public static void main(String[] args){
		FasterScanner s=new FasterScanner();
		PrintWriter out=new PrintWriter(System.out);
		int n=s.nextInt();
		int b=s.nextInt();
		int x=s.nextInt();
		int k=s.nextInt();
		int[] freq=new int[10];
		for(int i=0;i<n;i++)
			freq[s.nextInt()]++;
		long[][] mat=new long[k][k];
		for(int i=0;i<k;i++){
			for(int j=0;j<k;j++){
				for(int d=1;d<=9;d++){
					int check=((j*10)+d)%k;
					if(check==i){
						mat[i][j]+=freq[d];
					}
				}
			}
		}
		long[] v = new long[k];
		v[0]=1;
		long[][] ans=pow(mat, b);
		long[] V = new long[k];
		for(int i=0;i<k;i++){
			for(int j=0;j<k;j++){
				V[i]+=(ans[i][j]*v[j]);
			}
		}
		out.println(V[x]);
		out.close();
	}
	static long[][] pow(long[][] mat,long exp){
		if(exp==0){
			int n=mat.length;
			long[][] ans=new long[n][n];
			for(int i=0;i<n;i++){
				ans[i][i]=1;
			}
			return ans;
		}
		else{
			long[][] ans=pow(mat,exp/2);
			ans=mul(ans, ans);
			if(exp%2!=0){
				ans=mul(ans, mat);
			}
			return ans;
		}
	}

	static long[][] mul(long[][] a,long[][] b){
		long[][] c=new long[a.length][a.length];
		int n=a.length;
		for(int i=0;i<n;i++){
			for(int j=0;j<a.length;j++){
				for(int k=0;k<n;k++){
					c[i][j]+=(a[i][k]*b[k][j])%mod;
					c[i][j]-=c[i][j]>=mod?mod:0;
				}
			}
		}
		return c;

	}

	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = System.in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}

	public static class disjointSet {

		private int[] parent;  // parent[i] = parent of i
		private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
		private int count;     // number of components
		public disjointSet(int N) {
			if (N < 0) throw new IllegalArgumentException();
			count = N;
			parent = new int[N];
			rank = new byte[N];
			for (int i = 0; i < N; i++) {
				parent[i] = i;
				rank[i] = 0;
			}
		}

		public int find(int p) {
			if (p < 0 || p >= parent.length) throw new IndexOutOfBoundsException();
			while (p != parent[p]) {
				parent[p] = parent[parent[p]];    // path compression by halving
				p = parent[p];
			}
			return p;
		}
		public int count() {
			return count;
		}

		public boolean connected(int p, int q) {
			return find(p) == find(q);
		}

		public boolean union(int p, int q) {
			int rootP = find(p);
			int rootQ = find(q);
			if (rootP == rootQ) return false;

			// make root of smaller rank point to root of larger rank
			if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
			else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
			else {
				parent[rootQ] = rootP;
				rank[rootP]++;
			}
			count--;
			return true;
		}

	}
}