#include <bits/stdc++.h>
using namespace std;

int main()
{
    int tmp;
	while (cin>>tmp)
	{
		string s;
		s = to_string(tmp);
		reverse(s.begin(), s.end());
		tmp = stoi(s);
		string ans;
		while (tmp!=0)
		{
			ans = to_string(tmp % 5)+ans;
			tmp = tmp / 5;
		}
		cout << ans << endl;
	}
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main()
{
    const int mod = 1000000007;
    int n, m;
    cin >> n >> m;
    vector<long long> nums;

    long long tmp;
    while (n--)
    {
        cin >> tmp;

        if (tmp > m)
        {
            continue;
        }
        nums.emplace_back(tmp);
    }
    vector<long long> ans(m + 1, 0);
    ans[0] = 1;
    for (int j = 1; j <= m; ++j) {
        for (int i = 0; i < nums.size(); i++)
        {
            if (j < nums[i])
            {
                continue;
            }
            ans[j] += ans[j - nums[i]] % mod;
        }
    }
    long long c = ans[m] % mod;
    cout << c << endl;
    return 0;
}