#define HAVE_STRUCT_TIMESPEC

 #include<bits/stdc++.h>

 using namespace std;

 int a[];

 vector<int>v[];

 int l[],r[];

 const long long mod =1e9+;

 int n,m;

 int binary_search_(int color,int num){

     int point=upper_bound(v[color].begin(),v[color].end(),num)-v[color].begin();

     return point;

 }

 pair<int,long long> solve(){

     long long sum=;

     int ans=;

     for(int i=;i<=n;++i){//枚举草的颜色

         int x=binary_search_(i,l[i]);//有x头牛可以放在左边

         int y=binary_search_(i,r[i]);//有y有牛可以放在右边

         if(x*y-min(x,y)>){//两边都可以有牛放置

             ans+=;

             sum=(sum*(x*y-min(x,y)))%mod;//每头牛停止的位置是唯一的（数据保证不存在喜爱相同颜色且数量也相同的牛）

             //有几对喜爱吃颜色i草的牛，答案就乘多少，可以把每头牛看作一个位置，有几对牛可以放置相当于有几对位置可以给它睡觉，没有牛可以在其他牛的位置睡觉，所以有几对牛放置的可能答案就乘多少（相当于在原本的两个集合里分别插入一个元素，元素代表它睡觉的位置）

         }

         else if(x||y){//只有一边可以有牛放置或者两边只能放置同一头牛

             ++ans;

             sum=(sum*(x+y))%mod;//两种情况对答案产生的影响都是x+y，前者x或y有一个是0，后者x和y都是1

         }

     }

     return make_pair(ans,sum);

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     cin>>n>>m;

     for(int i=;i<=n;++i){

         cin>>a[i];

         ++r[a[i]];//[i,n]区间里a[i]出现的次数

     }

     for(int i=;i<=m;++i){

         int x,y;

         cin>>x>>y;

         v[x].emplace_back(y);

     }

     for(int i=;i<=n;++i)

         sort(v[i].begin(),v[i].end());

     int ans=;

     long long num=;

     for(int i=;i<=n;++i){//以i+0.5为分界点

         --r[a[i]];//分界点以右a[i]出现次数-1（a[i]被划到了左边）

         ++l[a[i]];//分界点以左a[i]出现次数+1（a[i]被划到了左边）

         pair<int,long long>pr=solve();

         if(pr.first>ans){

             ans=pr.first;

             num=pr.second;

         }

         else if(pr.first==ans)

             num=(num+pr.second)%mod;

     }

     for(int i=;i<=n;++i){

         l[a[i]]=;//初始化

         ++r[a[i]];//回归枚举分界线以前的状态

     }

     /*举一个重复计算的例子

       8 2

       1 1 1 1 2 2 2 2

       1 2

       2 2

       答案应输出2 3

       不容斥的话会输出2 11

       因为当一次枚举分界点的时候i=2~7，牛的最多头数都是2，可是排列方式总数全都加到了sum中

       通过容斥可以在第二次枚举分界点的时候i=2~6把多余的方案数去掉

       容斥去掉的是实际上被重复计算的那些，可能有多个区间计算了同样的方案，相同方案只计算一次，不同方案还是都应该计入贡献

       容斥去掉第i个位置没有牛的情况，这样可以保证所有计算在内的情况必定有牛要在[0,n]枚举区间i位置时睡觉

     */

     for(int i=;i<n;++i){//第一次枚举分界点的时候计算了很多重复情况，需要用容斥将它挤掉

         //新的分界左边区间是[0,i]，右边区间是[i+2,n]

         --r[a[i+]];

         ++l[a[i]];

         pair<int,long long>pr=solve();

         if(pr.first==ans)

             num=(mod+num-pr.second)%mod;//去掉重复计算的次数

     }

     cout<<ans<<" "<<num;

     return ;

 }