#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
ofstream file("debug.txt");
#define debug(x) file << (#x) << " = " << x << endl << flush
#define sz(x) (int)x.size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef long double ld;
template<typename Int>
ostream& operator<<(ostream &s, const vector<Int> &v) {
	s << '[';
	for (auto i = v.begin(); i != v.end(); i++) {
		s << *i;
		if (i != prev(v.end()))
			s << ", ";
	}
	s << ']';
	return s;
}
template<typename Int, typename INT>
ostream& operator<<(ostream &s, const map<Int, INT> &mp) {
	s << '[';
	for (auto &i : mp) {
		s << '[' << i.first << ", " << i.second << ']';
		if (i != *mp.rbegin())
			s << ", ";
	}
	s << ']';
	return s;
}
template<typename Int>
ostream& operator<<(ostream &s, const set<Int> &st) {
	s << '[';
	for (auto &i : st) {
		s << i;
		if (i != *st.rbegin())
			s << ", ";
	}
	s << ']';
	s << endl;
	return s;
}
template<typename Int, typename INt>
ostream& operator<<(ostream &s, const pair<Int, INt> &x) {
	s << '[' << x.first << ", " << x.second << ']';
	return s;
}
template<typename T>
void print(T *x, int n) {
	for (int i = 0; i < n; i++) {
		file << x[i] << " \n"[i == n - 1];
	}
}
template<typename T>
ostream& operator<<(ostream &s, const complex<T> &a) {
	s << '(' << a.real() << ", " << a.imag() << ')';
	return s;
}
//	Always think of patterns (LCM, GCD)
//	Be careful of unsigned
//	Think of a solution that gets TLE and optimize it
//	Use binary search
//	Solve on paper first
//	Reverse Thinking
//	Monotonic stack/dequeue
//	EV is computed using probabilities or number of ways
//	E(X + Y) = E(X) + E(Y)
//	E(X * Y) = E(X) * E(Y)
//	If there's an equation, transform it into an easy one
//	READ ALL PROBLEMS
const int N = 3e3 + 5;
const int MOD = 1e9 + 7;
int n, y[N][N], dp[N][N], mods[N];
ll x[N];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	clock_t START_TIME = clock();
#endif
	cin >> n;
	memset(y, -1, sizeof y);
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
		x[i] += x[i - 1];
		y[i][1] = i;
	}
	for (int i = 2; i <= n; i++) {
		memset(mods, -1, i * 4);
		for (int j = n; j; j--) {
			mods[x[j] % i] = j;
			int &tmp = mods[x[j - 1] % i];
			if (~tmp)
				y[j][i] = tmp;
		}
	}
	/*
	 for (int i = 1; i <= n; i++)
	 for (int j = 1; j <= n; j++)
	 file << y[i][j] << "\t\n"[j == n];
	 */
	dp[1][1] = 1;
	for (int mod = 1; mod <= n; mod++)	// group number
		for (int idx = 1; idx <= n; idx++) {	// index
			int &ret = dp[mod][idx], &ed = y[idx][mod];
			dp[mod + 1][ed + 1] += ret;
			dp[mod + 1][ed + 1] %= MOD;
			if (ed != n) {
				dp[mod][ed + 1] += ret;
				dp[mod][ed + 1] %= MOD;
			}
		}
	/*
	 for (int i = 1; i <= n; i++)
	 for (int j = 1; j <= n; j++)
	 file << dp[i][j] << " \n"[j == n];
	 */
	int ans = 0;
	for (int i = 1; i <= n + 1; i++)
		ans = (ans + dp[i][n + 1]) % MOD;
	cout << ans;
#ifndef ONLINE_JUDGE
	printf("\n// Time taken = %.3f ms",
			(clock() - START_TIME) * 1e3 / CLOCKS_PER_SEC);
#endif
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define ll long long
#define F(type, i, a, b, incr) for (type i = a; i <= (type)(b); i += (type)(incr))
#define RF(type, i, a, b, decr) for (type i = a; i >= (type)(b); i -= (type)(decr))
#define sz(a) sizeof(a)
#define deb(a) cerr << " [" << #a << "->" << a << "] "
#define next_line cerr << '\n'
#define all(a) a.begin(), a.end()
#define iter(it, s) for (auto it = s.begin(); it != s.end(); it++)
#define setbits(x) __builtin_popcountll(x)
using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

/*
1. If you cannot approach a problem
directly in the way it is proposed 
then try to think from backwards
2. Have you checked the implementation 
before starting to write the code?
3. Have you read the question carefully ?
4. Keep the names of variable descriptive.
5. Check the types and range of the values properly
6. Erase a iterator in the set or map only after using its value.
7. 1 bitset of 1e9 size only takes 256 mb.
8. Try to use global variables in case of recursion
9. Short and precise exectutes faster
*/

int INF = 1e16;
// graph[i] = stores the vectors of [neighbour, weight]
void DijikstraWithQueue(vector<int> &ans, vector<vector<vector<int> > > &graph, int s, int n)
{
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> > frontier;
    frontier.push(make_pair(0, s));
    ans.assign(n, INF);
    ans[s] = 0;
    vector<bool> visited(n, false);
    while(!frontier.empty())
    {
        int node = frontier.top().second, dis = frontier.top().first;
        frontier.pop();
        visited[node] = true;
        if(ans[node] != dis)
            continue;
        if(ans[node] == INF)
            break;
        for(vector<int> e : graph[node])
        {
            if(!visited[e[0] ])
            {
                //ans[e[0] ], e[0]
                int nx = (((ans[node] % e[2]) != 0LL) + (ans[node ] / e[2])) * e[2];
                if(ans[e[0] ] > nx + e[1])
                {
                    ans[e[0] ] = nx + e[1];
                    frontier.push(pair<int,int>(ans[e[0] ] , e[0]));
                }
            }
        }
    }
}

void solve()
{
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    vector<vector<vector<int> > > graph(n);
    F(int, i, 1, m, 1){
        int a, b,k,t;
        cin >> a >> b >> t >> k;
        a--;
        b--;
        graph[a].push_back(vector<int>{b, t, k});
        graph[b].push_back(vector<int>{a, t, k});
    }
    vector<int> ans(n);
    x--;
    y--;
    DijikstraWithQueue(ans, graph, x, n);
    if(ans[y] == INF)
        cout << "-1\n";
    else
        cout << ans[y] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        // freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
        // freopen("Debug.txt", "w", stderr);
    #else
    #endif
    // cout << fixed << setprecision(10);
    // int _t;
    // cin>>_t;
    // while(_t --)
        solve();
}
