Treasure Collection in the King's Dungeon

King X possesses a dungeon treasury arranged in an \( n \times m \) grid, where each cell contains a precious treasure with an associated value. The dungeon entrance is located at the top-left corner, and the exit is located at the bottom-right corner.

Little Ming is placed at the entrance. The king decrees that he may only move either right or down.

When Little Ming passes through a cell, if the value of the treasure in that cell is strictly greater than every treasure he has already collected, he may choose to pick it up (or leave it). When he reaches the exit, he will receive the treasures if and only if he has exactly \( k \) treasures.

Your task is to calculate the number of distinct ways in which Little Ming can traverse the dungeon (always moving right or down) and, by optionally picking up treasures (only when the treasure's value is greater than all previously picked treasures), end up with exactly \( k \) treasures.

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \). Each of the following \( n \) lines contains \( m \) integers, representing the values in the grid.

outputFormat

Output a single integer: the number of ways to complete the journey and collect exactly \( k \) treasures following the rules.

sample

1 1 0
5

1