游游拿到了一个01串，该字符串仅由'0'和'1'两种字符组成，且第一个字符保证是'1'。 由于该字符串过长，游游用一个大小为的数组表示该字符串： 第一个元素表示字符串开头有个'1'字符，第二个元素表示紧接着有个'0'字符，三个元素表示紧接着有个'1'字符，以此类推。这样就表示了一个长度为的01串。 游游想知道，该01串共有多少个非空回文子串？由于答案可能过大，请对取模。 回文的定义：字符串正着读和倒着读相同，例如"101101"是回文串。 子串的定义：字符串取一段连续的部分，例如"011"是"1011"的子串。

输入描述:

第一行输入一个正整数，代表数组的大小。第二行输入个正整数，代表数组的元素。

输出描述:

回文子串的数量，答案对取模。