Сізге 'a' және 'b' символдарынан тұратын ұзындығы \(n\) жол \(S\) берілген.

Әрбір \(S[i..j]\) қосымша жолы үшін, \(i \le j\) болғанда, оның мәнін анықтаймыз ең ұзын жолдың ұзындығы, ол бір уақытта оның басы (префикс) және соңы (суффикс) болып табылады, бірақ қосымша жолдың толық ұзындығынан қысқа.

Мысалы:

• aba қосымша жолы үшін, оның ең үлкен префиксі, ол суффикске тең, — a. Мәні = \(1\).

• aaaa қосымша жолы үшін, оның мәні = \(3\).

• ab қосымша жолы үшін, оның мәні = \(0\).

\(S[i..j]\) барлық қосымша жолдары бойынша мәндердің сомасын есептеу қажет, мұнда \(i \le j\).

\(S\) жолы берілген \(seed\) саны арқылы келесі түрде генерацияланады:

for (int i = 0; i < n; i++) {
    seed = (seed * 25343 + 49999) % 1000000007;
    S[i] = 'a' + (seed % 2);
}

(Переменная seed типі long long.)

Енгізу

Екі бүтін сан \(n\) және \(seed\) (\(1 \le n \le 10^6\), \(0 \le seed \le 10^9 + 6\)).

Шығару

Барлық қосымша жолдардың мәндерінің сомасын — бір санды шығарыңыз.

Мысалдар

Енгізу 1

10 94845

Жауап 1

39