Number formation
Tag(s):

## Algorithms, Dynamic Programming, Easy, Two dimensional

Problem
Editorial
Analytics

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$

SAMPLE INPUT
5
1 1 0 1 0
3

SAMPLE OUTPUT
9
Explanation

In the given sample following are the possible subsequences that form a valid $3$ digit number.
$[1 , 2 , 3] = 110$
$[1 , 2 , 4] = 111$
$[1 , 2 , 5] = 110$
$[1 , 3 , 4] = 101$
$[1 , 3 , 5] = 100$
$[1 , 4 , 5] = 110$
$[2 , 3 , 4] = 101$
$[2 , 3 , 5] = 100$
$[2 , 4 , 5] = 110$

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Cars24 Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
Уведомления

?