Хогвортс, школа магије и чаробњаштва, припрема се за ускршњи распуст када сви ученици иду кући на заслужени одмор. Како је магија забрањена у свету обичних људи, чаробњаци не носе своје чаробне штапове, већ их остављају Хагриду на чување. Чаробни штапови се чувају у посебним магичним кутијама. Хагрид је врло сенилан, па је заборавио где је оставио магичне кутије, те мора да направи нове.

Да се штапови не би помешали, па да након распуста чаробњаци не могу да нађу свој штап, постоји посебна процедура. Најпре сви чаробњаци, њих \(N\), оставе своје штапове на дугачком столу, а онда их Хагрид редом пакује у кутије. Хагрид мора да их пакује редом, тј свака кутија треба садржати само узастопне штапове.

Мора се водити рачуна и о стабилности кутија. У свакој кутији мора бити исти број штапова. Такође, штапови имају старост, изражену у годинама. Уколико се у једној кутији нађе више од \(К\) чаробних штапова исте старости, може доћи до велике магичне експлозије.

Хагрида занима на колико начина може да упакује штапове у кутије, а да испоштује сва правила.

Опис улаза

У првом реду стандардног улаза налазе се два природна броја, \(N\) - број чаробњака и \(K\) - највећи дозвољени броj штапова исте старости који се могу наћи у једној кутији. У следећем реду налази се N целих бројева, \(А_1, А_2, ..., A_N\) који представљају старости штапова.

Опис излаза

На стандардни излаз потребно је исписати један број, који представља број начина на који Хагрид може поделити штапове у кутије.

Примери

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            6 1<br/>                                          
            1 5 3 3 7 4 
        </span>
        <span class="exampleoutput">
            2
        </span>
    </div>
</div>

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            12 2<br/>
            1 2 3 4 2 3 4 2 1 2 3 4
        </span>
        <span class="exampleoutput">
            5
        </span>
    </div>
</div>

Објашњење примера

У првом примеру К је 1, што значи да сви штапови у једној кутији морају имати различиту старост. Могуће је ставити сваки штап у посебну кутију, или прва три у једну кутију, а следећа три у другу. Ако се стављају по два, друга кутија ће садржати штапове старости 3 и 3, што није стабилно. У другом примеру валидне су поделе на по 1, 2, 3, 4 и 6 штапова по кутији.

Ограничења и подзадаци

• \(1 \leq K \leq 200000\)
• \(1 \leq A_i \leq 10^9\)

Постоје 4 подзадатка, у којима додатно важи:

• Подзадатак 1 [16 поенa]: \(1 \leq N \leq 100\).
• Подзадатак 2 [24 поена]: \(1 \leq N \leq 20000\).
• Подзадатак 3 [29 поена]: \(1 \leq N \leq 200000\) и \(1 \leq A_i \leq 10^6\).
• Подзадатак 4 [31 поена]: \(1 \leq N \leq 200000\).

Напомена

Дозвољено је ставити и све штапове у једну кутију, уколико су испуњни сва правила.