Как-то раз, придя домой со школы, Света обнаружила записку от матери,

Извините,не могли бы вы написать это на языке программирования C++ либо Pascal?

Количество разных салатов R, которые можно приготовить, имея n продуктов и беря для изготовления k из них (k=2,3,... n-1), в математике определяется, как число размещений из n по k и определяется по последующей формуле:

Формула прекрасная, краткая, но неловкая для вычисления. В самом деле, надо отыскать три факториала, каждый из которых может оказаться довольно великим числом. Но можно сделать маленькое преображение и упростить вычисление.


Но это было вычисление R только для определенного k при данном n.
Нам же необходимо отыскать сумму R для всех k от 2 до n. И да, для k=n формула не предназначена, но зато мы и так понимаем, что для такого случая R=1.

Задачка свелась к нахождению обыкновенной суммы


// PascalABC.NET 3.2, сборка 1370 от 24.12.2016
// Внимание! Если программка не работает, обновите версию!

function C(n,k:integer):integer;
begin
  if n=k then Result:=1
  else begin
    var p:=1.0;
    for var i:=1 to n-k do p:=p*(k+i)/i;
    Result:=Round(p);
    end;
end;

begin
  var n:=ReadInteger('Кол-во товаров: ');
  var s:=1;
  for var i:=2 to n-1 do s:=s+C(n,i);
  Writeln('Кол-во салатов: ',s)
end.

Образцы:
Кол-во товаров:  3
Кол-во салатов: 4

Кол-во товаров:  5
Кол-во салатов: 26

Кол-во товаров:  10
Кол-во салатов: 1013