#include<cstdio>

 #include<cstring>

 #include<cctype>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int N=1e5+,mod=1e9+;

 int n,m,a[N],sum,b[N];

 inline int read()

 {

     int x=,w=;

     char c=getchar();

     while (!isdigit(c)&&c!='-') c=getchar();

     if (c=='-') c=getchar(),w=-;

     while (isdigit(c))

     {

         x=(x<<)+(x<<)+c-'';

         c=getchar();

     }

     return x*w;

 }

 #undef int

 int main()

 {

     #define int long long

     n=read(),m=read();

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

     {

         a[i]=read(); sum=(sum+a[i])%mod;

     }

     b[]=n-;

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

     {

         b[i]=1ll*(n-)*b[i-]%mod;

         if (i&) b[i]=(b[i]+)%mod;

         else b[i]=(b[i]-+mod)%mod;

     }

     while (m--)

     {

         int x=read(),t=read();

         if (!t) {printf("%lld\n",a[x]); continue;}

         if (t==) {printf("%lld\n",(sum-a[x]+mod)%mod); continue;}

         if (t==) {printf("%lld\n",1ll*(n-)*sum%mod+a[x]%mod); continue;}

         int ans=b[t]; ans=ans*sum%mod;

         if (t&) ans=(ans-a[x]+mod)%mod; else ans=(ans+a[x])%mod;

         printf("%lld\n",ans);

     }

     return ;

 }