#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    int tst;
    cin >> tst;
    while (tst--) {
        int n;
        cin >> n;
        cout << (n + 1) / 10 << '\n';
    }
}

q = int(input())
for i in range(q):
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	ans = False
	for i in range(n):
		for j in range(0, n - i):
			k = m - 1 - j
			if i + j < k:
				continue                                 
			l1 = i
			r = i + j
			l2 = r - k                                
			if s[l1:r+1] + s[l2:r][::-1] == t:
				ans = True	
	print('YES' if ans else 'NO')

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		int ans = 9;
		
		{
			int cnt0 = 0, cnt1 = 0;
			for (int i = 0; i < 10; ++i) {
				if (i % 2 == 0) cnt0 += s[i] != '0';
				else cnt1 += s[i] == '1'; 
				if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);
				if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);
			}
		}
		
		{
			int cnt0 = 0, cnt1 = 0;
			for (int i = 0; i < 10; ++i) {
				if (i % 2 == 0) cnt0 += s[i] == '1';
				else cnt1 += s[i] != '0'; 
				if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);
				if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);
			}
		}
		
		cout << ans + 1 << '\n';
	}
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 200200;
int n, m;
char s[N], t[N];

bool solve() {
	scanf("%s %s", s, t);
	n = strlen(s);
	m = strlen(t);
	if (n < m) return false;
	int p = (n - m) & 1;
	int q = 0;
	int k = 0;
	for (int i = p; i < n; i++) {
		if (k == 1) {
			k = 0;
			continue;
		}
		if (q < m && s[i] == t[q]) {
			q++;
		} else {
			k++;
		}
	}
	return q == m;
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	int T;
	scanf("%d", &T);
	while(T--) {
		if (solve())
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}

#include <bits/stdc++.h>     

using namespace std; 

int cycle_count(vector<int> q, int n)
{
 	for(int i = 0; i < n; i++)
 		q[i]--;
 	vector<int> used(n);
 	int ans = 0;
 	for(int i = 0; i < n; i++)
 	{
 		if(used[i] == 1) continue;
 		int j = i;
 		while(used[j] == 0)
 		{
 		 	used[j] = 1;
 		 	j = q[j];
 		}
 		ans++;
 	}
 	return ans;
}

bool check(int n, int m, int k, vector<int> p)
{
 	vector<int> q;
 	for(int i = k; i < n; i++)
 		q.push_back(p[i]);
 	for(int i = 0; i < k; i++)
 		q.push_back(p[i]);
 	return n - cycle_count(q, n) <= m;
}

void solve()
{
 	int n, m;
 	scanf("%d %d", &n, &m);
 	vector<int> p(n);
 	for(int i = 0; i < n; i++)
 		scanf("%d", &p[i]);
 	vector<int> cnt(n);
 	for(int i = 0; i < n; i++)
 	{
 	 	int offset = i + 1 - p[i];
 	 	if(offset < 0)
 	 		offset += n;
 	 	cnt[offset]++;
 	}
 	vector<int> ans;
 	for(int i = 0; i < n; i++)
 		if(cnt[i] + 2 * m >= n && check(n, m, i, p))
 			ans.push_back(i);
 	printf("%d", ans.size());
 	for(auto x : ans) printf(" %d", x);
 	puts("");
 			
}

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		solve(); 	
	}
}

// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template<int N> struct Fenw {
    ll t[N + 1];

    Fenw() {
        fill(t + 1, t + N + 1, 0ll);
    }

    void update(int p, ll x) {
        for (; p <= N; p |= (p + 1)) {
            t[p] += x;
        }
    }

    ll get(int p) {
        ll ret = 0;

        for (; p > 0; --p) {
            ret += t[p];
            p &= (p + 1);
        }

        return ret;
    }

    ll get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

const int M = (int)3e5;

void solve() {
    int n;
    cin >> n;
    Fenw<M> A, B;
    ll pref = 0, ans = 0;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ans += x * (i - 1ll);
        ans += A.get(x);
        ans += pref;
        pref += x;
        
        for (int j = x; j <= M; j += x) {
            int l = j, r = min(M, j + x - 1);
            ans -= B.get(l, r) * j;
            A.update(l, -x);
        }

        B.update(x, 1);
        cout << ans << " \n"[i == n];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;

    for (int i = 1; i <= tt; ++i) {
        solve();
    }

    return 0;
}

// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int M = (int)3e5;

namespace A {
    ll t[M * 4];

    void update(int l, int r, ll x, int v = 1, int tl = 1, int tr = M) {
        if (l > r || tl > r || tr < l) {
            return;
        }

        if (l <= tl && tr <= r) {
            t[v] += x;
            return;
        }

        int mid = (tl + tr) >> 1;
        int c1 = (v << 1), c2 = (c1 | 1);

        update(l, r, x, c1, tl, mid);
        update(l, r, x, c2, mid + 1, tr);
    }

    ll get(int p, int v = 1, int tl = 1, int tr = M) {
        if (tl == tr) {
            return t[v];
        }

        int mid = (tl + tr) >> 1;
        int c1 = (v << 1), c2 = (c1 | 1);

        if (p <= mid) {
            return t[v] + get(p, c1, tl, mid);
        }
        else {
            return t[v] + get(p, c2, mid + 1, tr);
        }
    }
}

namespace B {
    ll t[M * 4];

    void update(int p, ll x, int v = 1, int tl = 1, int tr = M) {
        if (tl == tr) {
            t[v] += x;
            return;
        }

        int mid = (tl + tr) >> 1;
        int c1 = (v << 1), c2 = (c1 | 1);

        if (p <= mid) {
            update(p, x, c1, tl, mid);
        }
        else {
            update(p, x, c2, mid + 1, tr);
        }

        t[v] = t[c1] + t[c2];
    }

    ll get(int l, int r, int v = 1, int tl = 1, int tr = M) {
        if (l > r || tl > r || tr < l) {
            return 0ll;
        }

        if (l <= tl && tr <= r) {
            return t[v];
        }

        int mid = (tl + tr) >> 1;
        int c1 = (v << 1), c2 = (c1 | 1);

        return get(l, r, c1, tl, mid) + get(l, r, c2, mid + 1, tr);
    }
}

int n;

void solve() {
    cin >> n;
    ll pref = 0, ans = 0;

    rep (i, 1, n + 1) {
        int x;
        cin >> x;
        ans += x * (i - 1ll);
        ans += A::get(x);
        ans += pref;
        pref += x;
        
        for (int j = x; j <= M; j += x) {
            int l = j, r = min(M, j + x - 1);
            ans -= x * B::get(l, r) * (j / x);
            A::update(l, r, -x * (j / x));
        }

        B::update(x, 1);
        cout << ans << " \n"[i == n];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;

    for (int i = 1; i <= tt; ++i) {
        solve();
    }

    return 0;
}

// gcd, AC, O((N+Q) * log^2), by Errichto
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

struct DSU {
	vector<int> parent;
	DSU(int m) {
		parent.resize(m + 1);
		for(int i = 0; i <= m; ++i) {
			parent[i] = i;
		}
	}
	int find(int a) {
		if(a == parent[a]) {
			return a;
		}
		return parent[a] = find(parent[a]);
	}
	void uni(int a, int b) {
		parent[find(a)] = find(b);
	}
};

int main() {
	// 1) read input
	int n, q;
	scanf("%d%d", &n, &q);
	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	int m = *max_element(a.begin(), a.end());
	// 2) prime sieve
	vector<vector<int>> prime_divisors(m + 2);
	for(int p = 2; p <= m + 1; ++p) {
		if(prime_divisors[p].empty()) {
			for(int j = p; j <= m + 1; j += p) {
				prime_divisors[j].push_back(p);
			}
		}
	}
	// 3) DSU, find initial connected components
	DSU dsu(m + 2);
	for(int x : a) {
		for(int p : prime_divisors[x]) {
			dsu.uni(x, p);
		}
	}
	// 4) DSU, find edges of cost 1
	set<pair<int,int>> edges;
	for(int x : a) {
		vector<int> nodes = prime_divisors[x+1];
		nodes.push_back(x);
		for(int& node : nodes) {
			node = dsu.find(node);
		}
		for(int i = 0; i < (int) nodes.size(); ++i) {
			for(int j = i + 1; j < (int) nodes.size(); ++j) {
				int one = nodes[i];
				int two = nodes[j];
				if(one != two) {
					if(one > two) {
						swap(one, two);
					}
					edges.insert({one, two});
				}
			}
		}
	}
	debug() << imie(edges);
	cerr << imie(edges.size()) << endl;
	// 5) answer queries
	while(q--) {
		int s, t;
		scanf("%d%d", &s, &t);
		--s;
		--t;
		s = dsu.find(a[s]);
		t = dsu.find(a[t]);
		if(s == t) {
			puts("0");
		}
		else if(edges.count({min(s, t), max(s, t)})) {
			puts("1");
		}
		else {
			puts("2");
		}
	}
}

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);
const int K = 20;

struct node
{
 	int max_val, min_val, ans, len;
 	node* left;
 	node* right;

 	void recalc()
 	{
 		len = left->len + right->len;
 		max_val = max(left->max_val, right->max_val + left->len);
 		min_val = min(left->min_val, right->min_val + left->len);
 	 	ans = min(min(left->ans, right->ans), min(INF, right->min_val - left->max_val + left->len));
 	}

 	node(int x)
 	{
 	 	ans = INF;
 	 	len = 1;
 	 	if(x == 1)
 	 	 	max_val = min_val = 0;
 	 	else
 	 	{
 	 	 	max_val = -INF;
 	 	 	min_val = INF;
 	 	}
 	}

 	node(node* l, node* r)
 	{
 	 	left = l;
 	 	right = r;
 	 	recalc();
 	}

 	node() {};
};

int cnt[1 << K];
node tree[2 << K];

int n, k, m;

void build(int v, int l, int r)
{
 	if(l == r - 1)
 		tree[v] = node(cnt[l]);
 	else
 	{
 		int m = (l + r) / 2;
 		build(v * 2 + 1, l, m);
 		build(v * 2 + 2, m, r);
 		tree[v] = node(&tree[v * 2 + 1], &tree[v * 2 + 2]); 	
 	}
 	//cerr << v << " " << l << " " << r << " " << tree[v].min_val << " " << tree[v].max_val << " " << tree[v].len << " " << tree[v].ans << endl;
}

void swap_segments(node* v, int d)
{
	if(d == 0)
	{
	 	swap(v->left, v->right);
	 	v->recalc();
 	}
 	else
 	{
 	 	swap_segments(v->left, d - 1);
 	 	swap_segments(v->right, d - 1);	
 	 	v->recalc();
 	}
 	//cerr << v->min_val << " " << v->max_val << " " << v->len << " " << v->ans << endl;
}

int res[1 << K];

int cur = 0;

void rec(int x)
{
    if(x == 0)
     	res[cur] = tree[0].ans;
    else
    	rec(x - 1);
    swap_segments(&tree[0], x);
    cur ^= (1 << (k - x - 1));
    if(x == 0)
    	res[cur] = tree[0].ans;
    else
    	rec(x - 1);
}	

int main()
{            
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++)
	{
		int x;
	 	scanf("%d", &x);
	 	cnt[x]++;
	}
	m = 1 << k;
	build(0, 0, m);
	rec(k - 1);
	for(int i = 0; i < m; i++)
		printf("%d ", res[i]);
	puts("");
}

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);
const int K = 20;

struct node
{
 	int max_val, min_val, ans, len;
 	
 	node(const node& left, const node& right)
 	{
 		len = left.len + right.len;
 		max_val = max(left.max_val, right.max_val + left.len);
 		min_val = min(left.min_val, right.min_val + left.len);
 	 	ans = min(min(left.ans, right.ans), min(INF, right.min_val - left.max_val + left.len));
 	}

 	node(int x)
 	{
 	 	ans = INF;
 	 	len = 1;
 	 	if(x == 1)
 	 	 	max_val = min_val = 0;
 	 	else
 	 	{
 	 	 	max_val = -INF;
 	 	 	min_val = INF;
 	 	}
 	}

 	node() {};
};

int cnt[1 << K];
vector<node> tree[2 << K];	

void build(int v, int l, int r)
{
	tree[v].resize(r - l);
 	if(l == r - 1)
 	{
 		tree[v][0] = node(cnt[l]);	
 	}
 	else
 	{
 	 	int m = (l + r) / 2;
 	 	build(v * 2 + 1, l, m);
 	 	build(v * 2 + 2, m, r);
 	 	for(int i = 0; i < m - l; i++)
 	 	{
 	 		tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
 	 		tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]); 	
 	 	}
 	}
}

int main()
{            
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++)
	{
		int x;
	 	scanf("%d", &x);
	 	cnt[x]++;
	}
	int m = 1 << k;
	build(0, 0, m);
	for(int i = 0; i < m; i++)
		printf("%d ", tree[0][i].ans);
	puts("");
}

#include<bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define sz(a) ((int)((a).size()))
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

template<const int &MOD>
struct _m_int {
	int val;
 
	_m_int(int64_t v = 0) {
		if (v < 0) v = v % MOD + MOD;
		if (v >= MOD) v %= MOD;
		val = int(v);
	}
 
	_m_int(uint64_t v) {
		if (v >= MOD) v %= MOD;
		val = int(v);
	}
 
	_m_int(int v) : _m_int(int64_t(v)) {}
	_m_int(unsigned v) : _m_int(uint64_t(v)) {}
 
	static int inv_mod(int a, int m = MOD) {
		int g = m, r = a, x = 0, y = 1;
 
		while (r != 0) {
			int q = g / r;
			g %= r; swap(g, r);
			x -= q * y; swap(x, y);
		}
 
		return x < 0 ? x + m : x;
	}
 
	explicit operator int() const { return val; }
	explicit operator unsigned() const { return val; }
	explicit operator int64_t() const { return val; }
	explicit operator uint64_t() const { return val; }
	explicit operator double() const { return val; }
	explicit operator long double() const { return val; }
 
	_m_int& operator+=(const _m_int &other) {
		val -= MOD - other.val;
		if (val < 0) val += MOD;
		return *this;
	}
 
	_m_int& operator-=(const _m_int &other) {
		val -= other.val;
		if (val < 0) val += MOD;
		return *this;
	}
 
	static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
		return unsigned(x % m);
#endif
		// Optimized mod for Codeforces 32-bit machines.
		// x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
		unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
		unsigned quot, rem;
		asm("divl %4\n"
			: "=a" (quot), "=d" (rem)
			: "d" (x_high), "a" (x_low), "r" (m));
		return rem;
	}
 
	_m_int& operator*=(const _m_int &other) {
		val = fast_mod(uint64_t(val) * other.val);
		return *this;
	}
 
	_m_int& operator/=(const _m_int &other) {
		return *this *= other.inv();
	}
 
	friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
	friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
	friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
	friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
 
	_m_int& operator++() {
		val = val == MOD - 1 ? 0 : val + 1;
		return *this;
	}
 
	_m_int& operator--() {
		val = val == 0 ? MOD - 1 : val - 1;
		return *this;
	}
 
	_m_int operator++(int) { _m_int before = *this; ++*this; return before; }
	_m_int operator--(int) { _m_int before = *this; --*this; return before; }
 
	_m_int operator-() const {
		return val == 0 ? 0 : MOD - val;
	}
 
	friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
	friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
	friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
	friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
	friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
	friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
 
	_m_int inv() const {
		return inv_mod(val);
	}
 
	_m_int pow(int64_t p) const {
		if (p < 0)
			return inv().pow(-p);
 
		_m_int a = *this, result = 1;
 
		while (p > 0) {
			if (p & 1)
				result *= a;
			a *= a;
			p >>= 1;
		}
 
		return result;
	}
 
	friend ostream& operator<<(ostream &os, const _m_int &m) {
		return os << m.val;
	}
};
 
extern const int MOD = 998244353;
using Mint = _m_int<MOD>;

const int LOGN = 19;
const int N = (1 << LOGN);
const int T = 2;          
Mint g = 3;

vector<Mint> w[LOGN];
vector<int> rv[LOGN];

void precalc() {
	Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
	forn(st, LOGN - 1) {
		w[st].assign(1 << st, 1);
		Mint bw = wb.pow(1 << (LOGN - st - 1));
		Mint cw = 1;
		forn(k, 1 << st) {
			w[st][k] = cw;
			cw *= bw;
		}
	}
	forn(st, LOGN) {
		rv[st].assign(1 << st, 0);
		if (st == 0) {
			rv[st][0] = 0;
			continue;
		}
		int h = (1 << (st - 1));
		forn(k, 1 << st)
			rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
	}
}

void ntt(vector<Mint> &a, bool inv) {
	int n = sz(a);
	int ln = __builtin_ctz(n);
	forn(i, n) {
		int ni = rv[ln][i];
		if (i < ni) swap(a[i], a[ni]);
	}
	forn(st, ln) {
		int len = 1 << st;
		for (int k = 0; k < n; k += (len << 1)) {
			fore(pos, k, k + len){
				Mint l = a[pos];
				Mint r = a[pos + len] * w[st][pos - k];
				a[pos] = l + r;
				a[pos + len] = l - r;
			}
		}
	}
	if (inv) {
		Mint rn = Mint(n).inv();
		forn(i, n) a[i] *= rn;
		reverse(a.begin() + 1, a.end());
	}
}

vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
	int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
	a.resize(cnt);
	b.resize(cnt);
	ntt(a, false);
	ntt(b, false);
	vector<Mint> c(cnt);
	forn(i, cnt) c[i] = a[i] * b[i];
	ntt(c, true);
	while(c.size() > 1 && c.back() == 0)
		c.pop_back();
	return c;
}

struct dp
{
 	vector<Mint> val[T][T];
 	bool is_unit;

 	dp() {};
 	dp(int len)
 	{
 		is_unit = len == 1;
 		for(int j = 0; j < T; j++)
 			for(int k = 0; k < T; k++)
 				val[j][k] = {0};
 		if(len == 1)
 			val[0][0][0] = 1;
 		else
 			val[1][1][0] = 2;
 	}

 	dp(const dp& a, const dp& b)
 	{
 		is_unit = false;
 		for(int l1 = 0; l1 < T; l1++)
 			for(int r1 = 0; r1 < T; r1++)
 				for(int l2 = 0; l2 < T; l2++)
 					for(int r2 = 0; r2 < T; r2++)
 					{
 					 	vector<Mint> cur = mul(a.val[l1][r1], b.val[l2][r2]);
 					 	if(val[l1][r2].size() < cur.size())
 					 		val[l1][r2].resize(cur.size());
 					 	for(int i = 0; i < cur.size(); i++)
 							val[l1][r2][i] += cur[i];
 					 	Mint merge_coeff = 2;
 					 	if(r1 == 1)
 					 		merge_coeff /= 2;
 					 	if(l2 == 1)
 					 		merge_coeff /= 2;
 					 	cur.insert(cur.begin(), 0);
 					 	for(int i = 0; i < cur.size(); i++)
 					 		cur[i] *= merge_coeff;
 					 	int L1 = l1;
 					 	int R2 = r2;
 					 	if(a.is_unit)
 					 		L1 = 1;
 					 	if(b.is_unit)
 					 		R2 = 1;
 					 	if(val[L1][R2].size() < cur.size())
 					 		val[L1][R2].resize(cur.size());
 					 	for(int i = 0; i < cur.size(); i++)
 					 	{
 					 		val[L1][R2][i] += cur[i];
 						}
 				 	}
 	}
};

ostream& operator<<(ostream& out, const dp& a)
{
 	for(int i = 0; i < T; i++)
 		for(int j = 0; j < T; j++)
 		{
 		 	out << "[" << i << "][" << j << "]";
 		 	for(auto x : a.val[i][j])
 		 		out << " " << x;
 		 	out << endl;
 		}
 	return out;
}

int a[N];
int len[N];
Mint fact[N];
int n;
int s;

dp build(int l, int r)
{
 	if(l == r - 1)
 	{
 		dp res(len[l]);   
 		//cerr << l << " " << r << endl;
 	 	//cerr << res;
 	 	return res;
 	}                     
 	else
 	{
 		int m = (l + r) / 2;
 		dp res(build(l, m), build(m, r));
 		//cerr << l << " " << r << endl;
 		//cerr << res;
 		return res;                         
 	}
}

int main()
{
	precalc();
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	 	scanf("%d", &a[i]);
	int cur = 0;
	while(cur != n)
	{
	 	if(cur + a[cur] > n)
	 	{
         	cout << 0 << endl;
         	return 0;
        }
        for(int l = cur; l < cur + a[cur]; l++)
        	if(a[l] != a[cur])
        	{
        	 	cout << 0 << endl;
        	 	return 0;
        	}
        len[s++] = a[cur];
        cur += a[cur];
	}
	
	fact[0] = 1;
	for(int i = 1; i <= s; i++)
		fact[i] = i * fact[i - 1];

	dp res = build(0, s);

	Mint ans = 0;
	for(int i = 0; i < s; i++)            
		for(int j = 0; j < T; j++)
			for(int k = 0; k < T; k++)
				if(res.val[j][k].size() > i)
					ans += fact[s - i] * res.val[j][k][i] * (i % 2 == 0 ? 1 : MOD - 1);
	cout << ans << endl;
}