const fi = 'TREELINE.INP';
    fo = 'TREELINE.OUT';
    MODD = trunc(1e9);
var n,h,ans,i:longint;
    s:string;
    a:array[1..100000] of longint;

function times(a:string; b:longint):string;
var i,carry,sum:longint;
    ans,tmp:string;
begin
    ans:=''; carry:=0;
    for i:=length(a) downto 1 do
        begin
            sum:=(ord(a[i]) - 48) * b + carry;
            carry:=sum div 10;
            ans:=chr(sum mod 10 + 48) + ans;
        end;
    if(carry > 0) then str(carry,tmp) else tmp:='';
    exit(tmp + ans);
end;

function divide(a:string; b:longint):string;
var tmp,i,hold:longint;
    ans:string;
begin
    ans:=''; hold:=0; tmp:=0;
    for i:=1 to length(a) do
        begin
            hold:=hold * 10 + ord(a[i]) - 48;
            tmp:=hold div b;
            hold:=hold mod b;
            ans:=ans + chr(tmp + 48);
        end;
    while(length(ans) > 1) and (ans[1] = '0') do delete(ans, 1, 1);
    exit(ans);
end;

begin
    assign(input,fi); reset(input);
    assign(output,fo); rewrite(output);
    
    read(n,h);
    for i:=1 to n do read(a[i]);

    ans:=2;
    for i:=n - 1 downto 1 do
        if(a[i] < a[i + 1]) then inc(ans) else break;
    writeln(ans);

    s:='1';
    inc(n);
    for i:=n + 2 to 2 * n do s:=times(s,i);
    for i:=1 to n do s:=divide(s,i);
    val(s,ans);
    writeln(ans mod MODD);

    close(input); close(output);
end.

// Buon buon nen lam` thoi :D

type int = longint;
     long = int64;
const maxn = trunc(1e5);
      MODD = trunc(1e9);
      lim = maxn * 2;
      fi = 'TREELINE.INP';
      fo = 'TREELINE.OUT';
var pr, pow: array[0..lim] of long;
    a: array[0..maxn] of int;
    np: array[0..lim] of boolean;
    i, n, h, cnt: int;

procedure sieve;
var i, j:int;
begin
    for i:=2 to trunc(sqrt(lim)) do
        if not np[i] then
            for j:=i to lim div i do
                np[i * j]:=true;
    for i:=2 to lim do
        if not np[i] then
            begin
                inc(cnt);
                pr[cnt]:=i;
            end;
end;

function powmod(a, n: long):long;
var res: long;
begin
    res:=1;
    while n <> 0 do
        begin
            if n and 1 = 1 then res:=(res * a) mod MODD;
            a:=(a * a) mod MODD;
            n:=n shr 1;
        end;
    exit(res);
end;

procedure analysis(n: long; decrease: boolean);
var i: int;
    x: long;
begin
    for i:=1 to cnt do
        begin
            x:=pr[i];
            while x <= n do
                begin
                    if decrease then dec(pow[i], n div x)
                                else inc(pow[i], n div x);
                    x:=x * pr[i];
                end;
        end;
end;

procedure calc;
begin
    sieve; inc(n);
    analysis(2 * n, false);
    analysis(n + 1, true);
    analysis(n, true);
end;

procedure solve;
var i, ans: int;
    res: long;
begin
    ans:=2;
    for i:=n - 1 downto 1 do
        if a[i] < a[i + 1] then inc(ans)
                           else break;
    writeln(ans);

    calc; res:=1;
    for i:=1 to cnt do
        res:= (res * powmod(pr[i], pow[i])) mod MODD;
    writeln(res);
end;

begin
    assign(input, fi);reset(input);
    assign(output, fo);rewrite(output);
    readln(n, h);
    for i:=1 to n do read(a[i]);
    solve;
    close(input);close(output);
end.