小红有一个数组，她需要对数组操作 次，每次操作有两种选择： 1. 选择数组的最后两个数，记 和 ，将它们从数组中删除，然后将 的个位数放回数组的最后。 2. 选择数组的最后两个数，记 和 ，将它们从数组中删除，然后将 的个位数放回数组的最后。 例如，对于数组 ，选择第一种操作后，数组变为 ，选择第二种操作后，数组变为 。 小红一共操作了 次，显然操作后数组只剩下了一个数。小红想知道，这个数等于 的方案数分别为多少，答案可能很大，你只需要输出答案对 取模的结果。 小红想知道，经过 次操作后，结果为 的方案数分别为多少，答案可能很大，你只需要输出答案对 取模的结果。

输入描述:

一个正整数。代表数组的长度。一行个正整数，代表初始数组。

输出描述:

一行个整数，第个数代表结果为的方案数。