22147번 - Монеты 다국어

Анк-Морпорк — огромный город с оживленной торговлей. В его порт заглядывают корабли из самых дальних стран. В связи с этим в обращении циркулирует большое количество монет разных государств. Для упрощения торговых отношений, у каждой монеты есть фиксированный обменный курс к официальной валюте города — Анк-Морпоркскому доллару. Будем называть этот курс номиналом монеты.

Подобное разнообразие приводит к тому, что даже самые опытные горожане иногда путают монеты между собой. Вот и волшебник Ринсвинд недавно заплатил за новую шляпу T долларов вместо положенных S. К тому моменту, когда он это обнаружил, лавочника уже и след простыл.

Ринсвинд считает, что он какую-то монету принял за другую, скажем, дублон за стерлинг. Каждый раз, когда он думал, что отсчитывает стерлинг, на самом деле он отдавал дублон. При этом настоящих стерлингов он не платил. Например, Ринсвинд мог думать, что заплатил дублон и два стерлинга, а на самом деле он отдал три дублона.

Ринсвинду интересно, сколько существует пар монет таких, что приняв первую монету за вторую, он мог заплатить ровно T долларов вместо S, как он посчитал.

Например, если в обращении есть монеты номиналом один, два и три доллара, и Ринсвинд заплатил десять долларов вместо девяти, то он мог это сделать, если принял монеты номиналом два за монеты номиналом один и заплатил, например, четыре монеты номиналом два и одну монету номиналом два, которую принял за монету номиналом один. Также, он мог принять монеты номиналом три за монеты номиналом два и заплатить семь монет номиналом один и одну номиналом три, которую принял за монету номиналом два.

А если в обращении есть монеты номиналом два, три и четыре доллара, и Ринсвинд заплатил одиннадцать долларов вместо десяти, то он мог это сделать, если принял монеты номиналом три за монеты номиналом два и заплатил две монеты номиналом четыре и одну монету номиналом три, которую принял за монету номиналом два.

Первая строка содержит три целых числа S, T и n (1 ≤ S, T ≤ 10000; S ≠ T; 1 ≤ n ≤ 200) — стоимость шляпы, сумма, потраченная Ринсвиндом, и число монет, соответственно.

Следующая строка содержит n целых чисел a₁, a₂, ..., a_n — номиналы монет (1 ≤ a_i ≤ 10000). Никакие две монеты не имеют одинаковый номинал.

Выведите число пар монет таких, что приняв первую монету за вторую, Ринсвинд мог заплатить T долларов вместо S.