A sign of place

Bob has an array of length $n$ whose elements lie in the range $[1,n]$. He compared the adjacent elements of the array and prepared a string $s$ of length $n-1$ of $<$, $>$, and  $=$ signs that show the result of the comparison between the adjacent elements of the array. 

Formally,

• If $s[i]:<$, then $a[i]<a[i+1]$.
• If $s[i]:>$, then $a[i]>a[i+1]$.
• If $s[i]:=$, then $a[i]=a[i+1]$.
• For each valid index $i$

Unfortunately, Bob lost the array and now he wonders how many distinct arrays of length $n$ exist such that its elements are between $1$ and $n$. Since the count can be very large, find this count modulo ${10}^9+7$. 

Two arrays are different if they differ at least one index.

Example:

Input:  n=3, str="<>"
Output: 5

Approach

Java

public class ASignPlace {
    public static void main(String[] args) {
        long mod = 1000000007L;
        int n = 3;
        String lim = "<>";
        System.out.println(solve(n, lim.replace("=", ""), mod));
    }

    private static long solve(int n, String lim, long mod) {
        if (lim.isEmpty()) {
            return n;
        }

        int len = lim.length();
        int[] g = new int[len];
        int[] l = new int[len];

        l[len - 1] = lim.charAt(len - 1) == '<' ? 1 : 0;
        for (int i = len - 2; i >= 0; i--) {
            if (lim.charAt(i) == '<') {
                l[i] = l[i + 1] + 1;
            } else {
                l[i] = 0;
            }
        }

        g[len - 1] = lim.charAt(len - 1) == '>' ? 1 : 0;

        for (int i = len - 2; i >= 0; i--) {
            if (lim.charAt(i) == '>') {
                g[i] = g[i + 1] + 1;
            } else {
                g[i] = 0;
            }
        }

        long[][] dp = new long[n][len + 1];

        if (lim.charAt(0) == '<') {
            for (int i = 0; i < n; i++) {
                dp[i][0] = i < n - l[0] ? 1 : 0;
            }
        } else {
            for (int i = n - 1; i > 0; i--) {
                dp[i][0] = i >= g[0] ? 1 : 0;
            }
        }

        for (int j = 1; j <= len; j++) {
            if (lim.charAt(j - 1) == '<') {
                for (int i = 1; i < n; i++) {
                    dp[i][j] = j == len || i < n - l[j] ? (dp[i - 1][j] + dp[i - 1][j - 1]) % mod : 0;
                }
            } else {
                for (int i = n - 2; i >= 0; i--) {
                    dp[i][j] = j == len || i >= g[j] ? (dp[i + 1][j] + dp[i + 1][j - 1]) % mod : 0;
                }
            }
        }

        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = (res + dp[i][len]) % mod;
        }

        return res;
    }

}