stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<string>

#include<sstream>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<cmath>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#include<functional>

#include<numeric>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

using ll = long long;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};



// 二項係数計算

long long com(ll n){

    ll k = 2;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return n*(n-1)/2;

}



int main()

{



    ll N;

    cin >> N;

    vector<ll> A;

    ll same[200005] = {};

    int done[200005] = {};



    for(ll i=0; i<N; ++i)

    {

        ll tmp;

        cin >> tmp;

        A.push_back(tmp);

        ++same[tmp];

    }



    ll all = 0;

    for(ll i=0; i<N; ++i)

    {

        if(done[A[i]]==1) continue;

        else

        {

            done[A[i]] = 1;

            all += com(same[A[i]]);

        }

    }



    for(ll i=0; i<N; ++i)

    {

        cout << all - com(same[A[i]]) + com(same[A[i]]-1) << endl;

    }



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3057892443447425x):
#include<iostream>

#include<string>

#include<sstream>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<cmath>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#include<functional>

#include<numeric>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

using ll = long long;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};



// 二項係数計算

long long com(ll n){

    ll k = 2;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return n*(n-1)/2;

}



int main()

{



    int N;

    cin >> N;

    vector<int> A;

    int same[200005] = {};

    int done[200005] = {};



    for(ll i=0; i<N; ++i)

    {

        ll tmp;

        cin >> tmp;

        A.push_back(tmp);

        ++same[tmp];

    }



    ll all = 0;

    for(ll i=0; i<N; ++i)

    {

        if(done[A[i]]==1) continue;

        else

        {

            done[A[i]] = 1;

            all += com(same[A[i]]);

        }

    }



    for(ll i=0; i<N; ++i)

    {

        cout << all - com(same[A[i]]) + com(same[A[i]]-1) << endl;

    }



    return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.960677122582098x):
#include<bits/stdc++.h>

using namespace std;

map<int,long long>sum;

int a[200005];

long long sss(long long n){

    if(n<=1) return 0;

    long long a=n*(n-1)/2;

    return a;

}

int main(){

    int n;

    long long s=0;

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

        sum[a[i]]++;

    }

    map<int,long long>::iterator it;

    for(it=sum.begin();it!=sum.end();it++)

        s=s+sss(it->second);

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

        if(sum[a[i]]>=2){

            printf("%lld\n",s-sss(sum[a[i]])+sss(sum[a[i]]-1));

            continue;

        }

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

    }

    return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.8870595346579275x):


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int arra[200007];



ll combination(ll n){

    return (n*(n-1))/2;

}



int main(){

    ll n, x, i, sum=0, temp;

    cin >> n;

    map<int, int>m;

    map<int, int>::iterator it;

    vector<int>v;

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

        cin >> x;

        arra[x]++;

        m[x] = arra[x];

        v.push_back(x);

    }

    for(it=m.begin(); it!=m.end(); it++){

        temp = it->second;

        sum += combination(temp);

    }

    for(i=0; i<v.size(); i++){

        temp = m[v[i]];

        cout << sum - combination(temp) + combination(temp-1) << endl;

    }

    return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.893733938468063x):
#include <bits/stdc++.h>

using namespace std;

const long long N=2e5;

long long a[N+5],cont[N+5];

long long ans[N+5];

int main() {

	long long n;

	cin>>n;

	vector < long long > v;

	set < long long > vis;

	for(long long i=0;i<n;i++) {

		cin>>a[i];

		if(vis.count(a[i])==0) v.push_back(a[i]);

		cont[a[i]]++;

		vis.insert(a[i]);

	}

	long long sum=0;

	for(long long i=0;i<v.size();i++) {

		sum+=cont[v[i]]*(cont[v[i]]-1)/2;

	}

	for(long long i=0;i<n;i++) {

		cout<<sum-(cont[a[i]]-1)<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.93766949677078x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

map<int,int> mp;

int a[200005];

ll cnt[200005];

ll sum;

int main()

{

    int n;  cin>>n;

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

    {

        scanf("%d",&a[i]);

        mp[a[i]]++;

    }

    for(auto it=mp.begin();it!=mp.end();it++)

    {

        ll t = it->second;

        sum+=t*(t-1)/2;

    }

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

    {

        ll ans=sum-(ll)mp[a[i]]+1;

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

    }

    return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.8932902538980025x):
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;



int main()

{

    ll n;

    cin>>n;

    map<ll,ll>mp;

    ll a[n+1];

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

    {

        cin>>a[i];;

        mp[a[i]]++;

    }

    ll sum=0;

    for(auto it:mp)

    {

        ll p = it.second;

        sum+=p*(p-1)/2;

    }

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

    {

        cout<<sum-(mp[a[i]]-1)<<endl;

    }

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.806713422191308x):
#include <iostream>

#include <cassert>

#include <algorithm>

#include <map>



#define N ((int)2e5)

using namespace std;

typedef long long ll;

int main(int argc,char ** argv)

{

    int n,a[N];

    ll ans=0;

    cin>>n;

    map<int,int> mp;

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

        cin>>a[i];

        ++mp[a[i]];

    }

    for(auto iter:mp){

        ans+=iter.second*((ll)iter.second-1)/2;

    }

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

        int t=mp[a[i]];

        cout<<ans-(t-1)<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.936464851687941x):
#include <bits/stdc++.h>

using namespace std;



constexpr const int N = 2e5 + 10;



using ll = long long;



int n;

ll a[N];

map<ll, ll> ms;



int main() {

    cin >> n;



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

        cin >> a[i];

        

        ++ms[a[i]];

    }



    ll res = 0;



    for (auto it : ms) {

        ll cnt = it.second;



        if (cnt >= 2) {

            res += cnt * (cnt - 1LL) / 2LL;

        }

    }



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

        ll ans = 0;



        if (ms[a[i]] >= 2) {

            ans = res - ms[a[i]] * (ms[a[i]] - 1LL) / 2LL;

            ans += (ms[a[i]] - 1LL) * (ms[a[i]] - 2LL) / 2LL;

        }

        else {

            ans = res;

        }



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

    }



    return 0;

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.969706551583576x):
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=200000+50;

int n;

int a[maxn];

int f[maxn];

int vis[maxn];

int tot;

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&a[i]);

        if(vis[a[i]]) f[vis[a[i]]]++;

        else

        {

            vis[a[i]]=++tot;

            f[vis[a[i]]]++;

        }    

    }   

    long long ans=0;

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

    {

        long long b=f[i];

        ans+=b*(b-1);

    }



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

    {

        long long b=f[vis[a[i]]];

        cout<<ans/2-b+1<<'\n';

    }

    return 0;



}
// Slower C++ solution:
#include<algorithm>

#include<iostream>

#include<stdio.h>

typedef long long ll;

using namespace std;



const ll mod = 998244353;

const ll inv2 = (mod + 1) >> 1;

ll poww(ll a, ll b){

	ll res = 1;

	while (b){

		if (b & 1) res = res * a % mod;

		a = a*a%mod;

		b >>= 1;

	}

	return res;

}



int n, s;

int a[3005];

ll c[3005];

int main(){

	cin >> n >> s;

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

		cin >> a[i];

		c[i] = 0;

	}

	c[0] = poww(2, n);

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

		for (int j = 3000 - a[i]; j >= 0; j--){

			c[j + a[i]] = (c[j + a[i]] + c[j]*inv2) % mod;

		}

		continue;

	}

	cout << c[s] << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.142162035705416x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e3 + 5;

const int INF = 0x7f7f7f7f;

const ll p = 998244353;

#define DEBUG(x) cout << x << '\n'



int n, s, t, f[MAXN];

ll f_pow(ll a, ll b){

    ll res = 1;

    for(; b; b >>= 1, a = a * a % p)

        if(b & 1) res = res * a % p;

    return res;

}

int main(){

#ifdef Irene

    freopen("in.txt", "r", stdin);

#endif // Irene

    ios::sync_with_stdio(false);



    cin >> n >> s;

    f[0] = f_pow(2, n);

    ll inv2 = f_pow(2, p - 2);

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

        cin >> t;

        for(int j = s - t; j >= 0; j--)

            f[j+t] = (f[j+t] + f[j] * inv2) % p;

    }

    cout << f[s];

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define watch(x) cout << (#x) << " is " << (x) << endl

const int mod = 998244353;



using namespace std;



int s, n;



void knapsackSubset()		//coeff x^s du polynome Pi(2+x^ai)

{	

	scanf("%d%d", &n, &s);

	int x;

	vector<long long> coeff(3000, 0);

	cin >> x;

	coeff[0] = 2, coeff[x] = 1;

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

	{

		scanf("%d", &x);

		vector<long long>oldCo = coeff; //ancient coordonnes, (ne pas oublier qu'on mulitplie par 2, on doit se rappeler des ancierts coo, quitte a diviser par 2 aussi)

		for (int j = 0; j <= s; j++)

		{

			coeff[j] = (2*coeff[j])%mod;

			if (j >= x)

				coeff[j] += oldCo[j-x];

			coeff[j] %= mod;

		}

	} 

	cout << coeff[s] << endl;	

}



int main()

{

	#ifdef ME

		freopen("input.txt", "r", stdin);

		freopen("output.txt", "w", stdout);

	#endif



	knapsackSubset();

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.2548998277806909x):
#include <bits/stdc++.h>

#define watch(x) cout << (#x) << " is " << (x) << endl

const int mod = 998244353;



using namespace std;



int s, n;



void knapsackSubset()		//coeff x^s du polynome Pi(2+x^ai)

{	

	scanf("%d%d", &n, &s);

	int x;

	vector<long long> coeff(s+1, 0);

	cin >> x;

	coeff[0] = 2;

	if (x <= s)

	 coeff[x] = 1;

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

	{

		scanf("%d", &x);

		vector<long long>oldCo = coeff; //ancient coordonnes, (ne pas oublier qu'on mulitplie par 2, on doit se rappeler des ancierts coo, quitte a diviser par 2 aussi)

		for (int j = 0; j <= s; j++)

		{

			coeff[j] = (2*coeff[j])%mod;

			if (j >= x)

				coeff[j] += oldCo[j-x];

			coeff[j] %= mod;

		}

	} 

	cout << coeff[s] << endl;	

}



int main()

{

	#ifdef ME

		freopen("input.txt", "r", stdin);

		freopen("output.txt", "w", stdout);

	#endif



	knapsackSubset();

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int64_t MOD = 998244353;



int64_t N_MAX = 3010;



int64_t dp[3010][3010];



//modの割り算

// a/bをa*modint(b,MOD) %MODに変換

long long modinv(long long a, long long m) {

  long long b = m, u = 1, v = 0;

  while (b) {

    long long t = a / b;

    a -= t * b; swap(a, b);

    u -= t * v; swap(u, v);

  }

  u %= m;

  if (u < 0) u += m;

  return u;

}



//繰り返し二乗法

int64_t powmod(int64_t x, int64_t n) { 

  int64_t ans = 1;

  while (n > 0) {

    if ((n & 1) == 1) {

      ans = ans * x;

      ans %= MOD;

    }

    x = x * x;//一周する度にx, x^2, x^4, x^8となる

    x %= MOD;

    n >>= 1; //桁をずらす n = n >> 1

  }

  return ans;

}



int main(){

  int64_t N, S;

  cin >> N >> S;

  vector<int64_t> vec(N);

  for(int i=0; i<N; i++){

    cin >> vec[i];

  }

  for(int i=0; i<N; i++){

    int64_t x = vec[i];

    dp[i+1][x] = powmod(2,N-1);

    for(int j=0; j<N_MAX; j++){

      dp[i+1][j] += dp[i][j]; //加えない

      if(j + x < N_MAX){ //加える

        int64_t y = dp[i][j];

        y %= MOD;

        y = y*modinv((int64_t)2,MOD) %MOD;

        dp[i+1][j+x] += y;

        dp[i+1][j+x] %= MOD;

      }

      dp[i+1][j] %= MOD;

    }

  }

  cout << (dp[N][S]) %MOD << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.117495437898497x):
#include<bits/stdc++.h>

using namespace std;



int64_t MOD = 998244353;



int64_t N_MAX = 3010;



int64_t dp[3010][3010];



//modの割り算

// a/bをa*modint(b,MOD) %MODに変換

long long modinv(long long a, long long m) {

  long long b = m, u = 1, v = 0;

  while (b) {

    long long t = a / b;

    a -= t * b; swap(a, b);

    u -= t * v; swap(u, v);

  }

  u %= m;

  if (u < 0) u += m;

  return u;

}



//繰り返し二乗法

int64_t powmod(int64_t x, int64_t n) { 

  int64_t ans = 1;

  while (n > 0) {

    if ((n & 1) == 1) {

      ans = ans * x;

      ans %= MOD;

    }

    x = x * x;//一周する度にx, x^2, x^4, x^8となる

    x %= MOD;

    n >>= 1; //桁をずらす n = n >> 1

  }

  return ans;

}



int main(){

  int N, S;

  cin >> N >> S;

  vector<int> vec(N);

  for(int i=0; i<N; i++){

    cin >> vec[i];

  }

  for(int i=0; i<N; i++){

    int x = vec[i];

    dp[i+1][x] = powmod(2,N-1);

    for(int j=0; j<N_MAX; j++){

      dp[i+1][j] += dp[i][j];

      if(j + x < N_MAX){

        int64_t y = dp[i][j];

        y = (y*modinv(2,MOD)) %MOD;

        dp[i+1][j+x] += y;

      }

      dp[i+1][j] %= MOD;

    }

  }

  cout << dp[N][S] << endl;

}
// Slower C++ solution:
#pragma gcc optimize ("O2")

#pragma gcc optimize ("unroll-loops")



#include <bits/stdc++.h>





#define fi first

#define se second

#define pb(a) push_back(a)

#define mp(a, b) make_pair(a, b)

#define el '\n'



using namespace std;

using ll = long long;

using pii = pair<int, int>;



const int N = 1e5 + 10;

const ll MOD = 1e9 + 7;



int n, k;

ll cnt[N];

vector<int> fac[N];



ll fpow(ll a, ll b){

    ll ret = 1;

    while (b){

        if (b & 1){

            ret = ret * a % MOD;

        }

        a = a * a % MOD;

        b >>= 1;

    }

    return ret;

}



int main () {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    cin >> n >> k;

    for (int i=1;i<=k;i++){

        for (int j=i + i;j<=k;j+=i){

            fac[j].pb(i);

        }

    }

    ll ans = 0;

    for (int i=k;i>=1;i--){

        ll bag = k / i;

        ll temp = fpow(bag, n);

        cnt[i] = (cnt[i] + temp + MOD) % MOD;

        ans = (ans + cnt[i] * i) % MOD;



        for (auto x : fac[i]){

            cnt[x] = (cnt[x] - cnt[i] + MOD) % MOD;

        }

    }

    cout << ans << el;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5737941769308517x):
//#include <bits/stdc++.h>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

ll n,k,ans;

ll sum[1000005],mod=1000000007ll;

ll pow1(ll x,ll y){

	ll a=1,b=x;while(y){if(y&1)a=(a*b)%mod;b=(b*b)%mod;y>>=1;}return a;

}

int main(){

    cin>>n>>k;

    for(int i=k;i>=1;i--){

		sum[i]=pow1(k/i,n);

		for(int j=2;i*j<=k;j++){

			sum[i]=(sum[i]-sum[i*j]+mod)%mod;

		}

		ans=(ans+i*sum[i])%mod;

	}

	cout<<ans;

	//system("pause");

    return 0;

}