FUNTRIP - Chuyến đi vui vẻ
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte

"Có công mài sắt, có ngày nên kim". Sau bao năm miệt mài với khu rừng zigzag, tuankiet65 đã chặt hết chúng xuống để bán lấy tiền. Giờ đây thì tiền bạc rảnh rúng, cậu bèn bày ra kế hoạch đi du lịch cho túi đỡ nặng. Lục lọi trong danh sách top 65535 công ty lữ hành tốt nhất thế giới, anh bị thu hút bởi công ty đứng vị trí #69 Aventure Joyeux do bangjdev, một người bạn cũ của anh sáng lập. Như một ưu đãi cho người đồng đội cũ, bangjdev đã đích thân vạch ra một kế hoạch tham quan các địa điểm du lịch nổi tiếng nhất thế giới với một mức giá vô cùng ưu đãi. Tuy nhiên, với tính cách ngỗ nghịch của mình, tuankiet65 đã đưa ra một thử thách cho vị CEO này, anh ta muốn các chuyến du lịch của mình phải thật "vui".

"Vui là sao cơ?" - bangjdev thắc mắc

Một chuyến du lịch "vui"  là một chuyến du lịch trong N ngày liên tiếp (N >= 2), mỗi ngày 1 địa điểm, sao cho địa điểm của ngày đầu tiên ngày cuối cùng phải khác nhau, hơn nữa các địa điểm từ ngày thứ 2 tới ngày thứ (N - 1) cũng phải khác địa điểm ngày đầu tiên và ngày cuối cùng.

"Tớ muốn biết có tất cả bao nhiêu cách để chọn ra các chuyến đi vui từ các địa điểm mà cậu đề xuất"

Với tư cách là một cựu học sinh chuyên tin, bangjdev không hề lúng túng mà tìm ngay ra cách giải quyết bài toán này.

"Haha lại những bài toán giải thuật quá ảo" - bangjdev cười mãn nguyện

Liệu các bạn có tài giỏi như anh chàng CEO này của chúng ta hay không? Thử xem nhé!

Yêu cầu: Cho xâu kí tự độ dài L mô tả danh sách các địa điểm du lịch mà bangjdev đề xuất. Hãy tính số lượng các chuyến du lịch vui có thể chọn ra từ danh sách này (không được thay đổi thứ tự các địa điểm)

Input:

Một xâu kí tự chiều dài L (L <= 105) mô tả kế hoạch tham quan mà bangjdev đã đề xuất. Kí tự thứ i biểu thị địa điểm du lịch ở ngày thứ i. Các địa điểm du lịch được đánh kí tự tới 'a' tới 'z'.

Output:

Gồm một dòng duy nhất chứa 1 số nguyên là số lượng các chuyến đi vui.

Ví dụ

  • input
    abbcccddddeeeee
    output
    10

Giải thích: Có 10 chuyến du lịch khác nhau thoả mãn điều kiện

  • ab
  • abbc
  • abbcccd
  • abbcccdddde
  • bc
  • bcccd
  • bcccdddde
  • cd
  • cdddde
  • de
Back to Top