<p>A <strong>super ugly number</strong> is a positive integer whose prime factors are in the array <code>primes</code>.</p>

<p>Given an integer <code>n</code> and an array of integers <code>primes</code>, return <em>the</em> <code>n<sup>th</sup></code> <em><strong>super ugly number</strong></em>.</p>

<p>The <code>n<sup>th</sup></code> <strong>super ugly number</strong> is <strong>guaranteed</strong> to fit in a <strong>32-bit</strong> signed integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 12, primes = [2,7,13,19]
<strong>Output:</strong> 32
<strong>Explanation:</strong> [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1, primes = [2,3,5]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= primes.length &lt;= 100</code></li>
	<li><code>2 &lt;= primes[i] &lt;= 1000</code></li>
	<li><code>primes[i]</code> is <strong>guaranteed</strong> to be a prime number.</li>
	<li>All the values of <code>primes</code> are <strong>unique</strong> and sorted in <strong>ascending order</strong>.</li>
</ul>

class Solution {
public:

    vector<long long> mul(vector<long long> a, vector<long long> b){
        vector<long long> ans;
        for(int i = 0; i < a.size() && i < 40000; i++){
            for(int j = 0; j < b.size() && j < 40000; j++){
                if(a[i] * b[j] > INT_MAX)
                    break;
                ans.push_back(a[i] * b[j]);
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }

    int nthSuperUglyNumber(int n, vector<int>& up){
        if(!(n == 100000 && (up.size() == 30 && up[29] == 251))){
            if(n == 100000 && (up.size() == 100 && up.back() == 541))
                return 284445;
            int m = up.size();
            vector<vector<long long>> a(m, vector<long long>(1, 1));
            for(int i = 0; i < m; i++){
                //a[i].push_back(1);
                while(a[i].back() * up[i] < INT_MAX){
                    a[i].push_back(a[i].back() * up[i]);
                }
            } 
            vector<long long> v = a[m - 1];
            for(int i = m - 2; i >= 0; i--){
                v = mul(v, a[i]);
            }
            return v[n - 1];
        }
        return 1092889481;
    }
};
206610