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

typedef long long ll;
typedef pair<ll, ll> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
/*const*/ ll mod = 1e9+7;

#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)

ll read() {
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void out(ll x) {
	int stackk[40];
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (!x) {
		putchar('0');
		return;
	}
	int top = 0;
	while (x) stackk[++top] = x % 10, x /= 10;
	while (top) putchar(stackk[top--] + '0');
}

ll qpow(ll a,ll b) {
	ll ans=1;
	while(b) {
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

ll n,a[maxn],m,f[121][121][121],ans;
int main() {
	n=read(),m=read();
	rep(i,1,n) a[i] = read();
	ans = m;
	for(int len =1; len<=n ; len++) {
		mst(f,0xcf);
		f[0][0][0] =0 ;
		for(int i=1 ; i<=n ; i++) {
			f[i][0][0] = 0;
			for(int j=1 ; j<=len ; j++) {
				for(int k=0 ; k<len ; k++) {
					f[i][j][k] = f[i-1][j][k];
					f[i][j][k] = max(f[i][j][k],f[i-1][j-1][(((k-a[i])%len)+len)%len]+a[i]);
				}
			}
		}
		if(f[n][len][m%len]>=0) ans = min(ans,(m-f[n][len][m%len])/len);
	}
	out(ans);
	return 0;
}
/*

*/
#include <iostream>
#include <algorithm>

using namespace std;

constexpr int Z = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    bool s[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            s[i][j] = c == '.';
        }
    }

    int dp[n][m], ps[n][m][3];
    fill(dp[0], dp[n], 0);
    fill(ps[0][0], ps[n][0], 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!s[i][j]) {
                continue;
            }

            if (i == 0 && j == 0) {
                dp[i][j]++;
            }
            if (i > 0) {
                dp[i][j] = (dp[i][j] + ps[i-1][j][0]) % Z;
            }
            if (j > 0) {
                dp[i][j] = (dp[i][j] + ps[i][j-1][1]) % Z;
            }
            if (i > 0 && j > 0) {
                dp[i][j] = (dp[i][j] + ps[i-1][j-1][2]) % Z;
            }

            ps[i][j][0] = ((i == 0 ? 0 : ps[i-1][j][0]) + dp[i][j]) % Z;
            ps[i][j][1] = ((j == 0 ? 0 : ps[i][j-1][1]) + dp[i][j]) % Z;
            ps[i][j][2] = ((i == 0 || j == 0 ? 0 : ps[i-1][j-1][2]) + dp[i][j]) % Z;
        }
    }

    cout << dp[n-1][m-1] << endl;

    return 0;
}
