В день празднования Дня Зависимости в Берляндии, было решено устроить грандиозный марафон. Берляндия состоит из n городов, некоторые из которых связаны двусторонними дорогами. Каждая дорога имеет некоторую длину. Города пронумерованы от 1 до n. Известно, что из любого города можно добраться по дорогам в любой другой.

В соревновании принимают участие n бегунов, по одному из каждого города. Но берляндские бегуны по своей натуре — болтуны, и поэтому жюри приняло меры для предотвращения больших скоплений участников марафона. Жюри решило, чтобы каждый спортсмен стартовал из своего родного города. Перед стартом каждый спортсмен получит листок бумаги, на котором будет написано, в каком городе у него расположен финиш. Финиш для каждого спортсмена назначается случайным образом, но не может совпадать с его стартом. Допускается, чтобы у нескольких спортсменов финиш располагался в одном и том же городе. Все спортсмены стартуют одновременно, и каждый бежит от старта до финиша по кратчайшему маршруту. Скорости всех спортсменов одинаковые и равны 1.

По итогам соревнования будет составлена таблица результатов, в которой спортсмены будут отсортированы по неубыванию времени, которое они потратили на преодоление дистанции. Первые g спортсменов в этой таблице получат золотые медали, следующие s спортсменов — серебряные, а остальные бронзовые. Причем, если два или более спортсмена потратили одинаковое время на преодоление дистанции, то они упорядочиваются по возрастанию номеров городов, из которых они стартовали. Из этого следует, что никакие два спортсмена не делят одно и то же место.

По правилам соревнования количество золотых медалей g должно удовлетворять неравенству g₁ ≤ g ≤ g₂, где g₁ и g₂ исторически сложившиеся значения. Аналогично, количество серебряных медалей s должно удовлетворять неравенству s₁ ≤ s ≤ s₂, где s₁ и s₂ тоже исторически сложившиеся значения.

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