tr

Farketmemiz gereken şeylerden ilki bir insanın takabileceği şapka sayısını bulmak için kendi şapkasından büyük eşit tüm şapka sayılarının toplamını bulmamız yeterli. Bunu da soruda verilen \(b\) listesini tersten toplayarak yeni bir \(s\) listesi oluşurarak bulabiliriz. Bu durumda \(x\) büyüklüğünde şapka takan birisinin toplamda takabileceği şapka sayısı \(s_{x}\) olur.

• \(s_i = b_i + b_{i+1} + .. + b_{K-1} + b_{K}\)

Diyelim ki \(a\) kişisinin giydiği şapka \(b\) kişisinkinden daha büyük. Bu demek oluyor ki \(b\) kişisinin takabileceği şapkaların içinde \(a\) kişisinin seçip aldığı şapka da var. Bundan dolayı bu iki kişinin mutlu olabilecekleri olasıkların sayısı:

• \(s_a \cdot(s_b-1)\).

Aslı'nın arkadaşlarını taktıkları şapka boyutlarına göre sıralayıp insanlara şapkaları büyükten küçüğe kaç farklı şapka alabileceklerini çarparak cevabı bulabiliriz. Bunu yaparken her insanın sırası geldiğinde alabileceği şapkalar arasından bir şapka almış olduğunu düşünmeliyiz. Bundan dolayı her hesapladığımız insandan sonra bir sonraki insanın alabileceği şapka sayısı bir azalmalı. Sıralanmış \(a\) listesi ile cevabı aşağıdaki formülle bulabiliriz.

• \(s_{a_N} \cdot(s_{a_{N-1}}-1) \cdot . . . \cdot (s_{a_{2}}-(N-2)) \cdot(s_{a_1}-(N-1))\)

en

The first thing it should be realized is that to find possible hats for a person, it's enough to find the number of hats size of greater than or equal to the size of the hat that person wears. To achieve this, we can sum the list \(b\) in reverse and construct a sum array \(s\). In this case, a person which wears a hat of size \(x\) can wear \(s_{x}\) hats.

• \(s_i = b_i + b_{i+1} + .. + b_{K-1} + b_{K}\)

Assume that person \(a\) wears a hat which is bigger that person \(b\) wears. This means that the set of hats person \(b\) can wear must include the hat person \(a\) wears. Hence different ways of those two people can escape are:

• \(s_a \cdot(s_b-1)\).

Sizes of hats Aslı's friends wear can be sorted to distribute hats in reverse order. To achieve this we multiply the number of different hats each person wears since we do this in reverse order there would be no conflict. The formula can be constructed as follows.

• \(s_{a_N} \cdot(s_{a_{N-1}}-1) \cdot . . . \cdot (s_{a_{2}}-(N-2)) \cdot(s_{a_1}-(N-1))\)

#include <bits/stdc++.h>
using namespace std;

const int md = (int) 1e9 + 7;
long long a[300005], b[300005], n, k, p, res=1, maxa;

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p;
        a[p]++;
        maxa=max(p, maxa);
    }
    for(int i=1;i<=k;i++) {
        cin>>b[i];
    }
    maxa=max(maxa, k);

    for(int i=maxa;i>=1;i--){
        while(a[i]){
            res*=b[i];
            res%=md;
            a[i]--;
            b[i]--;
        }
        b[i-1]+=b[i];
    }
    cout<<res;    
}