Ruudukko

// Annetaan taulukko
// Kokonaisluku leveys/korkes - leveys/korkeys toiseen
// Ruudukossa reitti siirtyy ruudusta pysty tai vaakasuunnassa
//  ruutuun jossa on pienempi luku kuin nykyisessä ruudussa
// Reitissä voi olla van yksi ruutu, ruutujen ei tarvitse olla vierekkäisiä
// Kuinka monta reittiä
// Anna jakojäännös luvulla 10^9+7

let lines = []
let expectedAmount = null

function pathFind(startX, startY, visited = [], isChain) {
    // Look for any value in the same line
    let pathCount = !isChain ? 1 : 0
    
    // console.log("#", startX, startY, visited)

    for (let i = startX; i < expectedAmount; i++) { // Right
        if (visited.includes(`${i}-${startY}`)) continue
        if (lines[startY][startX] > lines[startY][i]) {
            // console.log(" found", [startX, startY], [i, startY], !isChain ? "(root)" : "(child)")
            // This is a path
            pathCount += 1
            // Continue the path
            const nVisited = visited.slice(0)
            nVisited.push(`${i}-${startY}`)
            pathCount += pathFind(i, startY, nVisited, true)
        }
    }
    for (let i = startX; i > -1; i--) { // Left
        if (visited.includes(`${i}-${startY}`)) continue
        if (lines[startY][startX] > lines[startY][i]) {
            // console.log(" found", [startX, startY], [i, startY], !isChain ? "(root)" : "(child)")
            // This is a path
            pathCount += 1
            // Continue the path
            const nVisited = visited.slice(0)
            nVisited.push(`${i}-${startY}`)
            pathCount += pathFind(i, startY, nVisited, true)
        }
    }

    // Look for a path below or above
    for (let i = startY; i < expectedAmount; i++) { // Down
        if (visited.includes(`${startX}-${i}`)) continue
        if (lines[startY][startX] > lines[i][startX]) {
            // console.log(" found", [startX, startY], [startX, i], !isChain ? "(root)" : "(child)")
            // This is a path
            pathCount += 1
            // Continue the path
            const nVisited = visited.slice(0)
            nVisited.push(`${startX}-${i}`)
            pathCount += pathFind(startX, i, nVisited, true)
        }
    }
    for (let i = startY; i > -1; i--) { // Up
        if (visited.includes(`${startX}-${i}`)) continue
        if (lines[startY][startX] > lines[i][startX]) {
            // console.log(" found", [startX, startY], [startX, i], !isChain ? "(root)" : "(child)")
            // This is a path
            pathCount += 1
            // Continue the path
            const nVisited = visited.slice(0)
            nVisited.push(`${startX}-${i}`)
            pathCount += pathFind(startX, i, nVisited, true)
        }
    }

    // console.log("!", visited.map(() => "#").join(""), pathCount, [startX, startY])
    //console.log(isChain ? " !->" : "->", pathCount, [startX, startY])
    return pathCount
}

const { createInterface } = require("readline")
const interface = createInterface({
    input: process.stdin,
    terminal: false
})


interface.on("line", (data) => {
    const str = data.toString().trimEnd()

    // Get line count
    if (str.split(" ").length === 1) {
        expectedAmount = parseInt(str)
        return
    }

    // Push to memory
    lines.push(str.split(" ").map(Number))

    if (lines.length === expectedAmount) {
        // Logic
        // Test every item of every row for paths
        let pathsCount = 0

        for (let i = 0; i < lines.length; i++) {
            for (let ii = 0; ii < lines[i].length; ii++) {
                // console.log(ii, i)
                const paths = pathFind(ii, i)
                pathsCount += paths
                // console.log("+", paths, "\n")
            }
        }

        const answer = pathsCount % ((10**9) + 7)
        console.log(answer)
        process.exit()
    }
})

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED