#include<bits/stdc++.h>
using namespace std;
#define int long long
int k[501],d[501],dp[100000];
signed main()
{
	int n,m,ans=0,mn;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>k[i]>>d[i];
	for(int i=0;i<=m;i++)dp[i]=min(k[0],i/d[0]);
	for(int i=1;i<n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=1;k<=(::k[i]);k++)
			{
				if(j-k*d[i]<0)break;
				dp[j]+=dp[j-k*d[i]];
				dp[j]%=19260817;
			}
		}
	}
	for(int i=0;i<=m;i++)
	{
		ans+=dp[i];
		ans%=19260817;
	}
	cout<<ans;
	return 0;
}