Problem: Igor had a sequence d_1, d_2, ..., d_n of integers. When Igor entered the classroom there was an integer x written on the blackboard.

Igor generated sequence p using the following algorithm: 

  1. initially, p = [x]; 
  2. for each 1 ≤ i ≤ n he did the following operation |d_i| times: 
    * if d_i ≥ 0, then he looked at the last element of p (let it be y) and appended y + 1 to the end of p; 
    * if d_i < 0, then he looked at the last element of p (let it be y) and appended y - 1 to the end of p. 



For example, if x = 3, and d = [1, -1, 2], p will be equal [3, 4, 3, 4, 5].

Igor decided to calculate the length of the longest increasing subsequence of p and the number of them.

A sequence a is a subsequence of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

A sequence a is an increasing sequence if each element of a (except the first one) is strictly greater than the previous element.

For p = [3, 4, 3, 4, 5], the length of longest increasing subsequence is 3 and there are 3 of them: [\underline{3}, \underline{4}, 3, 4, \underline{5}], [\underline{3}, 4, 3, \underline{4}, \underline{5}], [3, 4, \underline{3}, \underline{4}, \underline{5}].

Input

The first line contains a single integer n (1 ≤ n ≤ 50) — the length of the sequence d.

The second line contains a single integer x (-10^9 ≤ x ≤ 10^9) — the integer on the blackboard.

The third line contains n integers d_1, d_2, …, d_n (-10^9 ≤ d_i ≤ 10^9).

Output

Print two integers: 

  * the first integer should be equal to the length of the longest increasing subsequence of p; 
  * the second should be equal to the number of them modulo 998244353. 



You should print only the second number modulo 998244353.

Examples

Input


3
3
1 -1 2


Output


3 3


Input


3
100
5 -3 6


Output


9 7


Input


3
1
999999999 0 1000000000


Output


2000000000 1


Input


5
34
1337 -146 42 -69 228


Output


1393 3876

Note

The first test case was explained in the statement.

In the second test case p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108].

In the third test case p = [1, 2, …, 2000000000].

Solution (in CPP):

Solution:
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXN = 50;
const int MOD = 998244353;
void inc(int& a, int b) { if ((a += b) >= MOD) a -= MOD; }

int n;
int firstval;
int deltaval[MAXN];
ll anslen; int answays;

ll segfrom[MAXN], segto[MAXN];
vector<ll> special;

vector<int> path;
vector<vector<int>> C;
vector<int> inv;

int choose(ll n, int k) {
	int ret = 1;
	REP(i, k) ret = (ll)ret * ((n - i) % MOD) % MOD * inv[i + 1] % MOD;
	return ret;
}

int calctrans(int s, int t) {
	int npos = 0;
	FOR(i, s, t) if (path[i] == path[s] && path[i + 1] == path[t]) ++npos;
	int nneg = npos - 1;
	ll between = special[path[t]] - special[path[s]] - 1;
	int nbar = npos + nneg - 1;
	//printf("\tnpos=%d nneg=%d between=%lld\n", npos, nneg, between);
	int ret = 0;
	REPE(i, nneg) { // #times neg more than 1
		ll rem = between - 2 * i;
		if (rem < 0) continue;
		int ways = (ll)choose(rem + nbar, nbar) * C[nneg][i] % MOD;
		//printf("\t%d: %d (rem=%lld)\n", i, ways, rem);
		if (i % 2 == 0) inc(ret, ways); else inc(ret, MOD - ways);
	}
	//printf("\t->%d\n", ret);
	return ret;
}


void solve() {
	REP(i, n) {
		segfrom[i] = i == 0 ? firstval : segto[i - 1];
		segto[i] = segfrom[i] + deltaval[i];
	}
	special.clear();
	REP(i, n) special.PB(segfrom[i]), special.PB(segto[i]);
	sort(special.begin(), special.end());
	special.erase(unique(special.begin(), special.end()), special.end());
	//printf("special:"); REPSZ(i, special) printf(" %lld", special[i]); puts("");

	path.clear();
	REP(i, n) {
		int fromidx = lower_bound(special.begin(), special.end(), segfrom[i]) - special.begin();
		int toidx = lower_bound(special.begin(), special.end(), segto[i]) - special.begin();
		if (i == 0) path.PB(fromidx);
		if (fromidx < toidx) FORE(j, fromidx + 1, toidx) path.PB(j);
		if (fromidx > toidx) for (int j = fromidx - 1; j >= toidx; --j) path.PB(j);
	}
	//printf("path:"); REPSZ(i, path) printf(" %d", path[i]); puts("");
	//printf("path:"); REPSZ(i, path) printf(" %lld", special[path[i]]); puts("");

	bool desc = true;
	FORSZ(i, 1, path) if (path[i] > path[i - 1]) desc = false;
	if (desc) { anslen = 1; answays = (special[path[0]] - special[path.back()] + 1) % MOD; return; }

	anslen = 0;
	REPSZ(i, path) FORSZ(j, i + 1, path) if (path[i] < path[j]) anslen = max(anslen, special[path[j]] - special[path[i]] + 1);
	assert(anslen > 0);

	C = vector<vector<int>>(SZ(path) + 1, vector<int>(SZ(path) + 1));
	REPSZ(i, C) { C[i][0] = C[i][i] = 1; FOR(j, 1, i) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; }
	inv = vector<int>(SZ(path) + 1);
	inv[1] = 1; FORSZ(i, 2, inv) inv[i] = (ll)(MOD - MOD / i) * inv[MOD % i] % MOD;

	answays = 0;
	vector<vector<int>> trans(SZ(path), vector<int>(SZ(path), 0));
	REPSZ(i, path) FORSZ(j, i + 1, path) if (path[j] == path[i] + 1) trans[i][j] = calctrans(i, j);
	REPSZ(i, special) {
		vector<int> dp(SZ(path), 0);
		REPSZ(j, path) if (path[j] == i) inc(dp[j], 1);
		REPSZ(j, path) FORSZ(k, j + 1, path) dp[k] = (dp[k] + (ll)dp[j] * trans[j][k]) % MOD;
		REPSZ(j, path) if (special[path[j]] - special[i] + 1 == anslen) inc(answays, dp[j]);
	}
}

void run() {
	scanf("%d", &n);
	scanf("%d", &firstval);
	REP(i, n) scanf("%d", &deltaval[i]);
	solve();
	printf("%lld %d\n", anslen, answays);
}

int main() {
	run();
	return 0;
}