Removing Elements
题号：NC276021
时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Let T \subseteq \{1,2,\ldots,n\} be a set of integers. Suppose you have a set S = \{1,2,\ldots,n\}. You may perform the following operations an arbitrary number of times (including zero times):
  • Choose k \in T such that k \le |S|;
  • Remove the k-th largest element in S.
Find the total number of sets S that can be generated through the process. The answer might be enormous, and you should output the desired value modulo 998\,244\,353.

输入描述:

The first line of input contains an integer n (1 \le n \le 200\,000).

The second line of input contains a binary string s=s_1 s_2\ldots s_n of length n, denoting the set T=\{1 \le i \le n \mid s_i = 1\}.

输出描述:

Output an integer in a line, denoting the answer.
示例1

输入

复制 
3
101

输出

复制 
6
示例2

输入

复制 
5
00001

输出

复制 
2
示例3

输入

复制 
10
1011011000

输出

复制 
695