#3227. 非回文串(超级加强版)

非回文串(超级加强版)

说明

输入格式

第一行一个正整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 表示字符个数。

<button class="btn btn-primary btn-circle btn-xs" style="--tw-border-spacing-x:0;--tw-border-spacing-y:0;--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;--tw-pan-x:;--tw-pan-y:;--tw-pinch-zoom:;--tw-scroll-snap-strictness:proximity;--tw-gradient-from-position:;--tw-gradient-via-position:;--tw-gradient-to-position:;--tw-ordinal:;--tw-slashed-zero:;--tw-numeric-figure:;--tw-numeric-spacing:;--tw-numeric-fraction:;--tw-ring-inset:;--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgb(59 130 246 / .5);--tw-ring-offset-shadow:0 0 #0000;--tw-ring-shadow:0 0 #0000;--tw-shadow:0 0 #0000;--tw-shadow-colored:0 0 #0000;--tw-blur:;--tw-brightness:;--tw-contrast:;--tw-grayscale:;--tw-hue-rotate:;--tw-invert:;--tw-saturate:;--tw-sepia:;--tw-drop-shadow:;--tw-backdrop-blur:;--tw-backdrop-brightness:;--tw-backdrop-contrast:;--tw-backdrop-grayscale:;--tw-backdrop-hue-rotate:;--tw-backdrop-invert:;--tw-backdrop-opacity:;--tw-backdrop-saturate:;--tw-backdrop-sepia:;display:inline-flex;flex-shrink:0;cursor:pointer;user-select:none;flex-wrap:wrap;align-items:center;justify-content:center;border-width:initial;border-style:none;border-color:initial;transition-property:color, background-color, border-color, text-decoration-color, fill, stroke, opacity, box-shadow, transform, filter, backdrop-filter, -webkit-backdrop-filter;transition-timing-function:cubic-bezier(0, 0, 0.2, 1);transition-duration:0.2s;border-radius:9999px;height:1.5rem;padding:0px;min-height:1.5rem;font-size:0.75rem;line-height:1em;gap:0.5rem;font-weight:600;animation:button-pop var(--animation-btn, .25s) ease-out;text-transform:var(--btn-text-case, uppercase);--tw-border-opacity:1;--tw-bg-opacity:1;--tw-text-opacity:1;outline-color:hsl(var(--p) / 1);width:1.5rem;"><svg viewbox="0 0 24 24" role="presentation" style="width:0.9rem;height:0.9rem;"><path d="M16,12A2,2 0 0,1 18,10A2,2 0 0,1 20,12A2,2 0 0,1 18,14A2,2 0 0,1 16,12M10,12A2,2 0 0,1 12,10A2,2 0 0,1 14,12A2,2 0 0,1 12,14A2,2 0 0,1 10,12M4,12A2,2 0 0,1 6,10A2,2 0 0,1 8,12A2,2 0 0,1 6,14A2,2 0 0,1 4,12Z" style="fill:currentcolor;"></path></svg></button>

第二行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个英文小写字母 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>�</mi><mi>�</mi></msub></mrow></semantics></math>ci

输出格式

仅一行一个整数表示答案。答案对 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></mrow></semantics></math>109+7 取模。

样例

3
aba
4

提示

对于 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>100</mn><mi mathvariant="normal">%</mi></mrow></semantics></math>100% 的数据,每个字母的个数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>2</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow></semantics></math>2×105,保证对于每组输入都一定可以通过重排组成回文串。