OPTIMAL GREEDY + COMBINATORICS O((R+C)logMOD) TIME
Intuition\n1. try to place \'a\' at i\'th position, now there are (aCount - 1) and bCount characters can be put after i\'th position, count all ways to do it. t
# Intuition\n1. try to place \'a\' at i\'th position, now there are (aCount - 1) and bCount characters can be put after i\'th position, count all ways to do it. that is: (aCount + bCount - 1)! / [(aCount-1)*bCount]. The intution if after putting \'a\' if we are able to generate atleat k different strings then it is optimal to put \'a\'.\n2. if it is >=k then we put \'a\' at i\'th index\n3. otherwise we put \'b\' and subract the ways from k.\n\n# Complexity\n- Time complexity:\nO((R+C)logMOD), MOD = 10^9 + 7\n\n- Space complexity:\nO(R+C)\n\n# Code\n```\nclass Solution {\n    public String kthSmallestPath(int[] destination, int k) {\n        int a = destination[1];\n        int b = destination[0];\n        int sum = a + b;\n        long[] fact = new long[sum+1];\n        long[] invFact = new long[sum+1];\n        fact[0] = invFact[0] = 1;\n        for(int i=1;i<=sum;i++){\n            fact[i] = i*fact[i-1];\n            fact[i]%=mod;\n            invFact[i] = _pow(fact[i],mod-2);\n        }\n    \n        StringBuilder ans = new StringBuilder();\n        for(int i=0;i<sum;i++){\n            if(a == 0){\n                ans.append(\'V\');\n                b--;\n                continue;\n            }\n            if(b == 0){\n                ans.append(\'H\');\n                a--;\n                continue;\n            }\n            long next = ((fact[a+b-1] * invFact[a-1] % mod )*invFact[b]%mod);\n            if(next >= k){\n                ans.append(\'H\');\n                a--;\n            }else {\n                ans.append(\'V\');\n                k-=next;\n                b--;\n            }\n        }\n        return ans.toString();\n\n    }\n    long mod = (int)1e9 + 7;\n    private long _pow(long x, long n){\n        long ans = 1;\n        while(n > 0){\n            if(n%2==1){\n                ans *=x;\n                n--;\n            }else {\n                x*=x;\n                n>>=1;\n            }\n            x%=mod;\n            ans%=mod;\n        }\n        return ans;\n    }\n\n}\n```
['Greedy', 'Combinatorics', 'Java']