Expected Books Remain

You are given n shelves, each containing m books. Every day, a disturbance happens to rearrange the books. After each disturbance day, every book on a shelf has a \( \frac{1}{m} \) probability of remaining in its original position. Note that the disturbances are independent for each book and each day.

After \( k \) disturbance days, regardless of k, the expected number of books that remain in their original positions on any single shelf is \( m \times \frac{1}{m} = 1 \). Since there are n shelves, the overall expected number is \( n \).

Your task is to compute the expected number of books that remain in their original positions after \( k \) disturbance days.

inputFormat

The input is read from standard input (stdin) and is in the following format:

 n m k
 shelf_1_book_1 shelf_1_book_2 ... shelf_1_book_m
 shelf_2_book_1 shelf_2_book_2 ... shelf_2_book_m
 ...
 shelf_n_book_1 shelf_n_book_2 ... shelf_n_book_m

Where n is the number of shelves, m is the number of books per shelf, and k is the number of disturbance days. Although the names of the books are provided, they do not affect the computation.

outputFormat

Output a single integer to standard output (stdout) representing the expected number of books that remain in their original positions after k disturbance days.

3 4 1
A B C D
E F G H
I J K L

3