#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
//ifstream fin("input.txt");
//ofstream fout("output.txt");
istream &fin = cin;
ostream &fout = cout;
long long mod = 1000*1000*1000+7;
long long megold_brute(int n, int k, const vector<long long> &meret);
long long megold_hatekony(int n, int k, const vector<long long> &meret);
long long megold_elfogadva(int n, int k, const vector<long long> &meret);
int main()
{
/* srand(42);
for (int test = 0; test < 1000000; test++) {
int n = 1 + rand()%10;
vector<long long> meret(n+1);
for (int i = 1; i <= n; i++)
meret[i] = 1+rand()%20;
sort(meret.begin()+1, meret.end());
for (int k = 1; k <= n; k++) {
long long m1 = megold_hatekony(n, k, meret);
long long m2 = megold_brute(n, k, meret);
long long m3 = megold_elfogadva(n, k, meret);
if (m1 != m2 || m2 != m3) {
cout << "e " << m1 << " " << m2 << " " << m3 << endl;
cout << n << " " << k << endl;
for (int i = 1; i <= n; i++)
cout << meret[i] << " ";
cout << endl;
return 0;
}
else
cout << ".";
}
}
cout << "ok" << endl;
*/
int n, k;
fin >> n >> k;
vector<long long> meret(n+1);
for (int i = 1; i <= n; i++)
fin >> meret[i];
fout << megold_hatekony(n, k, meret) << "\n";
//fout << megold_brute(n, k, meret) << "\n";
return 0;
}
long long megold_hatekony(int n, int k, const vector<long long> &meret)
{
vector<long long> pow2(n+1);
pow2[0] = 1;
for (int i = 1; i <= n; i++)
pow2[i] = pow2[i-1]*2 % mod;
vector<long long> sp(n+1, 0); // részösszegek a meret-en
for (int i = 1; i <= n; i++)
sp[i] = sp[i-1] + meret[i];
long long szorzo_bal = 0;
// k balra kell induljon ha nem utolso...
for (int i = 0; i <= k-1; i++) {
// i = hányan indulnak jobbra közvetlenül k előtt
// a (k-i-1). már balra indul ha még létezik
long long kmerete = sp[k] - sp[k-i-1];
if (kmerete >= sp[k-i-1]) {
long long lehetosegek_elotte = pow2[max(0, k-1 - i - 1)];
szorzo_bal = (szorzo_bal + lehetosegek_elotte) % mod;
}
}
/*
i > k esetén legyen
dp[i] = az i, i+1, ... n lárvák olyan indulási lehetőségeinek száma,
melyekkel nem alakul ki sum(meret[1], meret[i-1])-nél
nagyobb vagy egyenlő lárva (aki felfalná a balra levőket)
dp[n+1] = 1
dp[n] = {
0, ha meret[n] >= sum(meret[1]...meret[n])
2, különben (indulhat balra vagy jobbra is)
}
dp[i] = {
0, ha meret[i] >= sum(meret[1]...meret[i-1])
különben: sum(
// i balra indul:
dp[i+1],
// i jobbra indul:
sum(dp[x+1], minden x-re, ahol
i < x <= n és
sum(meret[i]...meret[x]) < sum(meret[1], meret[i-1])
)
)
}
= sum(dp[x+1], minden x-re, ahol
i <= x <= n és
sum(meret[i]...meret[x]) < sum(meret[1], meret[i-1])
)
dp kiszámolható O(N*log(N)) időben, ha minden i-re binárisan
keressük a legnagyobb x-et és a dp tömbön is részösszegeket
számolunk menet közben
*/
if (k == n)
return 2 * szorzo_bal % mod;
if (meret[n] >= sp[n-1])
return 0;
vector<long long> dp(n+2);
vector<long long> dps(n+3); // dps[i] = dp[i] + dp[i+1] + ... + dp[n+1]
dps[n+2] = 0;
dp[n+1] = 2;
dps[n+1] = dp[n+1] + dps[n+2];
dp[n] = 2;
dps[n] = dp[n] + dps[n+1];
for (int i = n-1; i > k; i--) {
int xbal = i, xjobb = n;
while (xbal < xjobb) {
int mid = (xbal+xjobb+1)/2;
if (sp[mid]-sp[i-1] < sp[i-1])
xbal = mid;
else
xjobb = mid-1;
}
if (sp[xbal] - sp[i-1] < sp[i-1]) {
dp[i] = dps[i+1] - dps[xbal+2]; /* dp[i+1] + ... + dp[x+1] */
dp[i] = (dp[i]+mod)%mod;
}
else {
//dp[i] = 0;
return 0;
}
dps[i] = (dp[i] + dps[i+1]) % mod;
}
return (szorzo_bal * dp[k+1])%mod;
}
//-----------------------------------------------------
struct Larva
{
int sorszam;
int poz;
int irany;
int meret;
};
long long megold_brute(int n, int k, const vector<long long> &meret)
{
int nrsol = 0;
int limit = 1 << n;
for (int mask = 0; mask < limit; mask++) // 0-bal, 1-jobb
{
vector<Larva> larvak(n);
for (int i = 1; i <= n; i++) {
larvak[i-1].sorszam = i;
larvak[i-1].poz = i;
larvak[i-1].irany = ((mask & (1 << (i-1))) == 0) ? -1 : 1;
larvak[i-1].meret = meret[i];
}
while (larvak.size() > 1) {
// lepnek
for (int i = 0; i < (int) larvak.size(); i++) {
larvak[i].poz += larvak[i].irany;
if (larvak[i].poz == 0) {
larvak[i].poz = 1;
larvak[i].irany = 1;
}
if (larvak[i].poz == n+1) {
larvak[i].poz = n;
larvak[i].irany = -1;
}
}
// esznek
for (int i = 0; i < (int) larvak.size() - 1; i++) {
if (larvak[i].poz >= larvak[i+1].poz) {
if (larvak[i].meret <= larvak[i+1].meret) {
larvak[i+1].meret += larvak[i].meret;
larvak.erase(larvak.begin()+i);
}
else {
larvak[i].meret += larvak[i+1].meret;
larvak.erase(larvak.begin()+i+1);
}
i--;
}
}
}
if (larvak[0].sorszam == k)
nrsol++;
}
return nrsol % mod;
}
long long megold_elfogadva(int n, int k, const vector<long long> &meret)
{
vector<ll> v = meret;
vector<ll> s(n + 1) ;
s[0] = 0 ;
for(int i = 1 ; i <= n ; i++)
{
s[i] = s[i - 1] + v[i] ;
}
ll ans = 1 ;
for(int i = 1 ; i < k ; i++)
{
if(2 * s[i] <= s[k])
{
ans *= 2 ;
ans %= mod ;
}
}
ll dp[n + 6] ;
ll S[n + 6] ;
dp[k] = ans ;
S[k] = ans ;
S[k - 1] = 0 ;
dp[k - 1] = 0 ;
for(int i = k + 1 ; i <= n ; i++)
{
int tl = k + 1 , tr = i ;
while(tr != tl)
{
int tm = (tl + tr) / 2 ;
if(s[tm - 1] > s[i] - s[tm - 1])
tr = tm ;
else
tl = tm + 1 ;
}
if(s[i - 1] <= v[i])
{
dp[i] = 0 ;
}
else
{
dp[i] = S[i - 1] - S[tl - 2] ;
}
if(dp[i] < 0)
dp[i] += mod ;
dp[i] %= mod ;
S[i] = S[i - 1] + dp[i] ;
if(S[i] < 0)
S[i] += mod ;
S[i] %= mod ;
}
dp[n] *= 2 ;
dp[n] %= mod ;
return dp[n] ;
}