You are given an array $$A$$ of $$N$$ integers. Each integer is a single digit number in the range $$[0\; 9]$$. You are also given a number $$K$$. Now, you need to count how many subsequences of the array $$A$$ exist such that they form a $$K$$ digit valid number.

A subsequence of size $$K$$ is called a valid number if there are no leading zeros in the number formed.

Notes:

• A subsequence of an array is not necessarily contiguous.
• Suppose the given array is $$0\;1\;0\;2$$, then if you choose subsequence to be $$002$$, then it is not a valid $$3$$ digit number. Also, it will not be considered as a single digit number. A valid $$3$$ digit number in the array is $$102$$. Please go through the sample I/O for better understanding.

Input Fomat

The first line contains an integer $$N$$ as input denoting the size of the array.
Next line contains $$N$$ space separated integers that denote elements of the array.
Next line contains an integer $$K$$.

Output Format

In the output, you need to print the count of valid $$K$$ digit numbers modulo $$720720$$.

Constraints

$$1 \le N \le 10^5$$
$$1 \le K \le 30$$
$$0 \le A_i \le 9$$