#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;
const int mod = 1e9 + 7;

pii mul(pii a, pii b) {
	ll c = (ll) a.st * b.st - (ll) a.nd * b.nd;
	ll d = (ll) a.st * b.nd + (ll) a.nd * b.st;
	c %= mod;
	d %= mod;
	if(c < 0) c += mod;
	if(d < 0) d += mod;
	return mp((int) c, (int) d);
}

pii pw(pii a, int k) {
	pii r = mp(1, 0);
	while(k) {
		if(k % 2) r = mul(r, a);
		a = mul(a, a);
		k /= 2;
	}
	return r;
}
int pw(int a, int k) {
	int r = 1;
	while(k) {
		if(k % 2) r = (ll) r * a % mod;
		a = (ll) a * a % mod;
		k /= 2;
	}
	return r;
}

int f(int n) {
	int r = pw(mp(1,mod-1), n).st + pw(mp(1,1), n).st;
	r %= mod;
	r += pw(2, n);
	r %= mod;
	r = (ll) r * pw(4, mod - 2) % mod;
	return r;
}

int dp[105];

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	dp[0] = 1;
	REP(_, n) {
		int a;
		scanf("%d", &a);
		a = f(a);
		FORD(j, k, 1)
			dp[j] = (dp[j] + (ll) dp[j-1] * a) % mod;
	}
	printf("%d\n", dp[k]);
	return 0;
}

 
import java.io.*;
import java.util.*;

public class Solution {
  private static InputReader in;
  private static PrintWriter out;
  public static long mod = 1000000007;
  public static long INV4 = pow(new Complex(4,0), mod-2).a;
  
  static class Complex {
    public long a,b;
    public Complex(long a, long b) {
      this.a = a;
      this.b = b;
      if (a < 0) a += mod;
     
    }
    
    public Complex multiply(Complex other) {
      return new Complex((a * other.a + mod - (b * other.b % mod)) % mod, (a * other.b + b * other.a) % mod);
    }
  }
  
  public static Complex pow(Complex a, long e) {
    Complex r = new Complex(1,0);
    while(e>0) {
      if ((e&1)==1) r = r.multiply(a);
      a = a.multiply(a);
      e >>= 1;
    }
    return r;
  }
  
  public static long nways(long x) {
    Complex s1 = pow(new Complex(1, 1), x);
    Complex s2 = pow(new Complex(1, mod - 1), x);
    Complex s3 = pow(new Complex(2, 0), x);
    long res = (s3.a + s1.a + s2.a) % mod;
    return res * INV4 % mod;
  }

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);

    int n = in.nextInt();
    int k = in.nextInt();
    long[] dp = new long[k+1];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
      long m = nways(in.nextInt());
      long[] next = new long[k+1];
      System.arraycopy(dp, 0, next, 0, k+1);
      for (int j = 0; j < k; j++) {
        next[j+1] = (next[j+1] + dp[j] * m) % mod;
      }
      dp = next;
    }
    out.println(dp[k]);
    out.close();
    System.exit(0);
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }


}

#!/bin/python3

import os
import sys
from functools import reduce
from itertools import combinations
#
# Complete the king function below.
#
cc = 10**9 + 7
d30 = 73741817
D2 = 976371285
D3 = 688423210
D4 = 905611805
D5 = 607723520
D6 = 235042059
D7 = 255718402
D8 = 494499948
def twopower(a):
    if a < 30:
        return (2**a)
    elif a >= 30 and a <100:
        dvi = a//30
        rem = a%30
        ans = ((d30**dvi)%cc) * ((2**rem)%cc)
        ans = ans%cc
        return (ans)
    elif a >= 100 and a <= 1000:
        dvi2 = a//100
        dvi = a%100//30
        rem = a%100%30
        ans = ((D2**dvi2)%cc) * ((d30**dvi)%cc)*((2**rem)%cc)
        ans = ans%cc
        return (ans)
def midpower(a):
    if a <= 1000:
        return (twopower(a))
    elif a > 1000 and a <= 10**4:
        x = a //1000
        y = a % 1000
        z = ((D3**x)%cc) * twopower(y)
        z = z%cc
        return (z)
    elif a >10**4 and a <= 10**5:
        x1 = a // 10**4
        x2 = a // 10**3 - x1*10
        y = a % 10**3
        z = ((D4**x1)%cc) * ((D3**x2)%cc) * twopower(y) 
        z = z % cc
        return (z)
    elif a >10**5 and a <= 10**6:
        x1 = a // 10**5
        x2 = a // 10**4 - x1*10
        x3 = a // 10**3 - x2*10 - x1*100
        y = a % 10**3
        z = ((D5**x1)%cc) * ((D4**x2)%cc) * ((D3**x3)%cc) * twopower(y) 
        z = z % cc
        return (z)
def hipower(a):
    if a <= 10**6:
        return (midpower(a))
    elif a > 10**6 and a <= 10**7:
        x = a //10**6
        y = a % 10**6
        z = ((D6**x)%cc) * midpower(y)
        z = z%cc
        return (z)
    elif a >10**7 and a <= 10**8:
        x1 = a // 10**7
        x2 = a // 10**6 - x1*10
        y = a % 10**6
        z = ((D7**x1)%cc) * ((D6**x2)%cc) * midpower(y) 
        z = z % cc
        return (z)
    elif a >10**8 and a <= 10**9:
        x1 = a // 10**8
        x2 = a // 10**7 - x1*10
        x3 = a // 10**6 - x2*10 - x1 *100
        y = a % 10**6
        z = ((D8**x1)%cc) * ((D7**x2)%cc) * ((D6**x3)%cc) * midpower(y) 
        z = z % cc
        return (z)

def fanum(a):
    if a%4 == 0 or a%4 == 1:
        if (a//4) % 2 == 0:
            return (int(hipower(a-2)+hipower(2*(a//4)-1)))
        else:
            return (int(hipower(a-2)-hipower(2*(a//4)-1)))
    elif a%4 == 3:
        if (a//4) % 2 == 0:
            return (int(hipower(a-2) - hipower(2*(a//4))))
        else:
            return (int(hipower(a-2) + hipower(2*(a//4))))
    elif a%4 == 2:
        return (int(hipower(a-2)))
def king(army, k):
    lst = []
    for i in army:
        lst.append(fanum(i))
    lst1 = []
    lst1.append(lst)
    for i in range(1,k):
        l = []
        el = 0
        for j in range(i,n):
            el = (el + lst1[i-1][j-i])%cc
            l.append((el*lst[j])%cc)        
        lst1.append(l)
    tt = sum(lst1[-1])
    return(tt%cc)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    army = list(map(int, input().rstrip().split()))

    result = king(army, k)

    fptr.write(str(result) + '\n')

    fptr.close()

import itertools, math

MOD=int(1e9+7)

def S_(n,k):
    def cnk(n,k):
        return int(math.factorial(n)/(math.factorial(k)*math.factorial(n-k)))
    return sum(cnk(n,i) for i in xrange(k,n+1,4))%MOD

ans=[
    [1],
   [1,1],
  [1,2,1],
 [1,3,3,1],
[1,4,6,4,1]]

def S(n,k=0):
    if n<5:
        return sum(ans[n][k::4])
    r=0
    r=pow(2,n-2,MOD)-pow(2,n/2,MOD)
    if n&1:
        r=(r+pow(2,(n-3)/2,MOD)*sum(ans[3][(k-(n-3)/2)%4::4]))%MOD
    else:
        r=(r+pow(2,(n-3)/2,MOD)*sum(ans[4][(k-(n-3)/2)%4::4]))%MOD
    return int(r)

# for n in (100,101):
#     for k in xrange(4):
#         s_,s=S_(n,k),S(n,k)
#         print "---",n,k,s_==s,s_,s

# exit()

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())

det=[S(i) for i in a]

# s=0
# for comb in itertools.combinations(range(n),k):
#     tot=1
#     for i in comb:
#         tot=(tot*det[i])%MOD
#     s=(s+tot)%MOD
# print s


mem=[[float("+inf")]*(i+1) for i in xrange(n+1)]
mem[0][0]=1
for i in xrange(1,n+1):
    mem[i][1] = sum(det[:i])%MOD
    mem[i][i] = (mem[i-1][i-1]*det[i-1])%MOD
for i in xrange(3,n+1):
    for j in xrange(2,min(i,k+1)):
        mem[i][j] = (mem[i-1][j] + mem[i-1][j-1]*det[i-1])%MOD

print mem[n][k]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
void one(long long*a,int SIZE);
void mul(long long*a,long long*b,int SIZE);
void powm(long long*a,int n,long long*res,int SIZE);
int a[10000];
long long dp[101][10001]={0},b[10000],B[4][4],C[4][4],A[4][4]={
{1,0,0,1},
{1,1,0,0},
{0,1,1,0},
{0,0,1,1}
},aa[4]={1,1,0,0};

int main(){
  int N,K,i,j;
  scanf("%d%d",&N,&K);
  for(i=0;i<N;i++)
    scanf("%d",a+i);
  for(i=0;i<N;i++)
    if(!a[i])
      b[i]=1;
    else{
      memcpy(B,A,sizeof(B));
      powm(&B[0][0],a[i]-1,&C[0][0],4);
      for(j=b[i]=0;j<4;j++)
        b[i]=(b[i]+aa[j]*C[0][j])%MOD;
    }
  dp[0][0]=1;
  for(i=0;i<N;i++)
    for(j=0;j<=K;j++)
      if(j)
        dp[j][i+1]=(dp[j][i]+dp[j-1][i]*b[i])%MOD;
      else
        dp[j][i+1]=dp[j][i];
  printf("%lld",dp[K][N]);
  return 0;
}
void one(long long*a,int SIZE){
    int i,j;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            a[i*SIZE+j] = (i == j);
    return;
}
void mul(long long*a,long long*b,int SIZE){
    int i,j,k;
    long long res[SIZE][SIZE];
    for(i=0;i<SIZE;i++)
      for(j=0;j<SIZE;j++)
        res[i][j]=0;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            for (k = 0; k < SIZE; k++)
                res[i][j] = (res[i][j]+a[i*SIZE+k] * b[k*SIZE+j])%MOD;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            a[i*SIZE+j] = res[i][j];
    return;
}
void powm(long long*a,int n,long long*res,int SIZE){
    one(res,SIZE);
    while (n > 0) {
        if (n % 2 == 0)
        {
            mul(a, a,SIZE);
            n /= 2;
        }
        else {
            mul(res, a,SIZE);
            n--;
        }
    }
}